K-Nearest Neighbors on road networks: Euclidean heuristic revisited

Tenindra Abeywickrama, Muhammad Aamir Cheema, David Taniar

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther


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.

Original languageEnglish
Title of host publicationProceedings of the Eleventh International Symposium on Combinatorial Search
EditorsVadim Bulitko, Sabine Storandt
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages2
ISBN (Electronic)9781577358022
Publication statusPublished - 2018
EventInternational Symposium on Combinatorial Search 2018 - Stockholm, Sweden
Duration: 14 Jul 201815 Jul 2018
Conference number: 11th


ConferenceInternational Symposium on Combinatorial Search 2018
Abbreviated titleSOCS 2018
Internet address

Cite this