다차원 색인구조 M-트리에서 노드 색인 공간의 중첩을 최소화하기 위한 효율적인 분할 알고리즘
An Efficient Split Algorithm to Minimize the Overlap between Node Index Spaces in a Multi-dimensional Indexing Scheme M-tree
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
멀티미디어 데이타를 위한 내용기반 검색 서비스의 속도를 증진하기 위해 다차원 색인 기법에 대한 연구가 활발하게 진행되고 있다. 다차원 색인 기법의 하나인 M-트리는 노드의 중심점과 객체간의 상대적 거리를 이용하여 색인을 구성하고, 검색 공간에 포함되는 객체를 액세스하는 기법으로서 노드들은 페이지 단위로 구성되며 하위 엔트리들을 포함할 수 있는 반경, 즉 유사도 거리에 의해 노드의 영역이 표현되어진다. 그러나 이와 같은 노드의 영역 표현에 있어서 노드 색인 공간의 중첩으로 인해 질의 시 검색해야 하는 노드수가 증가하고 이는 거리계산과 디스크 입출력의 횟수를 증가시킨다. 본 논문에서는 M-트리에서 문제가 되고 있는 노드 색인 공간 중첩을 최소화하는 노드 분할 정책을 제안한다. M-트리의 기존 분할 정책들과는 다르게 노드의 가상 중심점을 계산하여 라우팅 객체로 이용하여 노드 색인 공간의 중첩을 최소화하고 노드 안의 엔트리 재분배를 통해 노드의 색인 공간의 크기를 작게 유지하며 밀도 높은 노드를 구성하도록 한다. 실험으로부터 제안된 노드 분할 알고리즘이 라우팅 노드의 색인 공간의 반경을 작게 유지하며 결과적으로는 사용자 질의에 대해 개선된 응답 시간을 제공하는 것으로 판명되었다.
Abstract
To enhance the user response time of content-based retrieval service for multimedia information, several multi-dimensional index schemes have been proposed. M-tree, a well-known multidimensional index scheme is of metric space access method, and is based on the distance between objects in the metric space. However, since the overlap between index spaces of nodes might enlarge the number of nodes of M-tree accessed for query processing, the user response time for content-based multimedia information retrieval grows longer. In this paper, we propose a node split algorithm which is able to reduce the size of overlap between index spaces of nodes in M-tree. In the proposed scheme, we choose a virtual center point as the routing object and entry redistribution as the postprocessing after node split in order to reduce the radius of index space of a node, and finally in order to reduce the overlap between the index spaces of routing nodes. From the experimental results, we can see the proposed split algorithm reduce the overlap between index space of nodes and finally enhance the user response time for similarity-based query processing.
참고문헌 (19)
- C. Faloutsos, "Efficient and Effective Querying by Image Content", pp.231~262 (1994)
- C. Faloutsos, "A Fast Algorithm for Indexing Data-mining and Visualization of Traditional and Multimedia Databases", pp.163~174 (1995)
- E. Wood, "and Retrieval of Audio", pp.27~36 (1996)
- R. Agrwal,C. Faloutsos,and A. Swami, "Efficient Similarity Search in Sequence Databases", (730), pp.69~84 (1993), springer-verlag
- V. Gaedes, "Multidimensional Access Methods", pp.36~59 (1996)
- C. Traina Jr, "Fast Indexing and Visualization of Metric Data Sets using Slim-Trees", pp.244~259 (2002)
- C. Traina Jr, "High Performance Metric Trees Minimizing Overlap Between Nodes", pp.51~65 (2000)
- N. Beckmann, "An Efficient and Robust Access Method for Point and Rectangles Proc. of Int. Conf. on ACM SIGMOD", pp.322~331 (1990)
- D. A. White, "Similarity Indexing with the SS-tree", pp.516~523 (1996)
- N. G. Colossi, "Benchmarking Access Structure for High-Dimensional Multimedia Data" (1999), Univ. of Alberta
- N. Katayama, "The SR-tree:An Index Structure for High-Dimensional Nearest-Neighbor queries", pp.28~29 (1996)
- D. A. Keim, "An Index Structure for High-Dimensional Data", pp.517~542 (1996)
- J. K. Uhlmann, "Satisfying General Proximity", Similarity Queries with Metric Trees, 1991., 175~179
- T. Bozkaya, "Distance-Based Indexing for High-Dimensional Metric Spaces", pp.357~368 (1997)
- P. Ciaccia, "An Efficient Access Method for Similarity Search in Metric spaces", pp.426~435 (1997)
- E. Chavez, "Searching in Metric Spaces", pp.273~321 (2001)
- J. Han, "Data Mining: Concepts and Techniques", pp.349~354 (2001), Morgan Kaufmann Publishers
- J. M. Hellerstein, "Generalized Search Trees for Database Systems", pp.562~573 (1995)
- 박만수, "Pitch 히스토그램을 이용한 내용기반 음악 정보 검색", 9(1), pp.2~8 (2004), 한국방송공학회