A General Solution of the n-dimensional B-tree Problem

Summary: Proposes a generic solution to the n-dimensional B-tree problem arising from recursive data-space partitioning in multi-dimensional indexes. Shows how the partitioning preserves B-tree-like log access/update and a 1/3 occupancy bound for data and index nodes in n dimensions, yielding predictable worst-case performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2790
Venue: SIGMOD
Year: 1995
Pagerank: 6.0085156e-05
Overall Rank: 4,672 | 67.50%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Michael Freeston

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
6,243	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.1402191e-05
8,679	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	4.4697591e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938
1,008	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014666726
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4416732e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
12,843	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB	4.1945683e-05
5,328	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5665496e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677
6,480	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0475112e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05