멀티미디어 DBMS에서 복합 유사질의 처리를 위한 효율적인 색인 구조의 설계 및 구현

Abstract

최근 GIS나 이미지 및 비디오 검색 등과 같은 멀티미디어 응용들은 대규모 멀티미디어 데이터 집 합에 대한 효율적인 k-최근접 질의 처리 기법들을 요구하고 있다. 현재까지 이러한 질의를 처리하기 위한 알고리즘으로 Hjaltason과 Samet이 제안한 점진적 최근접 알고리즘이 가장 좋은 알고리즘으로 알려져 있다. 그러나, 이 알고리즘에서 사용하는 R-tree는 시각적 특징 정보를 색인하기 위한 다차 원 색인구조이기 때문에 의미적 검색 조건을 만족시키지 않는 후보 튜플을 효과적으로 제거할 수 없다는 단점이 존재한다. 본 논문에서는 이러한 단점을 극복하기 위하여 최근 고차원 색인 구조로 제안된 SPY-TEC과 시그너쳐 기법을 연계하여 시각적 특징 정보뿐만 아니라 의미적 특징 정보를 동 시에 색인할 수 있는 새로운 통합 색인구조를 제안하며, 이 색인 구조상에서 k-최근접 질의를 효율 적으로 처리할 수 있는 알고리즘을 제안한다. Abstract Recently, advanced multimedia applications, such as geographic information system, and content-based image/video retrieval system, require the efficient processing of k-nearest neighbor queries over large collection of multimedia objects. Among the available techniques for processing such queries, the incremental nearest neighbor algorithm proposed by Hjaltason and Samet is known as the best choice. However, this algorithm has no facility capable of partially pruning the candidate tuples that will turn out not to satisfy the semantic predicate because the R-tree, an underlying index structure used in this algorithm, is a hierarchical multidimensional index structure for only indexing the visual feature information. To overcome these drawbacks, we propose an integrated index structure, so-called SPY-TEC+, that provides an efficient method for indexing visual and semantic feature information at the same time using the SPY-TEC that was proposed for indexing high-dimensional data, and the signature file. We also propose an efficient incremental nearest neighbor algorithm for processing the k-nearest neighbor queries with visual and semantic predicates on SPY-TEC+.1)