AAAI Publications, Eleventh Annual Symposium on Combinatorial Search

Font Size: 
k-Nearest Neighbors on Road Networks: Euclidean Heuristic Revisited
Tenindra Abeywickrama, Muhammad Aamir Cheema, David Taniar

Last modified: 2018-07-02


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.

Full Text: PDF