Proceedings

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

Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

Download BibTeX Cite

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

Keywords

  • Multidisciplinary Topics and Applications: Transportation
  • Data Mining: Big Data, Large-Scale Systems
  • Heuristic Search and Game Playing: Heuristic Search

Abstract

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.

Tenindra Abeywickrama, Muhammad Aamir Cheema, and Sabine Storandt. 2021. Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract). In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4730–4734. https://doi.org/10.24963/ijcai.2021/640
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards