With rapid increase of information requirements from various application areas, there has been much research on the efficient information retrieval. An approach widely advocated for the efficient information retrieval is to use signature file method. The signature file is an abstraction of information and has been applied in many proposals of information retrieval systems. Many signature file methods have been developed to efficiently access unformatted data with low storage overhead. Some of them are for static environments and others are for dynamic environments. In general, however, all the previous methods have various problems such as inability to support range queries, lack of handling synonyms and so on. In addition, the static two-path methods that achieve good retrieval performance over other static methods suffer from path selection overhead. The previous dynamic methods also have the problem of serious performance degradation for light query signature weights.
In this dissertation we investigate various signature-based file organizations that work efficiently in various information retrieval applications. We first propose a new hybrid access method that employs signature clustering. Our proposed hybrid method overcomes various problems such as inability to support range queries, path selection overhead and lack of handling synonyms. A clustering method that has been extensively examined in the literature of library science is promising one to deal efficiently with signature files. However, works on clustering methods for clustering document signatures have not been made in the past. We develop two new heuristic clustering methods for signature files, called CBS and CWD. The CBS and CWD alleviate the problems of the previous clustering methods by grouping document signatures instead of documents. The clustering effects of CBS and CWD are tested by using 20,000 real library documents. We apply CBS and CWD to our hybrid method to improve its retrieval performance. We derive analytic performance evaluation models of our hybrid access method using clustering methods CBS and CWD, and existing signature file methods in terms of retrieval time and storage overhead. Performance comparison based on the analytic models shows that our hybrid access method achieves high performance over other methods proposed earlier. We perform experiments using 10,000 and 100,000 library documents. We show through analytic cost models and experiments that our hybrid method that employs two clustering algorithms achieves good retrieval performance over other existing signature file methods.
We then propose a new dynamic signature file organization based on a frame sliced approach, called the hierarchical signature(HS) file. The HS file uses frame sliced approach to leaf node construction to improve a filtering effect of signature file. The HS file alleviates the problem of light query signature weights. We derive analytic performance evaluation models of the existing dynamic signature file methods and the proposed HS file in terms of retrieval time, storage overhead and insertion time. We also perform extensive experiments with various data distributions such as uniform, normal and exponential distributions. The relationships among various performance parameters are thoroughly investigated. We show through performance comparison based on analytic models and experiments that regardless of data distribution, the HS file significantly improves performance in both the retrieval time and the storage overhead over the other dynamic signature file methods proposed earlier.
Finally, we summarize the signature file implementation techniques with emphasis on their convenience for the multimedia applications processed under different conditions. Two groups of criteria for signature extraction methods and storage structures are presented for guidelines that can be used to select effective implementations for specific applications. They should allow designers to express specific characteristics of their applications. Based on the criteria, we provide best combination of extraction methods and storage structures that can outperform others for the most effective usage to a given operational environment.
다양한 응용분야에서의 정보 요구에 대한 빠른 증가와 더불어 효율적인 정보검색을 지원하기 위해 요약 화일 방법에 관한 연구가 진행되었다. 요약 화일은 데이타베이스에 있는 문서들을 요약화하여 저장한 화일로써 문서 검색시 필터 역할을 하며, 많은 정보검색 시스템에 적용되어 왔다. 가능한 적은 부가저장공간을 사용하여 텍스트, 이미지 등과 같은 비정형화된 데이타를 효과적으로 접근하기 위해 많은 요약 화일 방법들이 개발되었다. 이러한 요약 화일 방법들은 정적 방법들과 동적 방법들로 구분된다. 그러나 기존의 요약 화일 방법들을 범위 질의, 접두사를 갖는 부분 매치 질의, 동의어 처리 등과 같은 응용들을 지원하지 못한다. 또한, 다른 정적 방법들에 비해 좋은 검색 성능을 보이는 이경로 방법은 경로 선택 부담을 갖고 있다. 기존의 동적 요약 화일 방법들은 질의 요약의 가중치가 낮을 때 성능 저하가 심각하다.
본 논문에서는 첫째로, 다양한 정보검색 응용들에서 효율적으로 동작하는 기존의 요약 화일 방법들을 살펴보고 경험적 요약 결집을 사용하는 새로운 합성 접근 기법을 제안한다. 제안된 합성 접근 기법은 범위 질의, 동의어 처리 등과 같은 응용들을 지원하고 경로 선택 부담을 해결한다. 이러한 접근 방법이외에, 결집 방법들이 도서 검색 시스템에서 문서 데이타베이스를 효율적으로 처리할 수 있도록 폭넓게 연구되었다. 그러나 이러한 결집 방법들은 문서들에 속해있는 단어들의 유사도의 정도에 따라 유사한 문서들을 결집하기 때문에 삽입이 쉽지 않고 문서들을 결집하는데 많은 시간이 소요될뿐만 아니라 많은 부가 저장 공간을 사용하는 단점을 갖는다. 본 논문에서는 둘째로 기존 결집 방법들의 문제점을 해결할 수 있을 뿐만아니라 요약 화일 방법들의 검색 성능을 향상시킬 수 있는 경험적 요약 결집 방법인 CBS와 CWD를 제안한다. 제안된 CBS 방식과 CWD 방식의 결집 효과를 평가하기 위해, 20,000개의 실질적인 문서들을 사용하여 실험을 수행한다. 또한 제안된 합성 접근 기법의 검색 성능을 향상시키기 위하여 CBS 방식과 CWD 방식을 합성 요약 화일 방법에 적용한다. CBS 방식과 CWD 방식을 사용하는 합성 요약 화일 방법들과 기존의 정적 요약 화일 방법들의 검색 성능과 저장 공간 측면에서 분석적 성능 비용 모델을 개발한다. 분석적 비용 모델에 근거한 성능 비교를 통하여, 제안한 결집 방법을 사용하는 합성 접근 기법이 다른 기존의 요약 화일 방법들에 비해 다양한 환경에서 우수한 검색 성능을 보인다. 또한 10,000과 100,000개의 도서 문서들을 갖는 데이타베이스에서 실험을 수행한 결과, 분석적 비용 모델을 통한 성능 비교 결과와 매우 유사하였다.
최근의 많은 응용들은 삽입, 삭제 및 갱신 등을 효율적으로 수행할 수 있는 동적 정보 저장 구조를 요구하고 있다. 현재, 동적 환경을 위한 요약 화일(signature file)기법이 존재하고 있지만 그들은 질의 요약의 가중치가 낮은 경우에 심각한 성능 저하를 야기 시킨다. 본 논문에서는 세째로, 질의 요약의 가중치에 관계없이 좋은 성능을 보이는 동적 환경에 적합한 새로운 요약 화일 방법인 Hierarchical Signature(HS) 화일을 제안한다. 성능평가를 위해 기존의 동적 요약 방법들과 제안하는 HS 화일의 분석적 모델을 검색시간, 저장공간, 삽입시간 측면에서 제시하고 그 모델을 기반으로 그들의 성능을 비교한다. 또한 제안된 분석적 모델의 타당성을 제시하고 HS 화일의 특성을 분석하기 위하여 균일 분포, 정규 분포, 지수 분포와 같은 다양한 분포를 갖는 데이타를 사용하여 실험을 수행한다. 이 실험을 통하여 동적 요약 화일 방법들에 관한 성능을 여러 환경에서 비교하고 분석한다. 분석적 비용 모델과 실험을 통하여, 제안된 HS 화일이 기존의 동적 요약 화일 방법들에 비해 데이타 분포에 관계없이 검색 시간과 저장 공간면에서 성능이 상당히 우수함을 보인다.
마지막으로, 다른 환경하에서 처리되는 멀티미디어 응용들에 각 요약 추출 방법과 각 저장 구조들의 적합성 정도를 요약한다. 이를위해 요약 추출 방법과 저장 구조를 위한 각각의 비교 기준들을 제시한다. 이와같은 기준에 따라 각 방법들의 적합성 정도를 제안하여 특정 응용을 위한 효과적인 방법들을 선택할 수 있도록 한다. 또한 주어진 연산 특성에 가장 효과적인 추출 방법과 저장 구조의 조합을 제안한다.