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

Summary: LSD tree: spatial index for k-D points and non-point objects, robust across distributions, cover quotients, and bucket capacities. Novel binary-tree directory paging with refined splitting avoids clipping/overlap, enabling fast, exact spatial access and interval handling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7883
Venue: VLDB
Year: 1989
Pagerank: 9.4416732e-05
Overall Rank: 2,144 | 85.09%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
1,479	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00011749057
1,528	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011497734
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,678	Effectively Learning Spatial Indices	2020	VLDB	8.3252088e-05
3,064	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.6279403e-05
4,547	On Indexing Line Segments	1990	VLDB	6.0986695e-05
4,672	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0085156e-05
5,101	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	5.6995265e-05
5,328	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5665496e-05
5,756	Query Processing for Distance Metrics	1990	VLDB	5.3401202e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05
8,359	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5372925e-05
8,601	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4875358e-05
8,881	Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization	1993	SIGMOD	4.4294996e-05
8,894	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	4.4274507e-05
12,775	A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations	1997	VLDB	4.1945683e-05

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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
1,008	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014666726
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05
2,199	Gral: An Extensible Relational Database System for Geometric Applications	1989	VLDB	9.3081334e-05
4,286	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.2898839e-05
5,021	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	5.7548311e-05
6,571	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0061936e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05
4,742	Efficient Spatial Access To A Data Base	1982	SIGMOD	5.9588592e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
6,571	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0061936e-05
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938
1,945	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB	0.00010001003