Processing Proximity Relations in Road Networks

Summary: Defines three proximity relations to model queries on moving objects in road networks. Introduces a moving-object index and road-network partitioning that confines computation to a partial road network, yielding >95% overhead reduction and ~20× speedup vs baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4310
Venue: SIGMOD
Year: 2010
Pagerank: 5.3153925e-05
Overall Rank: 9,143 | 37.28%
DOI: 10.1145/1807167.1807196

Incoming Non-self Citations Over Time

Authors

1. Zhengdao Xu (University of Toronto)
2. Hans-Arno Jacobsen (University of Toronto)

BibTeX Citation

@inproceedings{xu_sigmod10,
        title = {{Processing Proximity Relations in Road Networks}},
        author = {Xu, Zhengdao and Jacobsen, Hans-Arno},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807196},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807196},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,111	Efficient Algorithms for Finding Optimal Meeting Point on Road Networks	2011	VLDB	5.3221578e-05
10,102	Distributed Stream KNN Join	2021	SIGMOD	5.1488731e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
441	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018407547
449	Query Processing in Spatial Network Databases	2003	VLDB	0.0001826404
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
968	Path Oracles for Spatial Networks	2009	VLDB	0.00012901559
1,025	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012578515
1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010206305
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9591376e-05
2,629	Distance Indexing on Road Networks	2006	VLDB	8.3265243e-05
3,637	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.2339626e-05
8,787	Adaptive Location Constraint Processing	2007	SIGMOD	5.3729697e-05
13,909	Efficient Constraint Processing for Highly Personalized Location Based Services	2004	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,851	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB
2	10,379	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD
3	1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
4	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
5	949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
6	1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB
7	6,683	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD
8	8,787	Adaptive Location Constraint Processing	2007	SIGMOD
9	5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
10	10,460	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD