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


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 ... BibTeX

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


Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 BibTeX
Michael L. Fredman: The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries. FOCS 1980: 191-199 BibTeX
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 BibTeX
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579 BibTeX
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190 BibTeX
Andreas Henrich, Hans-Werner Six, Peter Widmayer: Paging Binary Trees with External Balancing. WG 1989: 260-276 BibTeX
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 BibTeX
Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 BibTeX
Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335 BibTeX
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) BibTeX
Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113 BibTeX
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 BibTeX

Referenced by

  1. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
  2. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
  3. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  4. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
  5. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  6. Andreas Henrich: The LSDh-Tree: An Access Structure for Feature Vectors. ICDE 1998: 362-369
  7. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
  8. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
  9. Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408
  10. Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
  11. Bernd-Uwe Pagel, Hans-Werner Six: Are Window Queries Representative for Arbitrary Range Queries? PODS 1996: 150-160
  12. Andreas Henrich: Improving the Performance of Multi-Dimensional Access Structures Based on k-d-Trees. ICDE 1996: 68-75
  13. Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB J. 4(2): 243-286(1995)
  14. Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91
  15. Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
  16. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
  17. Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179
  18. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
  19. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  20. Ralf Hartmut Güting: Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. SIGMOD Conference 1993: 277-286
  21. Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer: Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993: 214-221
  22. Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
  23. Wei Lu, Jiawei Han: Distance-Associated Join Indices for Spatial Range Search. ICDE 1992: 284-292
  24. Amarnath Gupta, Terry E. Weymouth, Ramesh Jain: Semantic Queries with Pictures: The VIMSYS Model. VLDB 1991: 69-79
  25. Jason Tsong-Li Wang, Dennis Shasha: Query Processing for Distance Metrics. VLDB 1990: 602-613
  26. H. V. Jagadish: On Indexing Line Segments. VLDB 1990: 614-625
  27. Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:40 2009