Geo-Social Group Queries with Minimum Acquaintance Constraint

Abstract

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 $k$NN 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.

This is the preprint version that is accepted by the Very Large Data Bases Journal

References in corpus (1)

• Community detection in graphs

Cited by in corpus (4)

• CS-MLGCN : Multiplex Graph Convolutional Networks for Community Search in Multiplex Networks
• CS-TGN: Community Search via Temporal Graph Neural Networks
• When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks
• Maximizing Friend-Making Likelihood for Social Activity Organization