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: 3264
Venue: SIGMOD
Year: 2001
Pagerank: 9.8638201e-05
Overall Rank: 1,983 | 86.21%
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.00026768139
1,050	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00014453896
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013406526
2,244	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.2097912e-05
3,895	P*TIME: Highly Scalable OLTP DBMS for Managing Update-Intensive Stream Workload	2004	VLDB	6.6581873e-05
4,746	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	5.9571146e-05
5,219	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	5.6217069e-05
6,537	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.0235647e-05
6,852	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	4.9078179e-05
8,359	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5372925e-05
8,562	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	4.4937074e-05
8,575	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4928872e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
124	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00045103515
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
7,779	Index Research: Forest or Trees?	2000	SIGMOD	4.6535251e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526
9,207	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR	4.3733038e-05
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
9,258	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.3690661e-05
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013406526
12,411	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1945683e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425