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