---
title: "Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract)"
authors:
  - "Tenindra Abeywickrama"
  - "Muhammad Aamir Cheema"
  - "Sabine Storandt"
doi: "10.24963/ijcai.2021/640"
url: "https://ijcai.org/proceedings/2021/640"
pdf: "https://ijcai.org/proceedings/2021/0640.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4730-4734"
track: "Sister Conferences Best Papers"
keywords:
  - "Multidisciplinary Topics and Applications: Transportation"
  - "Data Mining: Big Data, Large-Scale Systems"
  - "Heuristic Search and Game Playing: Heuristic Search"
---

# 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*, pages 4730-4734. DOI: [10.24963/ijcai.2021/640](https://doi.org/10.24963/ijcai.2021/640)

## 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.