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: 2791
Venue: SIGMOD
Year: 1995
Pagerank: 6.0039237e-05
Overall Rank: 4,669 | 67.56%
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
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579
6,249	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.132996e-05
8,675	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	4.4654743e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
1,009	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014658958
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,302	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1905499e-05
12,852	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB	4.1905499e-05
1,766	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010611043
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
8,471	Adaptive Index Structures	2002	VLDB	4.4986491e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
639	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018782897
6,473	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0427056e-05
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05