Hierarchical Graph Traversal for Aggregate K Nearest Neighbors Search in Road Networks (Extended Abstract)
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.
Cite
Text
Abeywickrama et al. "Hierarchical Graph Traversal for Aggregate K Nearest Neighbors Search in Road Networks (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/640Markdown
[Abeywickrama et al. "Hierarchical Graph Traversal for Aggregate K Nearest Neighbors Search in Road Networks (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/abeywickrama2021ijcai-hierarchical/) doi:10.24963/IJCAI.2021/640BibTeX
@inproceedings{abeywickrama2021ijcai-hierarchical,
title = {{Hierarchical Graph Traversal for Aggregate K Nearest Neighbors Search in Road Networks (Extended Abstract)}},
author = {Abeywickrama, Tenindra and Cheema, Muhammad Aamir and Storandt, Sabine},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {4730-4734},
doi = {10.24963/IJCAI.2021/640},
url = {https://mlanthology.org/ijcai/2021/abeywickrama2021ijcai-hierarchical/}
}