DBScholar

Back to papers

The LSD tree: spatial access to multidimensional point and non-point objects

Summary: Introduces the Local Split Decision (LSD) tree for indexing multidimensional points and arbitrary geometric objects. Local split choices provide robust performance across data distributions, overlap, and bucket capacities, with paging that avoids tree degeneration. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
8074
Venue
VLDB
Year
1989
Pagerank
9.5658249e-05
Overall Rank
1,877 | 87.13%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{henrich_vldb89,
        title = {{The LSD tree: spatial access to multidimensional point and non-point objects}},
        author = {Henrich, Andreas and Six, Hans-Werner and Widmayer, Peter},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {45--53},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
896 On Indexing Mobile Objects 1999 PODS 0.0001334014
1,370 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010997795
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.5068846e-05
3,771 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 7.1391812e-05
4,620 On Indexing Line Segments 1990 VLDB 6.6025691e-05
4,914 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.4477987e-05
5,273 Semantic Queries with Pictures: The VIMSYS Model 1991 VLDB 6.2888624e-05
5,304 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.2733516e-05
5,798 Query Processing for Distance Metrics 1990 VLDB 6.0856815e-05
6,089 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.9806097e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,796 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.3702721e-05
9,099 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.3250598e-05
9,152 Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization 1993 SIGMOD 5.3133028e-05
12,969 A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations 1997 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0020210012
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
1,032 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012530965
1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.6928497e-05
2,628 Gral: An Extensible Relational Database System for Geometric Applications 1989 VLDB 8.326647e-05
4,357 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.7463723e-05
5,183 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.3286498e-05
6,777 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.7773009e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB
2 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
3 1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
4 4,978 Efficient Spatial Access To A Data Base 1982 SIGMOD
5 5,202 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB
6 9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
7 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
8 6,777 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB
9 936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB
10 2,421 Multidimensional Access Methods: Trees Have Grown Everywhere 1997 VLDB