DBScholar

Back to papers

R-Trees: A Dynamic Index Structure For Spatial Searching

Summary: R-tree, a dynamic index for multidimensional spatial data; supports non-zero sized objects with bounding rectangles. Algorithms for search and update; empirical tests show strong performance and applicability to modern spatial DBs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h52759c68d03cd902
Venue
SIGMOD
Year
1984
Pagerank
0.001992968
Overall Rank
2 | 99.99%
DOI
10.1145/602259.602266

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{guttman_sigmod84,
        title = {{R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING}},
        author = {Guttman, Antonin},
        series = {{SIGMOD} '84},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/602259.602266},
        url = {https://dl.acm.org/doi/10.1145/602259.602266},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 384 citing papers.

Rank Citing Paper Year Venue Pagerank
3,302 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4433382e-05
3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4271038e-05
3,347 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3933163e-05
3,377 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 7.357781e-05
3,442 Cubetree: Organization of and Bulk Incremental Updates on the Data Cube 1997 SIGMOD 7.2979501e-05
3,546 A General and Efficient Querying Method for Learning to Hash 2018 SIGMOD 7.2123214e-05
3,560 Interactive Analysis of Web-Scale Data 2009 CIDR 7.2072209e-05
3,650 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 7.1341771e-05
3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.1125618e-05
3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0277477e-05
3,802 UlTraMan: A Unified Platform for Big Trajectory Data Management and Analytics 2018 VLDB 7.0132896e-05
3,818 Spatial Online Sampling and Aggregation 2016 VLDB 7.0060535e-05
3,829 RE-Tree: An Efficient Index Structure for Regular Expressions 2002 VLDB 6.9972992e-05
3,842 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 6.9896266e-05
3,859 OODB Indexing by Class-Division 1995 SIGMOD 6.9667626e-05
3,910 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.9310405e-05
4,060 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.8250997e-05
4,082 Learning User Preferences By Adaptive Pairwise Comparison 2015 VLDB 6.8176001e-05
4,155 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.7762032e-05
4,346 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.6488514e-05
4,352 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD 6.6423022e-05
4,364 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.6343719e-05
4,430 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.6024228e-05
4,474 Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams 2007 VLDB 6.5838686e-05
4,574 Collective Spatial Keyword Querying 2011 SIGMOD 6.5257688e-05
4,670 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.47772e-05
4,680 Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes 2018 VLDB 6.4722037e-05
4,716 On Indexing Line Segments 1990 VLDB 6.4554004e-05
4,728 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4473669e-05
4,797 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4113285e-05
4,835 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 6.3877419e-05
4,837 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 6.3872905e-05
4,850 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3808017e-05
4,856 Neighbor-Sensitive Hashing 2016 VLDB 6.3798143e-05
4,869 Durable Top-k Search in Document Archives 2010 SIGMOD 6.3739434e-05
4,885 Design Tradeoffs of Data Access Methods 2016 SIGMOD 6.3706825e-05
4,927 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3503189e-05
4,956 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.340462e-05
4,983 Indexing Large Human-Motion Databases 2004 VLDB 6.3269506e-05
4,986 Indexing for Interactive Exploration of Big Data Series 2014 SIGMOD 6.3264608e-05
5,023 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.3096704e-05
5,062 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2910498e-05
5,166 LightDB: A DBMS for Virtual Reality Video 2018 VLDB 6.2463315e-05
5,170 Toward Practical Constraint Databases 1993 VLDB 6.2448851e-05
5,218 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2231041e-05
5,282 High-Performance Extensible Indexing 1999 VLDB 6.1988765e-05
5,292 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.1924532e-05
5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1778312e-05
5,342 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1725496e-05
5,411 GTS: GPU-based Tree Index for Fast Similarity Search 2024 SIGMOD 6.1408042e-05
Previous Page 4 / 8 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032170066
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,421 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
2 90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB
3 146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
4 1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 7,904 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS
6 3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD
7 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
8 116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD
9 10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
10 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB