그리드 분할에 의한 다차원 데이터 디클러스터링 성능 분석
Performance Analysis on Declustering High-Dimensional Date by GRID Partitioning
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
대규모의 데이터를 다루는 여러 시스템에서 데이터를 다수의 병렬 디스크에 분산시켜 저장한 후 질의 처리시 동시에 여러 개의 디스크를 접근함으로써 입출력 성능의 향상을 위한 많은 노력들이 행해져 왔다. 대부분 이전 연구들은 데이터 공간을 이루는 각 차원이 겹치지 않는 여러 개의 구간으로 나누어져 전체 데이터 공간이 그리드 형태로 분할되어 있다는 가정하에 각 차원의 구간 번호로 결정되는 그리드 셀에 대해서 효과적으로 디스크 번호를 할당하는 알고리즘 개발에 집중되었다. 하지만, 그들은 데이터 공간을 그리드 형태로 분할하는 방법이 전체 디클러스터링 알고리즘 성능에 미치는 영향을 간과하였다. 본 논문에서 우리는 효과적인 그리드 분할을 통하여 매핑 함수를 이용하는 디클러스터링 알고리즘의 성능을 향상 시켰다. 이를 위하여 영역 질의 크기가 주어졌을 때 겹치는 그리드 셀의 수를 예측하는 모델을 제시하였으며 이를 이용하여 가능한 그리드 분할 방법들 중에서 질의 크기를 감소시키는 분할 방법을 선택하였다. 일반적으로, 다차원 데이터에 대해서는 이진 분할을 하지만 본 논문에서는 더 작은 수의 차원을 선택해서 여러 번 분할함으로써 질의를 만족하는 그리드 셀의 수를 감소시켰다. 다양한 실험 결과에 의하면 본 논문에서 제시한 예측 모델은 질의 크기와 차원에 관계없이 0.5% 이내의 에러율을 보이는 것으로 나타났다. 또한 효과적인 그리드 분할을 통하여 다차원 데이터에 대해서 가장 성능이 좋은 것으로 소개 되고 있는 Kronecker sequence 매핑 함수를 이용하는 디클러스터링 알고리즘의 성능을 최대 23배까지 향상시킬 수 있음을 알 수 있었다.
Abstract
A lot of work has been done to improve the I/O performance of such a system that store and manage a massive amount of data by distributing them across multiple disks and access them in parallel. Most of the previous work has focused on an efficient mapping from a grid cell, which is determined by the interval number of each dimension, to a disk number on the assumption that each dimension is split into disjoint intervals such that entire data space is GRID-like partitioned. However, they have ignored the effects of a GRID partitioning scheme on declustering performance. In this paper, we enhance the performance of mapping function based declustering algorithms by applying a good GRID partitioning method. For this, we propose an estimation model to count the number of grid cells intersected by a range query and apply a GRID partitioning scheme which minimizes query result size among the possible schemes. While it is common to do binary partition for high-dimensional data, we choose less number of dimensions than needed for binary partition and split several times along that dimensions so that we can reduce the number of grid cells touched by a query. Several experimental results show that the proposed estimation model gives accuracy within 0.5% error ratio regardless of query size and dimension. We can also improve the performance of declustering algorithm based on mapping function, called Kronecker Sequence, which has been known to be the best among the mapping functions for high-dimensional data, up to 23 times by applying an efficient GRID partitioning scheme.
참고문헌 (25)
- M. J. Atallah, "Optimal Parallel Block Access for Range Queries", pp.205~215 (2000)
- R. Bhatia, "Declustering Using Golden Ratio Sequences", pp.271~280 (2000)
- C-M. Chen, "Multidimensional Declustering Schemes Using Golden Ratio and Kronecker Sequences", 15(3), pp.659~670 (2003)
- C. M. Chen, "From Discrepancy to Declu- stering：Near optimal multidimensional declustering strategies for range queries", pp.29~38 (2002)
- H. C. Du, "Disk Allocation for Cartisian Files on Multiple-Disk Systems", 7(1), pp.82~102 (1982)
- C. Faloutsos, "IEEE Trans on Computers", 40(8), pp.907~914 (1991)
- M. H. Kim, "Optimal File Distribution For Partial Match Retrieval", pp.173~182 (1988)
- T-W. Kim, "A Distance-Based Packing Method for High Dimensional Data" (2003), Pusan National University
- S-W. Kuo, "New GDM-based Declustering Methods for Parallel Range Queries", pp.119~127 (1999)
- D. R. Liu, "Partitioning Similarity Graphs：A Framework for Declustering Problems：", 21(6), pp.475~496 (1996)
- S. Prabhakar, "Cyclic Allocation of Two-Dimensional Data", pp.94~101 (1998)
- Y. Zhou, "Disk Allocation Methods for Parallelizing Grid Files", pp.243~252 (1994)
- C. Bhm, "Fast Parallel Similarity Search in Multimedia Databases", pp.1~12 (1997)
- K. Abdel-Ghaffar, "Optimal Allocation of Two-Dimensional Data", pp.409~418 (1997)
- Y-L. Lo, "：A Multidimensional Data Partitioning Technique for Multi- processor Database Systems.", 9(3), pp.211~236 (2001)
- S. Prabhakar, "Disk Allocation for Fast Range and Nearest-Neighbor Queries", 14(2), pp.107~135 (2003)
- C-.M Chen, "Analysis and Comparison of Declustering Schemes for Interactive Navigation Queries", 12(5), pp.763~778 (2000)
- M. T. Fang, "The Idea of De-Clustering and Its Applications"
- B. Chor, "An Application of Number Theory to the Organization of Ras- ter-Graphics Memory Journal of ACM", 33(1), pp.86~104 (1986)
- L. T. Chen, "Declustering Objects for Visu- alization", pp.85~96 (1993)
- C. Chang, "Titan：a High-Performance Remote-sensing Database", pp.375~384 (1997)
- R. Bhatia, "Hierachical Decl- ustering Schemes for Range Queries", pp.525~537 (2000)
- D-R. Liu, "A Hypergraph Based Approach to Declustering Problems", 10(3), pp.269~288 (2001)
- T-W. Kim, "Analyzing the range query performance of two partitioning methods in high-dimensional space Department of Computer Science" (2003), Pusan National University
- S. Berchtold,, "Improving the Query Performance of High-Dimensional Index Structures by Bulk Loading R-trees", pp.216~230 (1998)