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: 86
Venue: CIDR
Year: 2007
Pagerank: 5.279561e-05
Overall Rank: 9,365 | 35.75%
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,632	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.5777517e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
299	Shoring Up Persistent Applications	1994	SIGMOD	0.00022084669
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013522522
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
3,125	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.7344198e-05
3,217	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.6314544e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
2	864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD
3	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
4	9,334	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB
5	12,818	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	592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
8	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
9	85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB
10	42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB