Performance Analysis for Multidimensional Indexing Methods Supporting Sequential Access

Guang-Ho Cha(차광호) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.2004 No.5

GB - 색인 : 고차원 데이타의 복합 유사 질의 및 적합성 피드백을 위한 색인 기법

차광호(Guang-Ho Cha) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.4

멀티미디어 데이타베이스와 같은 고차원 응용에서 유사 색인과 검색은 어려운 문제이며, 특히, 다수의 특성을 함께 색인하는 경우에는 더욱 어렵다. 본 논문에서는 고차원 이미지 데이타베이스에서 복합유사 질의 및 적합성 피드백을 효율적으로 처리하기 위한 새로운 색인 기법인 GB-색인을 제시한다. GB-색인은 각 특성 차원을 독립적으로 처리함으로써 다수의 특성과 다수의 질의 객체를 유연하게 제어한다. 아울러, 비트맵 색인을 통해 데이타베이스에 있는 모든 객체를 비트맵의 집합으로 표현하여 질의를 효율적으로 처리한다. GB-색인의 기술적인 주된 공헌은 다음과 같다: (1) 고차원 데이타를 위한 효율적인 색인, (2) 효율적인 복합 유사 질의 처리, (3) 적합성 피드백을 위한 분리형 질의의 효과적 처리. 실험 결과에 따르면 GB-색인은 순차 탐색 및 VA-파일에 비해 큰 성능 향상을 보였다. Similarity indexing and searching are well known to be difficult in high-dimensional applications such as multimedia databases. Especially, they become more difficult when multiple features have to be indexed together. In this paper, we propose a novel indexing method called the GB-index that is designed to efficiently handle complex similarity queries as well as relevance feedback in high-dimensional image databases. In order to provide the flexibility in controlling multiple features and query objects, the GB-index treats each dimension independently. The efficiency of the GB-index is realized by specialized bitmap indexing that represents all objects in a database as a set of bitmaps. Main contributions of the GB-index are three-fold: (1) It provides a novel way to index high-dimensional data; (2) It efficiently handles complex similarity queries; and (3) Disjunctive queries driven by relevance feedback are efficiently treated. Empirical results demonstrate that the GB-index achieves great speedups over the sequential scan and the VA-file.

이미지 데이터베이스 유사도 순위 매김 알고리즘

차광호(Guang-Ho Cha) 한국정보과학회 2009 정보과학회논문지 : 데이타베이스 Vol.36 No.5

이 논문은 이미지 데이터베이스를 위한 유사도 순위 매김 알고리즘을 제시한다. 이미지 검색의 문제점 중 하나가 이미지로부터 자동적으로 계산한 하위 레벨 특성과 인간 지각과의 의미 차이이며, 검색시에 이미지 유사도 측정을 위해 많은 알고리즘에서는 민코프스키 측정법(L<SUB>p</SUB>-norm)을 사용하고 있다. 그러나 민코프스키 측정법은 인간 시각 시스템의 비선형적 특성과 문맥 정보를 반영하지 못한다. 본 알고리즘에서는 인간 지각의 비선형성과 문맥 정보를 반영하는 유사도와 탐색 알고리즘을 통해 이 문제를 해결한다. 본 알고리즘을 필기체 숫자 이미지 데이터베이스에 적용하여 성능의 우수성과 효과를 증명하였다. In this paper, we propose a similarity search algorithm for image databases. One of the central problems regarding content-based image retrieval (CBIR) is the semantic gap between the low-level features computed automatically from images and the human interpretation of image content. Many search algorithms used in CBIR have used the Minkowski metric (or Lp-norm) to measure similarity between image pairs. However those functions cannot adequately capture the aspects of the characteristics of the human visual system as well as the nonlinear relationships in contextual information. Our new search algorithm tackles this problem by employing new similarity measures and ranking strategies that reflect the nonlinearity of human perception and contextual information. Our search algorithm yields superior experimental results on a real handwritten digit image database and demonstrates its effectiveness.

수요자 주도 광고를 위한 객체기반 대화형 비디오 시스템

차광호(Guang-Ho Cha) 한국정보과학회 2014 정보과학회논문지 : 데이타베이스 Vol.41 No.2

논문은 비디오 시청 중에 시청자의 관심을 끄는 객체가 있을 경우 그 객체를 클릭하거나 터치하여 선택하고 관련된 정보를 입수하여 구매를 유발시키는 새로운 형태의 광고 패러다임을 제공할 수 있는 객체기반 대화형 비디오 시스템을 제시한다. 이러한 시스템은 수요자 주도 광고나 시청자 특유의 광고 등과 같은 새로운 형태의 e-비즈니스 응용을 만들어 낼 수 있으며, 스트리밍 비디오의 새로운 대화 가능성을 제시하고, 전자 상거래를 PC에서 TV나 스마트폰으로 이동하게 하는 기회를 제공한다. 본 논문은 이러한 시스템을 위한 체계 및 저작 도구를 설명하고, 대화형 비디오의 비즈니스 기회와 도전에 대해 고찰한다. This paper presents an object-based interactive video system providing a new advertising paradigm that induces a viewer to take interests in the objects in the video and to buy the goods related to them by clicking or touching them while watching the video. This system could be used to create a new form of e-business applications such as consumer-driven advertising and audience-specific advertising. This object-based video system offers new interaction possibilities of the streaming video and the opportunity to move electronic commerce from personal computers to television receivers or smartphones. This paper presents the schematics for creating an object-based interactive video system and describes an authoring tool to create the interactive video. Finally, we also examine the business opportunities and challenges of the interactive video.

다차원 범위 질의를 위한 순차 색인 기법

차광호(Guang-Ho Cha) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.3

이 논문은 다차원 범위 질의를 위한 순차 색인 기법인 세그먼트-페이지 색인(SP-색인)이라는 새로운 색인 기법을 제안한다. SP-색인의 목표는 (1) 다차원 색인 기법에서의 범위 질의의 성능 향상, (2) 과도한 색인의 재구성 없이 색인의 클러스터링이라는 두 가지로 요약된다. 오랜 동안의 데이타베이스 연구결과로 다양한 다차원 색인 기법이 개발 되었지만, 대부분의 연구가 데이타 레벨의 클러스터링에 초점을 맞추었고, 색인 자체의 클러스터링에는 거의 관심을 두지 않았다. 따라서 대부분의 관련된 색인 노드가 디스크에 분산되고, 질의 처리 시에 많은 무작위 디스크 접근이 발생한다. SP-색인은 관련된 노드를 연속적인 디스크 페이지로 구성되는 하나의 세그먼트에 저장하여 노드들의 분산을 피하고, 세그먼트 내에서의 순차 접근을 통해 질의 처리 성능을 높인다. 실험 결과에 따르면 SP-색인은 페이지 기반의 전통적인 색인 기법에 비해 수행 시간 면에서 수 배의 성능 향상을 보이고, 단순히 큰 페이지를 사용에 따른 디스크 대역폭 낭비를 줄인다. This paper presents a new sequential indexing method called segment-page indexing (SP-indexing) for multidimensional range queries. The design objectives of SP-indexing are twofold: (1) improving the range query performance of multidimensional indexing methods (MIMs) and (2) providing a compromise between optimal index clustering and the full index reorganization overhead. Although more than ten years of database research has resulted in a great variety of MIMs, most efforts have focused on data-level clustering and there has been less attempt to cluster indexes. As a result, most relevant index nodes are widely scattered on a disk and many random disk accesses are required during the search. SP-indexing avoids such scattering by storing the relevant nodes contiguously in a segment that contains a sequence of contiguous disk pages and improves performance by offering sequential access within a segment. Experimental results demonstrate that SP-indexing improves query performance up to several times compared with traditional MIMs using small disk pages with respect to total elapsed time and it reduces waste of disk bandwidth due to the use of simple large pages.

적응 분할과 벡터 근사에 기반한 고차원 이미지 색인 기법

차광호(Guang-Ho Cha),정진완(Chin-Wan Chung) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.2

이 논문은 고차원 이미지 데이타의 효율적인 색인을 위한 LCP+-file을 제시한다. 멀티미디어 데이타의 사용이 증가하면서 고차원 이미지 데이타의 색인과 검색의 지원에 대한 요구가 증가하고 있다. 최근에 고차원 데이타의 색인을 위해 벡터 근사에 기반한 LPC-file [5]이 개발되었다. LPC-file은 특히, 데이타집합이 균일하게 분포할 때는 좋은 성능을 나타내지만 클러스터(cluster)를 이룰 때는 성능이 하락한다. 본 논문은 강하게 클러스터를 이루는 이미지 데이타 집합에 대해 LPC-file의 성능을 향상시킨 LCP+-file을 제시한다. 기본 아이디어는 고밀도 클러스터를 갖는 부분 공간을 찾기 위해 데이타 공간을 적응적으로 분할하고, 그 공간에 대해 벡터 근사의 식별 능력을 향상시키기 위해 더 많은 수의 비트를 할당한다. 그러나 분할된 공간이 비트들을 공유하기 때문에 사용되는 전체 비트 수는 오히려 줄어든다. 실험 결과에 따르면 LCP+-file은 강하게 클러스터를 이루는 이미지 데이타 집합에 대해 LPC-file의 성능을 크게 향상시킨다. In this paper, we propose the LPC+-file for efficient indexing of high-dimensional image data. With the proliferation of multimedia data, there is an increasing need to support the indexing and retrieval of high-dimensional image data. Recently, the LPC-file [5] that based on vector approximation has been developed for indexing high-dimensional data. The LPC-file gives good performance especially when the dataset is uniformly distributed. However, compared with for the uniformly distributed dataset, its performance degrades when the dataset is clustered. We improve the performance of the LPC-file for the strongly clustered image dataset. The basic idea is to adaptively partition the data space to find subspaces with high-density clusters and to assign more bits to them than others to increase the discriminatory power of the approximation of vectors. The total number of bits used to represent vector approximations is rather less than that of the LPC-file since the partitioned cells in the LPC+-file share the bits. An empirical evaluation shows that the LPC+-file results in significant performance improvements for real image datasets which are strongly clustered.

