DBScholar

Back to papers

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
2852
Venue
SIGMOD
Year
1995
Pagerank
6.4477987e-05
Overall Rank
4,914 | 66.29%
DOI
10.1145/223784.223796

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{freeston_sigmod95,
        title = {{A General Solution of the n-dimensional B-tree Problem}},
        author = {Freeston, Michael},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223796},
        url = {https://dl.acm.org/doi/10.1145/223784.223796},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
6,016 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 6.0082425e-05
8,680 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD 5.3857754e-05
Previous Page 1 / 1 Next

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.0020210012
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
96 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00034590762
936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00013092484
1,032 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012530965
1,877 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.5658249e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,036 New Concurrency Control Algorithms for Accessing and Compacting B-Trees 1994 VLDB
2 2,020 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB
3 5,304 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB
4 10,149 Bounding the Fragmentation of B-Trees Subject to Batched Insertions 2026 PODS
5 8,689 Adaptive Index Structures 2002 VLDB
6 1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB
7 8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD
8 1,059 On B-tree Indices for Skewed Distributions 1992 VLDB
9 6,451 Efficient Search of Multidimensional B-Trees 1995 VLDB
10 8,937 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS