k-Nearest Neighbors on Road Networks: Euclidean Heuristic Revisited

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Abstracts

In the age of smartphones, finding the nearest points of interest (POIs) is a highly relevant problem. A popular way to solve this is to use a k Nearest Neighbor (kNN) query to retrieve POIs by their road network distances from a query location. However, we find that existing kNN methods have not been carefully compared. We present a detailed and fair experimental study of the state-of-the-art, documenting the many insights gleaned along the way. Notably, a long overlooked Euclidean distance heuristic is often the best performing method by a wide margin. We have also released all code as open-source for readers to reproduce experiments and easily add methods or queries to the testbed for new studies.

10.1609/socs.v9i1.18443