k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation

Summary: In-memory evaluation of kNN on road networks, comparing network distance with Euclidean proxies and reproducing state-of-the-art methods fairly. Revisits the discarded IER approach with a simple improvement, often achieving the best performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h9a4c46cdf2b9680c
Venue: VLDB
Year: 2016
Pagerank: 5.9325005e-05
Overall Rank: 5,966 | 59.89%
DOI: 10.14778/2850583.2850592

Incoming Non-self Citations Over Time

Authors

1. Tenindra Abeywickrama (Monash University)
2. Muhammad Aamir Cheema (Monash University)
3. David Taniar (Monash University)

BibTeX Citation

@article{abeywickrama_vldb16,
        title = {{k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation}},
        author = {Abeywickrama, Tenindra and Cheema, Muhammad Aamir and Taniar, David},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {6},
        pages = {492--503},
        doi = {10.14778/2850583.2850592},
        url = {https://doi.org/10.14778/2850583.2850592},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,674	TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks	2018	VLDB	6.4750983e-05
8,629	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2994494e-05
9,400	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	5.1845732e-05
9,407	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.1828314e-05
10,246	VIP-Tree: An Effective Index for Indoor Spatial Queries	2017	VLDB	5.0525742e-05
11,551	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	4.9793485e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018159715
458	Query Processing in Spatial Network Databases	2003	VLDB	0.00017868943
677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014843441
953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012877507
1,048	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012303367
2,681	Distance Indexing on Road Networks	2006	VLDB	8.142964e-05
6,797	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	5.6798855e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,681	Distance Indexing on Road Networks	2006	VLDB
2	447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
3	953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
4	11,600	Efficient kNN Search in Public Transportation Networks	2024	VLDB
5	677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
6	2,194	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD
7	10,647	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
8	6,107	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
9	1,652	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB
10	8,895	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB