Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks

Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

 PosterID: 52
picture_as_pdf PDF
library_books Slides
library_books Poster
menu_book BibTeX
Location-based services heavily rely on efficient methods that search 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 on almost all settings.

Session Aus2: Search
Canb 10/28/2020, 20:00 – 21:00
10/30/2020, 13:00 – 14:00
Paris 10/28/2020, 10:00 – 11:00
10/30/2020, 03:00 – 04:00
NYC 10/28/2020, 05:00 – 06:00
10/29/2020, 22:00 – 23:00
LA 10/28/2020, 02:00 – 03:00
10/29/2020, 19:00 – 20:00
Contact: icaps20-support (at) googlegroups.com
Copyright ©2020 by ICAPS.