Parallel R-trees

Summary: Proposes a multiplexed R-tree across multiple disks on a single server to maximize range-query throughput. Uses a proximity index (PI) heuristic to place new nodes, outperforming Round Robin and Super-node with near-linear speedup and reduced I/O. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2649
Venue: SIGMOD
Year: 1992
Pagerank: 8.7233426e-05
Overall Rank: 2,341 | 83.95%
DOI: 10.1145/130283.130315

Incoming Non-self Citations Over Time

Authors

1. Ibrahim Kamel (University of Maryland)
2. Christos Faloutsos (University of Maryland)

BibTeX Citation

@inproceedings{kamel_sigmod92,
        title = {{Parallel R-trees}},
        author = {Kamel, Ibrahim and Faloutsos, Christos},
        series = {{SIGMOD} '92},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/130283.130315},
        url = {https://dl.acm.org/doi/10.1145/130283.130315},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
6,025	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	6.002739e-05
6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.9227722e-05
6,537	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.8478276e-05
7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.6873519e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	5.2740525e-05
10,479	P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction	2026	SIGMOD	5.093636e-05
10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD	5.093636e-05
13,068	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
1,125	Optimization Strategies for Spatial Query Processing	1991	VLDB	0.0001208101
1,202	Fractals for Secondary Key Retrieval	1989	PODS	0.00011672157
2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.1356669e-05
5,120	Multi-Disk B-trees	1991	SIGMOD	6.3577476e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
2	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
3	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
4	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
5	3,057	High-Concurrency Locking in R-Trees	1995	VLDB
6	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
7	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
8	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD
10	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB