ACM SIGMOD Anthology VLDB dblp.uni-trier.de

On Optimal Node Splitting for R-trees.

Yván J. García, Mario A. Lopez, Scott T. Leutenegger: On Optimal Node Splitting for R-trees. VLDB 1998: 334-344
@inproceedings{DBLP:conf/vldb/GarciaLL98,
  author    = {Yv{\'a}n J. Garc\'{\i}a and
               Mario A. Lopez and
               Scott T. Leutenegger},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {On Optimal Node Splitting for R-trees},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {334-344},
  ee        = {db/conf/vldb/GarciaLL98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem of finding an optimal bipartition of a rectangle set has a direct impact on query performance of dynamic R-trees. During update operations, overflowed nodes need to be split (bipartitioned) with the goal of minimizing resultant expected query time. The previous algorithm for optimal node splitting requires exponential time. One contribution of this paper is a polynomial time algorithm for finding optimal bipartitions for any objective function whose value depends exclusively on the bounding hyper-rectangles of the ensuing partitions. The algorithm runs in O(nd) time where d > 1 is the number of dimensions of the input. Experimental studies indicate that the use of optimal splits alone resultsin improvements of query performance of only between 5% and 15% when compared to other heuristics. Thus, a second contribution is to demonstrate the near optimality of previous split heuristics, a fact that suggests that research should focus on global rather than local optimization issues. Finally, we propose a new dynamic R-tree insertion method that uses a moreglobal restructuring heuristic when processing node overflows. When coupled with optimal splits our method results in improvements of up to 120% over the leading standard.

Copyright © 1998 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 DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bec90]
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
[Gut84]
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
[Kam93]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kam94]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Leu98]
Scott T. Leutenegger, Mario A. Lopez: The Effect of Buffering on the Performance of R-Trees. ICDE 1998: 164-171 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Leu97]
Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lop96]
...
[Rou85]
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
[Sel87]
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

Copyright © Mon Nov 2 21:19:16 2009 by Michael Ley (ley@uni-trier.de)