Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree

Summary: Challenges R*-tree dominance for low-to-medium dimensional point indexing, showing Quadtree’s regular, disjoint decomposition dramatically reduces MBR overlap and yields structural/search advantages. Analytical models and extensive experiments show quadtrees (despite being unbalanced) improve buffer-pool utilization and outperform R*-trees and the Pyramid technique on point workloads, motivating their reconsideration. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc592e3dfcd4fc9d1
Venue: CIDR
Year: 2007
Pagerank: 5.1611019e-05
Overall Rank: 9,544 | 35.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. You Jung Kim (University of Michigan)
2. Jignesh M. Patel (University of Michigan)

BibTeX Citation

@inproceedings{kim_cidr07,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '07},
        title = {{Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Kim, You Jung and Patel, Jignesh M.},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,788	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.4526034e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
302	Shoring Up Persistent Applications	1994	SIGMOD	0.0002167061
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001325914
1,142	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00011848523
3,182	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.561954e-05
3,253	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.4900624e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
2	886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD
3	9,400	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB
4	2,828	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
5	13,108	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB
6	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
7	597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
8	10,048	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
9	90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB
10	44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB