Geo-Social K-Cover Group Queries for Collaborative Spatial Computing

Yafei Li, Rui CHEN, Jianliang XU, Qiao Huang, Haibo HU, Koon Kau CHOI

Research output: Contribution to journalJournal articlepeer-review

32 Citations (Scopus)


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.

Original languageEnglish
Article number7079464
Pages (from-to)2729-2742
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number10
Publication statusPublished - 1 Oct 2015

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • group queries
  • Location-based services
  • query processing
  • social constraints


Dive into the research topics of 'Geo-Social K-Cover Group Queries for Collaborative Spatial Computing'. Together they form a unique fingerprint.

Cite this