Balanced Multidimensional Extendible Hash Tree

Summary: Order-preserving multidimensional extendible hashing with a hierarchical, B-tree–like directory that grows nearly linearly with insertions irrespective of key distribution. Guarantees ≤3 disk I/Os for exact-match (dirs ≤2^s) and supports grid-file–style range/partial queries in O(n_r) via a d‑dimensional extendible array. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 769
Venue: PODS
Year: 1986
Pagerank: 6.7463723e-05
Overall Rank: 4,357 | 70.11%
DOI: 10.1145/6012.6015

Incoming Non-self Citations Over Time

Authors

1. Ekow J. Otoo (Carleton University)

BibTeX Citation

@inproceedings{otoo_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{Balanced Multidimensional Extendible Hash Tree}},
        url = {https://dl.acm.org/doi/10.1145/6012.6015},
        doi = {10.1145/6012.6015},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Otoo, Ekow J.},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
5,183	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	6.3286498e-05
6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.7773009e-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
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
833	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.0001372601
4,505	A High Performance, Universal, Key Associative Access Method	1983	SIGMOD	6.6592412e-05
5,377	The Interpolation-Based Grid File	1985	PODS	6.2410452e-05
5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	6.1661217e-05
6,497	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.862009e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
2	507	Interpolation-Based Index Maintenance	1983	PODS
3	13,087	Fast Search In Main Memory Databases	1992	SIGMOD
4	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
5	253	A Class of Data Structures for Associative Searching	1984	PODS
6	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
7	3,115	Extendible Hashing for Concurrent Operations and Distributed Data	1983	PODS
8	5,047	A Multidimensional Digital Hashing Scheme for Files With Composite Keys	1985	SIGMOD
9	833	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS
10	5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB