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
8409
Venue
VLDB
Year
1994
Pagerank
0.00021068647
Overall Rank
329 | 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.00052102434
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
1,067 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012327784
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,418 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010835539
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
1,978 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.3627341e-05
1,993 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.3421788e-05
2,046 Distributed Trajectory Similarity Search 2017 VLDB 9.260657e-05
2,774 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 8.1372328e-05
2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.9083221e-05
3,379 Cubetree: Organization of and Bulk Incremental Updates on the Data Cube 1997 SIGMOD 7.4582502e-05
3,593 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.2750277e-05
3,741 Spatial Online Sampling and Aggregation 2016 VLDB 7.1586403e-05
4,569 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.6255507e-05
4,844 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.4826356e-05
5,202 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.3194496e-05
6,079 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.9850223e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
6,459 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.8727182e-05
6,491 Two-dimensional Substring Indexing 2001 PODS 5.8641664e-05
7,070 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.7116663e-05
7,151 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.6873519e-05
7,632 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.5777517e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,580 Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems 2012 VLDB 5.4082911e-05
8,644 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.3934068e-05
8,680 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD 5.3857754e-05
9,234 On Optimal Node Splitting for R-trees 1998 VLDB 5.3017497e-05
9,343 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.2854091e-05
9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.279561e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
9,544 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2528121e-05
9,657 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.2419252e-05
11,332 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 5.093636e-05
11,342 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 5.093636e-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.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
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,032 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012530965
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
Previous Page 1 / 1 Next

Semantically Similar Papers

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