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.0002058961
Overall Rank
338 | 97.74%
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.00051134355
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
843 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013501136
1,084 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012086348
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,445 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010607118
1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010103178
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,884 Effectively Learning Spatial Indices 2020 VLDB 9.422145e-05
2,007 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.182637e-05
2,029 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1470713e-05
2,035 Distributed Trajectory Similarity Search 2017 VLDB 9.1372983e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7045269e-05
3,454 Cubetree: Organization of and Bulk Incremental Updates on the Data Cube 1997 SIGMOD 7.270801e-05
3,678 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.0857938e-05
3,825 Spatial Online Sampling and Aggregation 2016 VLDB 6.9795872e-05
4,685 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.4533027e-05
4,980 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.3167773e-05
5,350 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1545256e-05
6,221 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.8286278e-05
6,427 External Memory Algorithms 1998 PODS 5.7713075e-05
6,604 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7196547e-05
6,631 Two-dimensional Substring Indexing 2001 PODS 5.7114931e-05
7,236 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.5629185e-05
7,324 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5387994e-05
7,811 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.432001e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
8,644 Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems 2012 VLDB 5.2822865e-05
8,829 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2533436e-05
8,834 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2524856e-05
8,877 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD 5.2450451e-05
9,441 On Optimal Node Splitting for R-trees 1998 VLDB 5.163285e-05
9,560 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1473114e-05
9,579 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.141601e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-05
9,875 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1049486e-05
11,703 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 4.9605343e-05
11,712 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 4.9605343e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
102 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033850505
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019931086
1,060 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012222117
1,145 Optimization Strategies for Spatial Query Processing 1991 VLDB 0.00011800785
1,231 Fractals for Secondary Key Retrieval 1989 PODS 0.0001140916
2,818 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 7.9536217e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,412 A Model for the Prediction of R-tree Performance 1996 PODS
2 7,324 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
3 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB
4 5,350 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB
5 3,678 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
6 1,231 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,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
9 3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
10 9,441 On Optimal Node Splitting for R-trees 1998 VLDB