ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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}
}

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AS91]
Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BB82]
...
[Ben75]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bia69]
T. Bially: Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory 15(6): 658-664(1969) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fal88]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FR89]
Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre87]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gar82]
Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra92]
...
[Gre89]
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gri86]
J. G. Griffiths: An Algorithm for Displaying a Class of Space-filling Curves. Softw., Pract. Exper. 16(5): 403-411(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gun89]
Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84a]
Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84b]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HN83]
Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jag90a]
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jag90b]
H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KF93]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS91]
Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Man77]
...
[OHM+84]
...
[Ore86]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RL85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rob81]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sam89]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SSU91]
Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities. Commun. ACM 34(10): 110-120(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Whi81]
...

Copyright © Fri Mar 12 17:22:53 2010 by Michael Ley (ley@uni-trier.de)