The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

Summary: Introduces the Priority R-tree (PR-tree), the first R-tree variant that guarantees worst-case optimal window-query I/Os: O((N/B)^(1-1/d) + T/B). Establishes asymptotic optimality and demonstrates practical gains over existing R-trees, excelling on extreme data via extensive real and synthetic experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7de6a505f656dac2
Venue: SIGMOD
Year: 2004
Pagerank: 7.1125618e-05
Overall Rank: 3,669 | 75.34%
DOI: 10.1145/1007568.1007608

Incoming Non-self Citations Over Time

Authors

1. Lars Arge (Duke University)
2. Mark de Berg (Eindhoven University of Technology)
3. Herman J. Haverkort (Utrecht University)
4. Ke Yi (Duke University)

BibTeX Citation

@inproceedings{arge_sigmod04,
        title = {{The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree}},
        author = {Arge, Lars and de Berg, Mark and Haverkort, Herman J. and Yi, Ke},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007608},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007608},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,774	ArrayStore: A Storage Manager for Complex Parallel Array Processing	2011	SIGMOD	9.6688719e-05
3,034	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.7330662e-05
4,956	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.340462e-05
6,663	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.7166181e-05
7,788	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.4526034e-05
8,369	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3450708e-05
12,618	Measuring Two-Event Structural Correlations on Graphs	2012	VLDB	4.9793485e-05
12,779	Worst-Case Efficient Range Search Indexing	2009	PODS	4.9793485e-05
12,980	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
743	Client-Server Paradise	1994	VLDB	0.00014311524

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,895	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
2	985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB
3	3,034	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
4	1,405	A Model for the Prediction of R-tree Performance	1996	PODS
5	2,388	Parallel R-trees	1992	SIGMOD
6	1,861	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
7	9,406	On Optimal Node Splitting for R-trees	1998	VLDB
8	12,779	Worst-Case Efficient Range Search Indexing	2009	PODS
9	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
10	7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB