DBScholar

Back to papers

Hilbert R-tree: An Improved R-tree Using Fractals

Summary: Introduces the Hilbert R-tree, ordering rectangles by Hilbert values of their centers to enable deferred splitting and controllable high space utilization. A 2-to-3 split policy balances insertion and search costs, achieving up to 28% savings over R*-trees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h4b75df320359b8a6
Venue
VLDB
Year
1994
Pagerank
0.00020660268
Overall Rank
335 | 97.75%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{kamel_vldb94,
        title = {{Hilbert R-tree: An Improved R-tree Using Fractals}},
        author = {Kamel, Ibrahim and Faloutsos, Christos},
        journal = {PVLDB},
        series = {{VLDB} '94},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
1,080 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012131978
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,446 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010629222
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,878 Effectively Learning Spatial Indices 2020 VLDB 9.4451309e-05
1,996 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.216723e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,021 Distributed Trajectory Similarity Search 2017 VLDB 9.1719539e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.967335e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,442 Cubetree: Organization of and Bulk Incremental Updates on the Data Cube 1997 SIGMOD 7.2979501e-05
3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.1125618e-05
3,818 Spatial Online Sampling and Aggregation 2016 VLDB 7.0060535e-05
4,670 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.47772e-05
4,956 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.340462e-05
5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1778312e-05
6,203 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.8507344e-05
6,413 External Memory Algorithms 1998 PODS 5.7931958e-05
6,595 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7413481e-05
6,616 Two-dimensional Substring Indexing 2001 PODS 5.7330951e-05
7,215 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.5837763e-05
7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5598057e-05
7,788 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.4526034e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,619 Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems 2012 VLDB 5.3016441e-05
8,804 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2732683e-05
8,809 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2724071e-05
8,845 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD 5.2649359e-05
9,406 On Optimal Node Splitting for R-trees 1998 VLDB 5.1828502e-05
9,522 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1668323e-05
9,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.1611019e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
9,833 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1243105e-05
11,650 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 4.9793485e-05
11,660 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

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.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
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,055 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012266704
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
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,405 A Model for the Prediction of R-tree Performance 1996 PODS
2 7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
3 5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB
4 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB
5 3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
6 1,226 Fractals for Secondary Key Retrieval 1989 PODS
7 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
8 1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
9 3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
10 9,406 On Optimal Node Splitting for R-trees 1998 VLDB