Spatial consensus queries in a collaborative environment

Mohammed Eunus Ali, Egemen Tanin, Peter Scheuermann, Sarana Nutanong, Lars Kulik

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


We introduce a new type of query for a location-based social network platform. Consider a scenario in which a group of users is trying to find a common meeting location, yet attempting to include all group members is introducing a significant traveling cost to most of them. In this article, we formulate a new query type called the consensus query, which can be used to help users explore these trade-off options to find a solution upon which everyone can agree. Specifically, we study the problem of evaluating consensus queries in the context of nearest neighbor queries, where the group is interested in finding a meeting place that minimizes the travel distance for at least a specified number of group members. To help the group in selecting a suitable solution, the major challenge is to find optimal subgroups of all allowable subgroup sizes, i.e., greater or equal to the minimum specified subgroup size, that minimize the travel distances.We develop incremental algorithms to evaluate in one pass the optimal query subgroups of different sizes along with their corresponding nearest data points. These subsets, which are evaluated by the location-based service provider, constitute the answer set that is returned to the group. The group then collaboratively selects the final answer from the candidate answer set. An extensive experimental study shows the efficiency and effectiveness of our proposed techniques.

Original languageEnglish (US)
Article number3
JournalACM Transactions on Spatial Algorithms and Systems
Issue number1
StatePublished - Mar 2016


  • Consensus queries
  • Group queries
  • Location-based services

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Modeling and Simulation
  • Computer Science Applications
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Spatial consensus queries in a collaborative environment'. Together they form a unique fingerprint.

Cite this