Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract)

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract)

Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Sister Conferences Best Papers. Pages 4730-4734. https://doi.org/10.24963/ijcai.2021/640

A k nearest neighbors (kNN) query finds k closest points-of-interest (POIs) from an agent's location. 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). We propose a novel data structure COLT (Compacted Object-Landmark Tree) which enables efficient hierarchical graph traversal and utilize it to efficiently answer AkNN queries. Our experiments on real-world and synthetic data sets show that our techniques outperform existing approaches by more than an order of magnitude in almost all settings.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Multidisciplinary Topics and Applications: Transportation
Data Mining: Big Data, Large-Scale Systems