# Geo-Social Group Queries with Minimum Acquaintance Constraint

arXiv: https://arxiv.org/abs/1406.7367 · HTML: https://mlsanity.com/paper/1406.7367/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2014.

## Built on by (most cited first, 3 of 3)

- [CS-MLGCN : Multiplex Graph Convolutional Networks for Community Search in Multiplex Networks](https://mlsanity.com/paper/2210.08811/) (2022)
- [CS-TGN: Community Search via Temporal Graph Neural Networks](https://mlsanity.com/paper/2303.08964/) (2023)
- [An Effective Index for Truss-based Community Search on Large Directed Graphs](https://mlsanity.com/paper/2401.10641/) (2024)

## Abstract (arXiv)

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.