ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Balanced Multidimensional Extendible Hash Tree.

Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113
@inproceedings{DBLP:conf/pods/Otoo86,
  author    = {Ekow J. Otoo},
  title     = {Balanced Multidimensional Extendible Hash Tree},
  booktitle = {Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 24-26, 1986, Cambridge, Massachusetts},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-179-2},
  pages     = {100-113},
  ee        = {http://doi.acm.org/10.1145/6012.6015, db/conf/pods/Otoo86.html},
  crossref  = {DBLP:conf/pods/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present a method for designing a multidimensional order preserving extendible hashing scheme that allows the directory to grow almost linearly with the number of insertions, irrespective of the key distribution. Such robustness in the design is achieved through the use of a hierarchical directory that grows in a manner similar to a multidimensional B-tree. For most practical directory sizes of at most 232 entries, we guarantee no more than three disk accesses for an exact match search. Like the grid file, the directory corresponds to a rectilinearly partitioned attribute space which is represented as d-dimensional extendible array. Hence range and partial-range searches are efficiently executed in 0(nR), where nR is the number of rectangular cells that cover the response region.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts. ACM 1986, ISBN 0-89791-179-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
[2]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]
Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179 BibTeX
[4]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
[5]
Philippe Flajolet: On the Performance Evaluation of Extendible Hashing and Trie Searching. Acta Inf. 20: 345-369(1983) BibTeX
[6]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[7]
...
[8]
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 BibTeX
[9]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[10]
David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133 BibTeX
[11]
Haim Mendelson: Analysis of Extendible Hashing. IEEE Trans. Software Eng. 8(6): 611-619(1982) BibTeX
[12]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[13]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[14]
...
[15]
Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506 BibTeX
[16]
...
[17]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[18]
Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27 BibTeX
[19]
Mark H. Overmars, Jan van Leeuwen: Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Inf. 17: 267-285(1982) BibTeX
[20]
Mireille Régnier: Analysis of Grid File Algorithms. BIT 25(2): 335-357(1985) BibTeX
[21]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[22]
Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984) BibTeX
[23]
...

Referenced by

  1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  2. Thomas A. Mück, Manfred J. Schauer: Optimizing Sort Order Query Execution in Balanced and Nested Grid Files. IEEE Trans. Knowl. Data Eng. 7(2): 246-260(1995)
  3. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
  4. Aris M. Ouksel, Otto Mayer: The Nested Interpolation Based Grid File. MFDBS 1991: 173-187
  5. Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526
  6. Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601
  7. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379
  8. Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53
  9. Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
  10. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190
  11. Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503
  12. Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376
  13. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579
  14. Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363
  15. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions. ICDE 1987: 10-17
  16. Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:49 2009