비구조화된 이미지 저장소를 위한 객체지향 검색체계

차광호(Guang-Ho Cha),정진완(Chin-Wan Chung) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.2

This paper describes an object-oriented mechanism for effective image retrieval from unstructured image repositories. The image content is defined by three kinds of information: visual information with quantifiable characteristics, semantic information with non-quantifiable characteristics, and keywords describing most abstract information. The visual information and keywords are usually stored in a repository as sets without any specific structure. On the other hand, it is natural that the semantic information is represented by some hierarchical structure with inheritance and aggregation relationships. We present the unified retrieval mechanism for these unstructured image repositories using the object-oriented model. Experiments have been earned out on large image collections to demonstrate the effectiveness of the proposed retrieval mechanism. 본 논문은 비구조화된 이미지 저장소로 부터 효과적인 이미지 검색을 위한 객체 지향 검색 체계를 제시한다. 본 검색 체계에서는 이미지의 내용을 정량적 특성을 갖는 시각 정보, 비정량적 특성을 나타내는 의미 정보, 그리고 가장 추상적인 정보를 포함하는 키워드의 세 종류로 규정한다. 시각 정보와 키워드는 특별한 구조 없이 집합의 형태로 저장하고, 의미 정보는 상속과 군집 관계를 갖는 계층 구조로 저장하는 것이 자연스럽다. 본 논문에서는 객체 지향 모델을 사용하여 비구조화된 이미지 저장소를 위한 통일된 검색 체계를 제시한다. 제안된 검색 체계의 효과를 검증하기 위해 많은 이미지 집합에 대한 실험을 수행하였다.

GC - 트리 : 이미지 데이타베이스를 위한 계층 색인 구조

차광호(Guang-Ho Cha) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.1

멀티미디어 데이타의 사용이 증가함에 따라 고차원 이미지 데이타에 대한 효율적인 색인과 검색 기법이 크게 요구되고 있다. 그러나 많은 노력에도 불구하고 현재의 다차원 색인 기법들은 고차원 데이타 공간에서 만족할 만한 성능을 보여주지 못하고 있다. 이러한 소위 차원의 저주를 해결하기 위해 최근에 차원을 줄이거나 근사 해를 구하는 등의 접근법이 시도되고 있지만 이러한 방법들은 근본적으로 정확도의 상실이라는 문제를 갖고 있다. 정확도의 보존을 위해 VA-file, LPC-file등과 같이 벡터 근사에 기반한 기법들이 최근에 개발되었다. 그러나 이 기법은 검색 성능이 색인 파일의 크기에 큰 영향을 받으며, 한번에 큰 검색 공간을 줄이는 계층 색인 구조의 장점을 상실한다. 본 논문에서는 이미지 데이타베이스에서 유사성 질의를 위한 새로운 계층 색인 구조인 GC-트리를 제안한다. GC-트리는 밀도 함수에 기초하여 데이타 공간을 적응적으로 분할하고, 색인 구조를 동적으로 생성한다. 이러한 특성을 갖는 GC-트리는 군집화된 고차원 이미지 데이타 검색에 훌륭한 성능을 나타낸다. With the proliferation of multimedia data, there is an increasing need to support the indexing and retrieval of high-dimensional image data. Although there have been many efforts, the performance of existing multidimensional indexing methods is not satisfactory in high dimensions. Thus the dimensionality reduction and the approximate solution methods were tried to deal with the so-called dimensionality curse. But these methods are inevitably accompanied by the loss of precision of query results. Therefore, recently, the vector approximation-based methods such as the VA-file and the LPC-file were developed to preserve the precision of query results. However, the performance of the vector approximation-based methods depend largely on the size of the approximation file and they lose the advantages of the multidimensional indexing methods that prune much search space. In this paper, we propose a new index structure called the GC-tree for efficient similarity search in image databases. The GC-tree is based on a special subspace partitioning strategy which is optimized for clustered high-dimensional images. It adaptively partitions the data space based on a density function and dynamically constructs an index structure. The resultant index structure adapts well to the strongly clustered distribution of high-dimensional images.

