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

Authors

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

DOI:

https://doi.org/10.1609/icaps.v30i1.6639

Abstract

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.

Downloads

Published

2020-06-01

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