Optimizing Multidimensional Index Trees for Main Memory Access

Summary: CR-tree, a cache-conscious R-tree variant for main memory, compresses MBR keys to increase fanout. Relative-to-parent coordinates and fixed-bit quantization create wider, smaller nodes, yielding up to 2.5× faster 2D searches with ~60% less memory and similar updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3265
Venue: SIGMOD
Year: 2001
Pagerank: 9.8561164e-05
Overall Rank: 1,987 | 86.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
1,046	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00014446882
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013404419
2,233	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.2299873e-05
3,890	P*TIME: Highly Scalable OLTP DBMS for Managing Update-Intensive Stream Workload	2004	VLDB	6.6552177e-05
4,741	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	5.951386e-05
5,226	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	5.6164816e-05
6,534	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.018905e-05
6,851	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	4.9031078e-05
8,354	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5329424e-05
8,559	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	4.4893996e-05
8,572	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4885798e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
104	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049475932
124	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.0004501099
240	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031526134
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
7,779	Index Research: Forest or Trees?	2000	SIGMOD	4.6490763e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
235	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00031980259
9,209	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR	4.3691119e-05
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
9,168	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.380727e-05
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013404419
12,420	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1905499e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
104	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049475932
1,807	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.0001047644
240	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031526134