TY - JOUR
T1 - Geo-Social K-Cover Group Queries for Collaborative Spatial Computing
AU - Li, Yafei
AU - Chen, Rui
AU - Xu, Jianliang
AU - Huang, Qiao
AU - Hu, Haibo
AU - Choi, Byron
N1 - This work was supported by the Research Grants Council of Hong Kong under Project Nos. HKBU211512 and
HKBU12200114.
PY - 2015/10/1
Y1 - 2015/10/1
N2 - 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.
AB - 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.
KW - group queries
KW - Location-based services
KW - query processing
KW - social constraints
UR - http://www.scopus.com/inward/record.url?scp=84941551685&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2015.2419663
DO - 10.1109/TKDE.2015.2419663
M3 - Journal article
AN - SCOPUS:84941551685
SN - 1041-4347
VL - 27
SP - 2729
EP - 2742
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 10
M1 - 7079464
ER -