Hierarchical graph traversal for aggregate k nearest neighbors search in road networks

Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Conference on Automated Planning and Scheduling
EditorsJ. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781577358244
Publication statusPublished - 2020
EventInternational Conference on Automated Planning and Scheduling 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020
Conference number: 30th
https://aaai.org/ojs/index.php/ICAPS/issue/view/263 (Proceedings)
https://dblp.org/db/conf/aips/icaps2020.html (Proceedings on dblp)
https://icaps20.icaps-conference.org (Website)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherThe AAAI Press
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843


ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
Internet address

Cite this