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: 7884
Venue: VLDB
Year: 1989
Pagerank: 9.4375327e-05
Overall Rank: 2,144 | 85.11%
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,004	On Indexing Mobile Objects	1999	PODS	0.00014694512
1,476	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00011752931
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
2,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
3,065	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.6258862e-05
4,544	On Indexing Line Segments	1990	VLDB	6.0939082e-05
4,669	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0039237e-05
5,100	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	5.6940372e-05
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
5,751	Query Processing for Distance Metrics	1990	VLDB	5.3396192e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
8,354	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5329424e-05
8,599	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4832771e-05
8,881	Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization	1993	SIGMOD	4.4252575e-05
8,894	Are Window Queries Representative For Arbitrary Range Queries?	1996	PODS	4.4232095e-05
12,784	A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations	1997	VLDB	4.1905499e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
1,009	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014658958
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
2,200	Gral: An Extensible Relational Database System for Geometric Applications	1989	VLDB	9.3055387e-05
4,279	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.2850695e-05
5,013	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	5.7533424e-05
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
4,743	Efficient Spatial Access To A Data Base	1982	SIGMOD	5.949696e-05
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
1,943	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB	0.00010009557