The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure.

@inproceedings{DBLP:conf/dasfaa/WhangK91,
  author    = {Kyu-Young Whang and
               Ravi Krishnamurthy},
  editor    = {Akifumi Makinouchi},
  title     = {The Multilevel Grid File - A Dynamic Hierarchical Multidimensional
               File Structure},
  booktitle = {Database Systems for Advanced Applications '91, Proceedings of
               the Second International Symposium on Database Systems for Advanced
               Applications, Tokyo, Japan, April 2-4, 1991},
  publisher = {World Scientific},
  series    = {Advanced Database Research and Development Series},
  volume    = {2},
  year      = {1991},
  isbn      = {981-02-1055-8},
  pages     = {449-459},
  ee        = {db/conf/dasfaa/WhangK91.html},
  crossref  = {DBLP:conf/dasfaa/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[Aho79]

Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979) BibTeX

[Bay72]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[Bay77]

Rudolf Bayer, Karl Unterauer: Prefix B-Trees. ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX

[Ber81]

Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX

[Ben75]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX

[Bol79]

Azad Bolour: Optimality Properties of Multiple-Key Hashing Functions. J. ACM 26(2): 196-210(1979) BibTeX

[Bur76a]

...

[Bur76b]

Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976) BibTeX

[Bur83]

Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX

[Fag79]

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

[Fin74]

Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX

[Fre60]

...

[Fus85]

Shinya Fushimi, Masaru Kitsuregawa, Masaya Nakayama, Hidehiko Tanaka, Tohru Moto-Oka: Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. SIGMOD Conference 1985: 308-318 BibTeX

[Ham76]

Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX

[Hin85]

...

[Knu73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[Kri84]

Ravi Krishnamurthy, Stephen P. Morgan: Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract). VLDB 1984: 26-29 BibTeX

[Lar78]

Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX

[Lar80]

Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX

[Lar82]

Per-Åke Larson: Performance Analysis of Linear Hashing with Partial Expansions. ACM Trans. Database Syst. 7(4): 566-587(1982) BibTeX

[Lio77]

J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977) BibTeX

[Lit78]

Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX

[Lit79]

...

[Lit80]

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX

[Lit81]

Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX

[Lom81]

David B. Lomet: Digital B-Trees. VLDB 1981: 333-344 BibTeX

[Mer82]

T. H. Merrett, Ekow J. Otoo: Dynamic Multipaging: A Storage Structure for Large Shared Data Banks. JCDKB 1982: 237-255 BibTeX

[Mul81]

James K. Mullin: Tightly Controlled Linear Hashing without Separate Overflow Storage. BIT 21(4): 390-400(1981) BibTeX

[Nie84]

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

[Ore82]

Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) BibTeX

[Oto84]

Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506 BibTeX

[Oto85a]

Ekow J. Otoo: A Multidimensional Digital Hashing Scheme for Files With Composite Keys. SIGMOD Conference 1985: 214-229 BibTeX

[Oto85b]

...

[Ouk83]

Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX

[Riv76]

Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX

[Rob81]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[Sch81]

Michel Scholl: New File Organizations Based on Dynamic Hashing. ACM Trans. Database Syst. 6(1): 194-211(1981) BibTeX

[Sch82]

Peter Scheuermann, Aris M. Ouksel: Multidimensional B-trees for associative searching in database systems. Inf. Syst. 7(2): 123-137(1982) BibTeX

[Wha83]

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983) BibTeX

[Wha84]

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) BibTeX

[Wha85a]

Kyu-Young Whang: Property of separability in physical design of network model databases. Inf. Syst. 10(1): 57-63(1985) BibTeX

[Wha85b]

Kyu-Young Whang: Index Selection in Relational Databases. FODO 1985: 487-500 BibTeX

[Wie83]

...

Referenced by

1. Junping Sun, William I. Grosky: Dynamic Maintenance of Multidimensional Range Data Partitioning for Parallel Data Processing. DOLAP 1998: 72-79
2. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
3. Sang-Wook Kim, Wan-Sup Cho, Min-Jae Lee, Kyu-Young Whang: A New Algorithm for Processing Joins Using the Multilevel Grid File. DASFAA 1995: 115-123
4. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
5. Shashi Shekhar, Babak Hamidzadeh, Ashim Kohli, Mark Coyle: Learning Transformation Rules for Semantic Query Optimization: A Data-Driven Approach. IEEE Trans. Knowl. Data Eng. 5(6): 950-964(1993)
6. Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
7. Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113