A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations.

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
  author    = {Jong-Hak Lee and
               Young-Koo Lee and
               Kyu-Young Whang and
               Il-Yeol Song},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {A Region Splitting Strategy for Physical Database Design of Multidimensional
               File Organizations},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {416-425},
  ee        = {db/conf/vldb/LeeLWS97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP,}


This paper presents a region splitting strategy for physical database design of multidimensional file organizations. Physical database design is the process of determining the optimal configuration of physical files for a given set of queries. Recently, many multidimensional file organizations for supporting multiattribute access have been proposed in the literature. However, there has been no effort for their physical database design. We first show that the performance of query processing is highly affected by the similarity between the shapes of query regions and page regions in the domain space, and then propose a new region splitting strategy that finds the optimal configuration of the multidimensional file by controlling the interval ratio of different axes to achieve the similarity. We also present the results of extensive experiments using the multilevel grid file (MLGF), a multidimensional file organization, and various types of queries and record distributions. The results indicate that our proposed strategy builds optimal MLGFs regardless of query types and record distributions. When the interval ratio of a two-dimensional query region is 1:1024, the performance of the proposed strategy is enhanced by as much as 7.5 times over that of the conventional cyclic splitting strategy. The performance is further enhanced for the query types having higher interval ratios. The result is significant since interval ratios can be far from 1:1 for many practical applications, especially when different axes have different domains.

Copyright © 1997 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents BibTeX

Electronic Edition

From CS Dept., University Trier (Germany)


Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems, 2nd Edition. Benjamin/Cummings 1994, ISBN 0-8053-1748-1
Contents BibTeX
Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988) BibTeX
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994) BibTeX
David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
Yasuaki Nakamura, Shigeru Abe, Yutaka Ohsawa, Masao Sakauchi: A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics. IEEE Trans. Knowl. Data Eng. 5(4): 682-694(1993) BibTeX
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
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 BibTeX
Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994) BibTeX
Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:17 2009