Efficient Algorithms for Finding Optimal Meeting Point on Road Networks

Summary: Baseline OMP for road networks: shrink search from |Q|·|E| to |V|+|Q|; adds two pruning methods. Introduces a high-quality near-optimal algorithm for rapid, large-query workloads—orders of magnitude faster than exact OMP; confirmed by extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10516
Venue: VLDB
Year: 2011
Pagerank: 5.3221578e-05
Overall Rank: 9,111 | 37.50%
DOI: 10.14778/3402707.3402715

Incoming Non-self Citations Over Time

Authors

1. Da Yan (Hong Kong University of Science and Technology)
2. Zhou Zhao (Hong Kong University of Science and Technology)
3. Wilfred Ng (Hong Kong University of Science and Technology)

BibTeX Citation

@article{yan_vldb11,
        title = {{Efficient Algorithms for Finding Optimal Meeting Point on Road Networks}},
        author = {Yan, Da and Zhao, Zhou and Ng, Wilfred},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {968--979},
        doi = {10.14778/3402707.3402715},
        url = {https://doi.org/10.14778/3402707.3402715},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,251	The Flexible Socio Spatial Group Queries	2019	VLDB	5.9415675e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
449	Query Processing in Spatial Network Databases	2003	VLDB	0.0001826404
665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00015167291
1,025	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012578515
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010206305
2,153	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	9.0762376e-05
2,629	Distance Indexing on Road Networks	2006	VLDB	8.3265243e-05
9,143	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.3153925e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,602	Clustering Objects on a Spatial Network	2004	SIGMOD
2	11,401	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD
3	10,460	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
4	3,817	Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach	2007	VLDB
5	5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
6	1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
7	949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
8	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
9	4,807	Diversified Top-k Route Planning in Road Network	2022	VLDB
10	6,683	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD