On socio-spatial group query for location-based social networks

De Nian Yang; Chih Ya Shen; Wang Chien Lee; Ming Syan Chen

doi:10.1145/2339530.2339679

On socio-spatial group query for location-based social networks

De Nian Yang, Chih Ya Shen, Wang Chien Lee, Ming Syan Chen

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

107 Scopus citations

Abstract

Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.

Original language	English (US)
Title of host publication	KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Pages	949-957
Number of pages	9
DOIs	https://doi.org/10.1145/2339530.2339679
State	Published - 2012
Event	18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012 - Beijing, China Duration: Aug 12 2012 → Aug 16 2012

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other	18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012
Country/Territory	China
City	Beijing
Period	8/12/12 → 8/16/12

All Science Journal Classification (ASJC) codes

Software
Information Systems

Access to Document

10.1145/2339530.2339679

Cite this

@inproceedings{e0a3c412981345e38723151fd9c7f45e,

title = "On socio-spatial group query for location-based social networks",

abstract = "Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.",

author = "Yang, {De Nian} and Shen, {Chih Ya} and Lee, {Wang Chien} and Chen, {Ming Syan}",

year = "2012",

doi = "10.1145/2339530.2339679",

language = "English (US)",

isbn = "9781450314626",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

pages = "949--957",

booktitle = "KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

note = "18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012 ; Conference date: 12-08-2012 Through 16-08-2012",

}

Yang, DN, Shen, CY, Lee, WC & Chen, MS 2012, On socio-spatial group query for location-based social networks. in KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 949-957, 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012, Beijing, China, 8/12/12. https://doi.org/10.1145/2339530.2339679

On socio-spatial group query for location-based social networks. / Yang, De Nian; Shen, Chih Ya; Lee, Wang Chien et al.
KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2012. p. 949-957 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On socio-spatial group query for location-based social networks

AU - Yang, De Nian

AU - Shen, Chih Ya

AU - Lee, Wang Chien

AU - Chen, Ming Syan

PY - 2012

Y1 - 2012

N2 - Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.

AB - Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.

UR - http://www.scopus.com/inward/record.url?scp=84866046517&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866046517&partnerID=8YFLogxK

U2 - 10.1145/2339530.2339679

DO - 10.1145/2339530.2339679

M3 - Conference contribution

AN - SCOPUS:84866046517

SN - 9781450314626

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 949

EP - 957

BT - KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

T2 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012

Y2 - 12 August 2012 through 16 August 2012

ER -

On socio-spatial group query for location-based social networks

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this