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: hba84904d1e0e7926
Venue: PODS
Year: 1986
Pagerank: 6.5987766e-05
Overall Rank: 4,443 | 70.13%
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
965	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00012809362
1,903	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4032472e-05
5,292	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	6.1924532e-05
6,905	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.6505668e-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.0008122792
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
855	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.00013437655
4,595	A High Performance, Universal, Key Associative Access Method	1983	SIGMOD	6.5101758e-05
5,505	The Interpolation-Based Grid File	1985	PODS	6.1017692e-05
5,707	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	6.0283329e-05
6,623	Index Maintenance for Non-Uniform Record Distributions	1984	PODS	5.7307592e-05

Semantically Similar Papers

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