Efficient kNN Search in Public Transportation Networks

Summary: Introduces a lightweight, path-index-free index for kNN search over public-transit networks, achieving near-optimal query complexity while scaling to large graphs. Experiments show up to 10,000× faster queries and 100× faster construction than prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13739
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,272 | 22.67%
DOI: 10.14778/3681954.3682009

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Qingshuai Feng (University of New South Wales)
2. Junhua Zhang (University of New South Wales)
3. Wenjie Zhang (University of New South Wales)
4. Lu Qin (University of Technology Sydney)
5. Ying Zhang (University of Technology Sydney)
6. Xuemin Lin (Shanghai Jiao Tong University)

BibTeX Citation

@article{feng_vldb24,
        title = {{Efficient kNN Search in Public Transportation Networks}},
        author = {Feng, Qingshuai and Zhang, Junhua and Zhang, Wenjie and Qin, Lu and Zhang, Ying and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {11},
        pages = {3402--3414},
        doi = {10.14778/3681954.3682009},
        url = {https://doi.org/10.14778/3681954.3682009},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
449	Query Processing in Spatial Network Databases	2003	VLDB	0.0001826404
1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010242826
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
2,871	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	8.0110616e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
4,573	TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks	2018	VLDB	6.6226156e-05
5,678	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	6.1246854e-05
5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	6.0183678e-05
7,372	Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand	2021	SIGMOD	5.6312975e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,629	Distance Indexing on Road Networks	2006	VLDB
2	1,251	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
3	1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD
4	10,379	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD
5	4,316	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD
6	665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
7	5,851	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB
8	5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
9	10,460	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
10	8,731	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB