ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects.

Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53
@inproceedings{DBLP:conf/vldb/HenrichSW89,
  author    = {Andreas Henrich and
               Hans-Werner Six and
               Peter Widmayer},
  editor    = {Peter M. G. Apers and
               Gio Wiederhold},
  title     = {The LSD tree: Spatial Access to Multidimensional Point and Nonpoint
               Objects},
  booktitle = {Proceedings of the Fifteenth International Conference on Very
               Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands},
  publisher = {Morgan Kaufmann},
  year      = {1989},
  isbn      = {1-55860-101-5},
  pages     = {45-53},
  ee        = {db/conf/vldb/HenrichSW89.html},
  crossref  = {DBLP:conf/vldb/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We propose the Local Split Decision tree (LSD tree, for short), a data structure supporting efficient spatial access to geometric objects. Its main advantages over other structures are that it performs well for all reasonable data distributions, cover quotients (which measure the overlapping of the data objects), and bucket capacities, and that it maintains multidimensionalpoints as well as arbitrary geometric objects. These properties demonstrated by an extensive performance, evaluation make the LSD tree extremely suitable for the implementation of spatial access paths in geometric databases. The paging algorithm for the binary tree directory is interesting in its own right because a practical solution for the problem of how to page a (multidimensional) binary tree without access path degeneration is presented.

Copyright © 1989 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

Peter M. G. Apers, Gio Wiederhold (Eds.): Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. Morgan Kaufmann 1989, ISBN 1-55860-101-5
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[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
[FSR87]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fred80]
Michael L. Fredman: The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries. FOCS 1980: 191-199 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Free87]
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
[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
[Güt89]
Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hin85]
...
[HSW88a]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW88b]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW89]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: Paging Binary Trees with External Balancing. WG 1989: 260-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ks86]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS88]
Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KW85]
...
[LZL88]
Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NHS84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Otoo86]
Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113 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
[SK88]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SW88]
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)