다중 존 디스크 환경에서 다차원 인덱스 구조의 효율적 저장 기법 = Efficient Storage Techniques for Multidimensional Index Structures in Multi-Zoned Disk Environments

국문 초록 (Abstract)

대용량의 다차원 데이타를 다루는 데이타베이스 응용분야에서는 접근 방법 및 기반 디스크 시스템이 전반적인 성능에 중요한 영향을 미친다. 현재 생산되고 있는 많은 디스크들은 다중의 물리적 존을 갖도록 설계되고 있다. 그러나 기존의 접근 방법에 대한 연구는 단순한 가정의 전통적인 디스크 모델에 기반을 두고 진행되어 왔고, 다중 존 디스크를 고려한 접근 방법에 대한 연구는 현재까지 거의 이루어 지지 않고 있다. 본 논문에서는 다중 존 디스크 환경에서 실질적인 데이타 전송률을 향상시키기 위해, 정적 및 동적 환경 모두를 고려한 다차원 인덱스 구조의 디스크 저장 기법을 제안한다. 이를 위해 다차원 인덱스 구조를 다중 존 디스크에 효과적으로 배치하는 알고리즘을 제시하고, 범위 질의에 대해 지역화된 질의 처리 기법을 제안한다. 또한 실험을 통하여 본 논문이 제안한 기술이 질의 성능을 획기적으로 향상시킨다는 것을 증명한다.

다국어 초록 (Multilingual Abstract)

The performance of database applications with large sets of multidimensional data depends on the performance of its access methods and the underlying disk system. In modeling the disk system, even though modern disks are manufactured with multiple physical zones, conventional access methods have been developed based on a traditional disk model with many simplifying assumptions. Thus, there is a marked lack of investigation on how to enhance the performance of access methods given a zoned disk model. The paper proposes novel zoning techniques that can be applied to any multidimensional access methods, both static and dynamic, enhancing the effective data transfer rate of underlying disk system by fully utilizing its zone characteristics. Our zoning techniques include data placement algorithms for multidimensional index structures and accompanying localized query processing algorithms for range queries. The experimental results show that our zoning techniques significantly improve the query performance.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 다중 존 구조에서의 인덱스 저장 기법
• 3. 다중 존에서의 질의 처리
• 4. 실험 결과
• 5. 결론
• 참고문헌

참고문헌 (Reference)

• 1 "Zoning Multidimensional Access Methods for Analytical Database Applications" 191-196, 2005
• 2 "Topological relations in the world of minimum bounding rectangles: A study with R- trees" 92-103, 1995
• 3 "Time- and Space- Optimality in B-trees ACM Transactions on Database Systems" 174-193, 1981
• 4 "The X-tree: An index structure for high-dimensional data" 28-39, 1996
• 5 "The TV- tree: An Index Structure for High-Dimensional Data" 3 : 517-542, 1995
• 6 "The TPR*-tree: An optimized spatio-temporal access method for predictive queries" 790-801, 2003
• 7 "The Pyramid-technique: Towards breaking the curse of dimensionality" 142-153, 1998
• 8 "The Effect of Buffering on the Performance of R-trees" 12 (12): 33-44, 2000
• 9 "Similarity Indexing with the SS-tree" 516-523, 1996
• 10 "Scalable QSF-Trees: Retrieving Regional Objects in High-Dimensional Spaces" Idea Group Publishing 15 (15): 45-59, 2004
• 11 "STR: A Simple and Efficient Algorithm for R-tree Packing" 497-506, 1997
• 12 "Novel Approaches to the Indexing of Moving Object Trajectories" 395-406, 2000
• 13 "Indexing the positions of continuously moving objects" 331-342, 2000
• 14 "In Proceedings of the ACM International Conference on Information and Knowledge Management" 490-499, 1993
• 15 "Evaluating Probabilistic Queries over Imprecise Data" 551-562, 2003
• 16 "Dynamic Splitting Policies of the Adaptive 3DR-tree for Indexing Continuously Moving Objects" Springer- Verlag, Berlin Hidelberg 2736 : 308-317, 2003
• 17 "Direct Spatial Search on Pictorial Database Using Packed R- trees ACM International Conference on Management of Data" 1985
• 18 "An Introduction to Disk Drive Modeling"
• 19 "An Efficient and Robust Access Method for Points and Rectangles In ACM SIGMOD International Conference on Management of Data" 1990
• 20 "An Efficient Zoning Technique for Multidimensional Access Methods" 129-143, 2005
• 21 "Advances in Disk Technology: Performance Issues" 75 (75): 1998
• 22 "A dynamic index structure for spatial searching on Management of Data" 47-54, 1984
• 23 "A Search Structure for Large Multidimensional Dynamic Indexes on Management of Data" 10-18, 1981
• 24 "A Retrieval Technique for High-Dimensional Data and Partially Specified Queries" 42 (42): 1-21, 2002