DocumentCode :
738428
Title :
Geo-Social K-Cover Group Queries for Collaborative Spatial Computing
Author :
Li, Yafei ; Chen, Rui ; Xu, Jianliang ; Huang, Qiao ; Hu, Haibo ; Choi, Byron
Author_Institution :
Department of Computer Science, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China
Volume :
27
Issue :
10
fYear :
2015
Firstpage :
2729
Lastpage :
2742
Abstract :
With the rapid development of location-aware mobile devices, ubiquitous Internet access and social computing technologies, lots of users’ personal information, such as location data and social data, has been readily accessible from various mobile platforms and online social networks. The convergence of these two types of data, known as geo-social data, has enabled collaborative spatial computing that explicitly combines both location and social factors to answer useful geo-social queries for either business or social good. In this paper, we study a new type of Geo-Social K-Cover Group (GSKCG) queries that, given a set of query points and a social network, retrieves a minimum user group in which each user is socially related to at least k other users and the users’ associated regions (e.g., familiar regions or service regions) can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-complete. We consequently explore a set of effective pruning strategies to derive an efficient algorithm for finding the optimal solution. Moreover, we design a novel index structure tailored to our problem to further accelerate query processing. Extensive experiments demonstrate that our algorithm achieves desirable performance on real-life datasets.
Keywords :
Algorithm design and analysis; Collaboration; Indexes; Mobile communication; Silicon; Social factors; Social network services; Location-based services; group queries; query processing; social constraints;
fLanguage :
English
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1041-4347
Type :
jour
DOI :
10.1109/TKDE.2015.2419663
Filename :
7079464
Link To Document :
بازگشت