2014/06/28 by Qijun Zhu, Zhu, Qijun, Haibo Hu +7 · 1 citation
Computer Science · Social Sciences · #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Geographic Information Systems Studies #Human Mobility and Location-Based Analysis #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1406.7367
openalex publication_date 2014/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The prosperity of location-based social networking services enables geo-social group queries for group-based activity planning and marketing. This paper proposes a new family of geo-social group queries with minimum acquaintance constraint (GSGQs), which are more appealing than existing geo-social group queries in terms of producing a cohesive group that guarantees the worst-case acquaintance level. GSGQs, also specified with various spatial constraints, are more complex than conventional spatial queries; particularly, those with a strict kNN spatial constraint are proved to be NP-hard. For efficient processing of general GSGQ queries on large location-based social networks, we devise two social-aware index structures, namely SaR-tree and SaR*-tree. The latter features a novel clustering technique that considers both spatial and social factors. Based on SaR-tree and SaR*-tree, efficient algorithms are developed to process various GSGQs. Extensive experiments on real-world Gowalla and Dianping datasets show that our proposed methods substantially outperform the baseline algorithms based on R-tree.