COVA : 내용 기반 강의 검색을 지원하는 원격 학습 시스템

차광호(Guang-Ho Cha) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.2

인터넷, 데이타베이스, 멀티미디어 기술의 복합적인 영향으로 교육과 학습의 형태가 크게 변하고 있다. 그러나 강의 내용을 효과적으로 관리하고 검색할 수 있는 시스템과 도구의 부족으로 원격 학습은 크게 효과적이지 못하다. 이 논문은 대용량 강의 데이타베이스에서 사용자가 내용에 기반하여 관심있는 강의 부분만 발췌하여 접근할 수 있도록 하는 프로토타입 시스템 COVA를 소개한다. COVA는 원격 학습에서 내용 기반 강의 검색을 위한 다음과 같은 새로운 기법을 포함한다: (1) 강의 내용을 표현하기 위한 XML 기반의 준구조적(semistructured) 데이타 모델; (2) XML 강의 데이타베이스의 구조적 요약, 즉, 스키마 추출 기법; (3) 원하는 강의 부분의 빠른 탐색을 위한 색인 기법. Education and training are expected to change dramatically due to the combined impact of the Internet, database, and multimedia technologies. However, the distance learning is often impeded by the lack of effective tools and system to manage and retrieve the lecture contents effectively. This paper introduces a prototype system called COVA that enables remote users to access specific parts of interest by contents from a large lecture database. COVA includes several novel techniques to achieve the content-based lecture retrieval in distance learning: (1) The XML-based semistructured model to represent lecture contents; (2) The technique to build structural summaries, i.e., schemas, of XML lecture databases; (3) Index structures to speed up the search to find appropriate lecture contents.

멀티미디어 데이타베이스에서 최근접 질의의 성능평가에 관한 분석 모델

이주홍,차광호,김형주,정진완(Ju-Hong Lee),Guang-Ho Cha,Hyoung-Joo Kim,Chin-Wan Chung 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.7

다차원 색인 트리를 이용하는 최근접 질의는 멀티미디어 데이타베이스템에서 자주 사용되는 중요한 질의 형식으로서 그 성능 분석은 질의 성능 개선을 위해 중요하다. 지금까지 다차원 트리에서의 질의 성능 분석 모델에 관한 대부분의 연구는 R 트리와 같은 특정 트리에서의 범위 질의에 대한 분석만을 주로 다루고 있었으나 최근 다차원 색인 트리에서 최근접 질의에 대한 성능 모델[1]이 발표되었다. 그러나 이 모델은 1-최근접 질의만을 다루고 있다. 본 논문에서는 다차원 색인 트리에서 일반적인 k-최근접 질의의 성능 분석 모델을 제시한다. 이 모델은 다차원 색인 트리의 종류나 k-최근접 질의 처리 알고리즘의 종류에 관계 없이 적용되는 모델이다. 모델의 기본 개념으로서 지역 평균 볼륨과 가변 밀도 함수의 개념을 소개한다. 본 모델의 이점은 다음과 같다: 임의의 데이타 분포를 가진 데이타 집합에 대해서도 적용 할 수 있고, 1-최근접 질의뿐 아니라 k-최근접 질의에서도 잘 적용되며, 색인 트리에 저장된 데이타로 곧바로 분석하므로 시간이 많이 소요되는 시뮬레이션 없이 빠르게 분석할 수 있다. 본 모델의 정확성을 평가하기 위해서 여러 가지 분포의 데이타 집합에 관하여 실험하였다. 실험 결과는 저차원 또는 중차원 데이타 집합에 대하여 데이타의 분포에 관계없이 정확한 결과를 보여주고 있다. The k-nearest neighbor query in multidimensional index tree is one of the most frequently used query types in multimedia databases. It is important to analyze the performance of the k-nearest neighbor query for its performance improvement. Until now, most of the analytic models are restricted to a particular type of the index tree, for example, the R-Tree and they concentrate on the analysis of the range query. Recently, a cost model [1] was reported for nearest neighbor queries. However, the model considered only 1-nearest neighbor queries rather than k-nearest neighbor queries. In this paper, we present an analytic model for the performance of the k-nearest neighbor query in multidimensional index trees. This model is independent of kinds of multi-dimensional index trees and k-nearest neighbor algorithms. As a basis of the model, we introduce the concept of the regional average volume and the varying density function. The advantages of our model are in particular as follows: It is applicable to any type of datasets with arbitrary distributions (uniform and non-uniform ones), works for the k- as well as 1-nearest neighbor query, and is a dynamic analysis method which enables a rapid analysis without requiring a time-consuming simulation of data. To estimate the accuracy of our model, we conducted a various range of experiments on the datasets with various distributions. The results show that our analytic model is accurate for the data sets with non-uniform distributions as well as uniform distributions in low and mid dimensions.