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: 3326
Venue: SIGMOD
Year: 2001
Pagerank: 9.3627341e-05
Overall Rank: 1,978 | 86.44%
DOI: 10.1145/375663.375679

Incoming Non-self Citations Over Time

Authors

1. Kihong Kim (Seoul National University)
2. Sang K. Cha (Seoul National University)
3. Keunjoo Kwon (Seoul National University)

BibTeX Citation

@inproceedings{kim_sigmod01,
        title = {{Optimizing Multidimensional Index Trees for Main Memory Access}},
        author = {Kim, Kihong and Cha, Sang K. and Kwon, Keunjoo},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375679},
        url = {https://dl.acm.org/doi/10.1145/375663.375679},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
932	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.00013119305
1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00012140661
1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.9537123e-05
3,658	P*TIME: Highly Scalable OLTP DBMS for Managing Update-Intensive Stream Workload	2004	VLDB	7.2184172e-05
4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	6.5283833e-05
4,772	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	6.5154736e-05
6,488	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.865078e-05
6,669	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	5.8077717e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	5.3766157e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
8,326	Index Research: Forest or Trees?	2000	SIGMOD	5.4537411e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB
2	9,365	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR
3	42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB
4	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
5	1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
6	12,605	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
7	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
8	67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD
9	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
10	204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB