The signature file is an abstraction of documents, which has been studied as a storage structure for unformatted data. Since the size of the signature file is much smaller than that of a data file, it has been shown that the signature file can effectively work as a filter that immediately discards most non-qualifying documents for a given query. Although sequential organization of a signature file works well for a data file with a small size, its performance becomes a problem when the size of a data file is large. Many organizations of a signature file can improve the performance based on a tree or hashing techniques for single processor systems.
There have also been many attempts to make the schemes run for parallel environment. The Hamming Filter shows good declustering performance for some partial match queries. It declusters a signature file by using the Linear Code Decomposition Method(LCDM) that is used for detecting and correcting errors while transmitting data. The LCDM yields practically no execution skew, if the data is not skewed. However, since the LCDM allocates signatures with the same suffix into the same processing node, it can not avoid data skew if many signatures have the same suffix. In addition, it has problems that make the LCDM difficult for parallelism such as non-scalability and non-determinism.
In this dissertation we have proposed two signature file declustering methods, called MIN-entropy, Inner-product respectively that overcome the problems in the LCDM. They decluster signature file dynamically based on the current status of signature allocation. Thus, the MIN-entropy and the Inner-product can cope with a variety of workloads and configurations. We have showed through the performance evaluation based on the statistical modeling that the MIN-entropy and the Inner-product give better retrieval performance than the LCDM for data sets with various distributions such as uniform distribution, normal distribution and exponential distribution. And we also have addressed the performance of signature insertion time by using asymptotic notation. It shows Inner-product method works well in a dynamic environment where insertions frequently occur.
Finally we summarize the results in a guide that provides information for selecting a signature file declustering method for a specific applications. We recommend the MIN-entropy for the environment where retrieval is main operation and insertion seldom occurs and scalability is important such as mesh, ring parallel systems. The Inner-product are highly recommended for the environment where insertion frequently happens and scalability is important like the MIN-entropy.'
다양한 응용분야에서의 정보 요구에 대한 빠른 증가와 더불어 효율적인 정보검색을 지원하기 위해 요약화일 방법에 관한 연구가 진행되었다. 요약화일은 데이터베이스에 있는 문서들을 요약화하여 별도의 파일로 저장한 후 문서 검객 시 필터로 사용되는 인덱스 구조로써 많은 정보 검색 시스템에 적용되어 왔다. 가능한 적은 부가저장 공간을 사용하여 텍스트, 이미지 등과 같은 비정형화된 데이터를 효과적으로 접근하기 위해 많은 요약화일 방법 개발되었으며, 데이터의 크기가 비약적으로 증가하면서 병렬 시스템을 이용한 요약화일 방법에 관한 연구가 활발히 진행 중이다.
병렬 처리 시스템을 이용하여 요약화일을 효율적으로 검색하기 위해서는 질의-내 병렬화가 가장 중요하다. 질의-내 병렬화를 이용한 질의 검색 시 질의 응답 시간을 최소화하기 위해서는 수행부하 편중이 발생하지 않는 요약화일 분산 기법이 요구된다. 선형코드분산기법(LCDM)은 기존 병렬 요약화일인 Hamming Filter의 분산기법으로 사용되며, 우수한 요약화일 분산 성능을 보인다. 그러나, 데이터 자체가 편중되어 있을 때는 부하 균등 분산 문제를 안고 있다. 더욱이, LCDM은 병렬 알고리즘에 필수적인 확장성(scalability)과 결정성(determinism) 등을 제공하지 못한다.
본 논문에서는 LCDM이 안고있는 문제점을 극복하며, 보다 우수한 분산 성능을 보장하는 요약화일 분산 기법인 MIN-entropy 기법과 Inner-product 기법을 제안한다. 제안된 두 가지 요약화일 분산 기법은 현재 병렬 노드에 분산된 요약들에 대한 통계치와 분산할 새로운 요약과의 이질도(signature difference)에 근거하여 동적으로 요약화일을 분산한다. 따라서 다양한 작업부하와 변화 가능한 병렬 구성 환경에서 우수한 요약화일 분산 성능을 보장한다. 시뮬레이션을 이용한 성능 평가를 통하여 MIN-entropy와 Inner-product 요약화일 분산 기법이 다양한 분포의 데이터에 대해서 또한 다양한 시스템 구성 환경에서 LCDM보다 우수한 분산 성능을 제공함을 보인다.
이때 MIN-entropy는 Inner-product 분산 기법에 비해 보다 균등한 요약화일 분산 성능을 나타낸다. 그러나 문서 삽입 시 MIN-entropy 요약화일 분산 기법이 Inner-product 요약화일 분산 기법에 비해 느린 처리 속도를 나타낸다. 따라서 MIN-entropy 분산 기법은 문서 검색이 주된 연산인 정적인 환경에 적합한 분산 기법인 반면 Inner-product 분산 기법은 문서의 삽입, 삭제 및 갱신이 빈번한 동적 환경에 적합한 분산 기법이다.
