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: hc48ee67cbd61add8
Venue: VLDB
Year: 2011
Pagerank: 5.2036709e-05
Overall Rank: 9,280 | 37.61%
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,263	The Flexible Socio Spatial Group Queries	2019	VLDB	5.8323838e-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.0011405675
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
1,048	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012303367
1,304	Continuous Nearest Neighbor Search	2002	VLDB	0.00011104243
1,652	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	9.9778734e-05
2,194	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	8.8805644e-05
2,681	Distance Indexing on Road Networks	2006	VLDB	8.142964e-05
9,313	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.1961681e-05

Semantically Similar Papers

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