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: hbb21cb2b8019b38f
Venue: SIGMOD
Year: 1992
Pagerank: 8.5375939e-05
Overall Rank: 2,388 | 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
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
6,145	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.8717297e-05
6,418	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.7907247e-05
6,663	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.7166181e-05
7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5598057e-05
7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4295914e-05
9,597	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	5.1557462e-05
10,666	P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction	2026	SIGMOD	4.9793485e-05
11,115	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.9793485e-05
13,358	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
54	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040499302
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019976696
1,144	Optimization Strategies for Spatial Query Processing	1991	VLDB	0.00011842581
1,226	Fractals for Secondary Key Retrieval	1989	PODS	0.00011431306
2,828	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	7.9650643e-05
5,234	Multi-Disk B-trees	1991	SIGMOD	6.217296e-05

Semantically Similar Papers

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