ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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
@inproceedings{DBLP:conf/vldb/LeeLWS97,
  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, http://dblp.uni-trier.de}
}

Abstract

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

From CS Dept., University Trier (Germany)

References

[1]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems, 2nd Edition. Benjamin/Cummings 1994, ISBN 0-8053-1748-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:06 2010 by Michael Ley (ley@uni-trier.de)