Hilbert R-tree: An Improved R-tree using Fractals.
Ibrahim Kamel, Christos Faloutsos:
Hilbert R-tree: An Improved R-tree using Fractals.
VLDB 1994: 500-509@inproceedings{DBLP:conf/vldb/KamelF94,
author = {Ibrahim Kamel and
Christos Faloutsos},
editor = {Jorge B. Bocca and
Matthias Jarke and
Carlo Zaniolo},
title = {Hilbert R-tree: An Improved R-tree using Fractals},
booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
publisher = {Morgan Kaufmann},
year = {1994},
isbn = {1-55860-153-8},
pages = {500-509},
ee = {db/conf/vldb/vldb94-500.html},
crossref = {DBLP:conf/vldb/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
We propose a new R-tree structure that outperforms all the older ones.
The heart of the idea is to facilitate the deferred splitting approach
in R-trees. This is done by proposing an ordering on the R-tree
nodes. This ordering has to be `good', in the sense that it should
group `similar' data rectangles together, to minimize the area and
perimeter of the resulting minimum bounding rectangles (MBRs).
Following [Kamel93] we have chosen the so-called `2D-c' method, which
sorts rectangles according to the Hilbert value of the center of the
rectangles. Given the ordering, every node has a well-defined set of
sibling nodes; thus, we can use deferred splitting. By adjusting the
split policy, the Hilbert R-tree can achieve as high utilization as
desired. To the contrary, the R*-tree has no control over the space
utilization, typically achieving up to 70%. We designed the
manipulation algorithms in detail, and we did a full implementation of
the Hilbert R-tree. Our experiments show that the `2-to-3' split
policy provides a compromise between the insertion complexity and the
search cost, giving up to 28% savings over the R*-tree [Beckmann90] on
real data.
Copyright © 1994 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.):
VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile.
Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX
References
- [AS91]
- Walid G. Aref, Hanan Samet:
Optimization for Spatial Query Processing.
VLDB 1991: 81-90 BibTeX
- [BB82]
- ...
- [Ben75]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975) BibTeX
- [Bia69]
- T. Bially:
Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction.
IEEE Transactions on Information Theory 15(6): 658-664(1969) BibTeX
- [BKSS90]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331 BibTeX
- [Fal88]
- Christos Faloutsos:
Gray Codes for Partial Match and Range Queries.
IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
- [FR89]
- Christos Faloutsos, Shari Roseman:
Fractals for Secondary Key Retrieval.
PODS 1989: 247-252 BibTeX
- [Fre87]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269 BibTeX
- [Gar82]
- Irene Gargantini:
An Effective Way to Represent Quadtrees.
Commun. ACM 25(12): 905-910(1982) BibTeX
- [Gra92]
- ...
- [Gre89]
- Diane Greene:
An Implementation and Performance Analysis of Spatial Data Access Methods.
ICDE 1989: 606-615 BibTeX
- [Gri86]
- J. G. Griffiths:
An Algorithm for Displaying a Class of Space-filling Curves.
Softw., Pract. Exper. 16(5): 403-411(1986) BibTeX
- [Gun89]
- Oliver Günther:
The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases.
ICDE 1989: 598-605 BibTeX
- [Gut84a]
- Antonin Guttman:
New Features for Relational Database Systems to Support CAD Applications.
Ph.D. thesis, University of California, Berkeley 1984
BibTeX
- [Gut84b]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [HN83]
- Klaus Hinrichs, Jürg Nievergelt:
The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects.
WG 1983: 100-113 BibTeX
- [Jag90a]
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319 BibTeX
- [Jag90b]
- H. V. Jagadish:
Linear Clustering of Objects with Multiple Atributes.
SIGMOD Conference 1990: 332-342 BibTeX
- [KF93]
- Ibrahim Kamel, Christos Faloutsos:
On Packing R-trees.
CIKM 1993: 490-499 BibTeX
- [KS91]
- Curtis P. Kolovson, Michael Stonebraker:
Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data.
SIGMOD Conference 1991: 138-147 BibTeX
- [LS90]
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
- [Man77]
- ...
- [OHM+84]
- ...
- [Ore86]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336 BibTeX
- [RL85]
- Nick Roussopoulos, Daniel Leifker:
Direct Spatial Search on Pictorial Databases Using Packed R-Trees.
SIGMOD Conference 1985: 17-31 BibTeX
- [Rob81]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18 BibTeX
- [Sam89]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
BibTeX
- [SRF87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518 BibTeX
- [SSU91]
- Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman:
Database Systems: Achievements and Opportunities.
Commun. ACM 34(10): 110-120(1991) BibTeX
- [Whi81]
- ...
Referenced by
- Gísli R. Hjaltason, Hanan Samet:
Distance Browsing in Spatial Databases.
ACM Trans. Database Syst. 24(2): 265-318(1999)
- Botao Wang, Hiroyuki Horinokuchi, Kunihiko Kaneko, Akifumi Makinouchi:
Parallel R-Tree Search Algorithm on DSVM.
DASFAA 1999: 237-245
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Yván J. García, Mario A. Lopez, Scott T. Leutenegger:
On Optimal Node Splitting for R-trees.
VLDB 1998: 334-344
- Rasa Bliujute, Christian S. Jensen, Simonas Saltenis, Giedrius Slivinskas:
R-Tree Based Indexing of Now-Relative Bitemporal Data.
VLDB 1998: 345-356
- Apostolos Papadopoulos, Yannis Manolopoulos:
Similarity Query Processing Using Disk Arrays.
SIGMOD Conference 1998: 225-236
- Jeffrey Scott Vitter:
External Memory Algorithms.
PODS 1998: 119-128
- Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter:
Efficient Searching with Linear Constraints.
PODS 1998: 169-178
- Scott T. Leutenegger, Mario A. Lopez:
The Effect of Buffering on the Performance of R-Trees.
ICDE 1998: 164-171
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations.
EDBT 1998: 216-230
- Shashi Shekhar, Duen-Ren Liu:
CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations.
IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
- Euripides G. M. Petrakis, Christos Faloutsos:
Similarity Searching in Medical Image Databases.
IEEE Trans. Knowl. Data Eng. 9(3): 435-447(1997)
- Viswanath Poosala, Yannis E. Ioannidis:
Selectivity Estimation Without the Attribute Value Independence Assumption.
VLDB 1997: 486-495
- Nick Roussopoulos, Yannis Kotidis, Mema Roussopoulos:
Cubetree: Organization of and Bulk Updates on the Data Cube.
SIGMOD Conference 1997: 89-99
- Apostolos Papadopoulos, Yannis Manolopoulos:
Performance of Nearest Neighbor Queries in R-Trees.
ICDT 1997: 394-408
- Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez:
STR: A Simple and Efficient Algorithm for R-Tree Packing.
ICDE 1997: 497-506
- Kenneth C. Sevcik, Nick Koudas:
Filter Trees for Managing Spatial Data over a Range of Size Granularities.
VLDB 1996: 16-27
- Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast Nearest Neighbor Search in Medical Image Databases.
VLDB 1996: 215-226
- Yannis Theodoridis, Timos K. Sellis:
A Model for the Prediction of R-tree Performance.
PODS 1996: 161-171
- Nick Koudas, Christos Faloutsos, Ibrahim Kamel:
Declustering Spatial Databases on a Multi-Computer Architecture.
EDBT 1996: 592-614
- Christos Faloutsos:
Fast Searching by Content in Multimedia Databases.
IEEE Data Eng. Bull. 18(4): 31-40(1995)
- Alberto Belussi, Christos Faloutsos:
Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension.
VLDB 1995: 299-310
- Nick Roussopoulos, Stephen Kelley, Frédéic Vincent:
Nearest Neighbor Queries.
SIGMOD Conference 1995: 71-79
- Christos Faloutsos, King-Ip Lin:
FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets.
SIGMOD Conference 1995: 163-174
- King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB J. 3(4): 517-542(1994)
- Christos Faloutsos, Ibrahim Kamel:
High Performance R-trees.
IEEE Data Eng. Bull. 16(3): 28-33(1993)
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:59 2009