Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks


  • Tenindra Abeywickrama National University of Singapore
  • Muhammad Aamir Cheema Monash University
  • Sabine Storandt University of Konstanz




Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) close to a given location. A k nearest neighbors (kNN) query is one such example that finds k closest POIs from an agent's location. While most existing techniques focus on finding nearby POIs for a single agent, many applications require POIs that are close to multiple agents. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e.g., sum of its distances from each agent). Existing search heuristics are designed for a single agent and do not work well for multiple agents. We propose a novel data structure COLT (Compacted Object-Landmark Tree) to address this gap by enabling efficient hierarchical graph traversal. We then utilize COLT for a wide range of aggregate functions to efficiently answer AkNN queries. In our experiments on real-world and synthetic data sets, our techniques significantly improve query performance, typically outperforming existing approaches by more than an order of magnitude in almost all settings.




How to Cite

Abeywickrama, T., Cheema, M. A., & Storandt, S. (2020). Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1), 2-10. https://doi.org/10.1609/icaps.v30i1.6639