@article{Abeywickrama_Cheema_Storandt_2020, title={Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks}, volume={30}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/6639}, DOI={10.1609/icaps.v30i1.6639}, abstractNote={<p>Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) close to a given location. A <em>k</em> nearest neighbors (<em>k</em>NN) query is one such example that finds <em>k</em> 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 <em>multiple</em> agents. In this paper, we study a natural extension of the <em>k</em>NN query for multiple agents, namely, the Aggregate <em>k</em> Nearest Neighbors (A<em>k</em>NN) query. An A<em>k</em>NN query retrieves <em>k</em> 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 A<em>k</em>NN 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.</p>}, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Abeywickrama, Tenindra and Cheema, Muhammad Aamir and Storandt, Sabine}, year={2020}, month={Jun.}, pages={2-10} }