The n-gram inverted index has two major advantages: language-neutral and error-tolerant. Due to these advantages, it has been widely used in information retrieval or in similar sequence matching for DNA and protein databases. Nevertheless, the n-gram inverted index also has drawbacks: the size tends to be very large, and the performance of queries tends to be bad. In this dissertation, we propose a new index structure that solves these drawbacks.
In the first part of this dissertation, we propose the two-level n-gram inverted index(simply, the n-gram/2L index) that significantly reduces the size and improves the query performance while preserving the advantages of the n-gram inverted index. The proposed index eliminates the redundancy of the position information that exists in the n-gram inverted index. The proposed index is constructed in two steps: 1) extracting subsequences of length m from documents and 2) extracting n-grams from those subsequences. We formally prove that this two-step construction is identical to the relational normalization process that removes the redundancy caused by a non-trivial multivalued dependency. The n-gram/2L index has the following excellent properties: 1) it significantly reduces the size and improves the performance compared with the n-gram inverted index with these improvements becoming more marked as the database size gets larger; 2) the query processing time increases only very slightly as the query length gets longer. Experimental results using databases of 1GBytes show that the size of the n-gram/2L index is reduced by up to 1.9∼2.4 times and, at the same time, the query performance for exact string matching is improved by up to 13.1 times compared with those of the n-gram inverted index.
Approximate string matching is one of the major applications of the n-gram inverted index. It is defined as finding all the occurrences of a query string in a text database allowing a specified number of errors. Approximate string matching based on the n-gram inverted index(simply, n-gram Matching) has been widely used. It has a major advantage of being scalable for large databases because it is not a main memory algorithm. Nevertheless, n-gram Matching also has drawbacks: the query performance tends to be bad, and many false positives occur when a large number of errors are allowed.
In the second part of this dissertation, we propose an inverted index structure, which we call the n-gram/2L-Approximation index, that improves on these drawbacks. The n-gram/2L-Approximation index is an adaptation of the n-gram/2L index for approximate string matching. Inheriting the advantages of the n-gram/2L index, the n-gram/2L-Approximation index reduces the size of the index and improves the query performance significantly compared with the n-gram inverted index. In addition, the n-gram/2L-Approximation index reduces false positives compared with the n-gram inverted index when a large number of errors are allowed. We perform extensive experiments using the text and protein databases. Experimental results using databases of 1GBytes show that the n-gram/2L-Approximation index reduces the index size by up to 1.8 times and, at the same time, improves the query performance by up to 4.2 times compared with those of the n-gram inverted index.
In summary, we have proposed new index structures that improve the n-gram inverted index. For exact string matching, we have proposed the n-gram/2L index that significantly reduces the size and improves the query performance compared with the n-gram inverted index. For approximate string matching, we have proposed the n-gram/2L-Approximation index, which is an adaptation of the n-gram/2L index. We have verified the effectiveness of the proposed indexes by extensive experiments. We believe that the proposed indexes are novel data structures that are capable of replacing the n-gram inverted index in many applications such as information retrieval and similar sequence matching in bioinformatics.
n-gram 기반 역색인(간단히 n-gram 역색인)은 언어 중립적(language-neutral)이고 에러 허용적인(error tolerant) 장점들로 인해 복잡한 언어적인 지식을 필요로 하는 일부 아시아권 언어에 대한 정보 검색이나 단어의 개념이 명확하지 않은 단백질과 DNA의 시퀀스의 근사 문자열 매칭에 유용하게 사용되고 있다. 그러나, n-gram 역색인은 색인의 크기가 크고 질의 처리 시간이 오래 걸리는 등 공간적, 시간적 비용이 크다는 단점을 가지고 있다. 이에 본 학위논문에서는 n-gram 역색인의 장점을 그대로 유지하면서 단점을 개선한 새로운 색인 구조를 다룬다.
본 학위논문의 첫 번째 파트에서는 n-gram 역색인에 비해 색인의 크기를 줄이고 질의 처리 성능을 크게 향상시킨 2단계 n-gram 역색인(간단히 n-gram/2L 역색인)을 제안한다.
n-gram/2L 역색인은 n-gram 역색인에 존재하던 위치 정보의 중복을 제거한다. 이를 위해 문서로부터 subsequence들을 추출하고, 그 subsequence들로부터 n-gram을 추출하여 2단계로 역색인을 구성한다. 이러한 2단계 n-gram 역색인의 구성 방법은 이론적으로 유의미 다치 종속성(non-trivial multivalued dependency)이 존재하는 릴레이션을 정규화(normalization)하여 중복을 제거하는 것과 동일하며, 본 학위논문에서는 이를 정형적으로 증명한다. n-gram/2L 역색인은 데이타의 크기가 커질 수록 n-gram 역색인에 비해 색인 크기가 줄어들며 질의 처리 성능이 향상되고, 질의 문자열의 길이가 길어질 때 질의 처리 시간의 증가율이 n-gram 역색인에 비해 더 작다는 좋은 특성을 가진다. 1GByte의 텍스트 데이타와 단백질 시퀀스 데이타에 대한 실험을 통하여, n-gram/2L 역색인은 n-gram 역색인에 비해 최대 1.9∼2.4배 더 작은 크기를 가지면서, 동시에 exact 문자열 매칭 질의 처리 성능은 3∼18 범위의 길이를 가지는 질의들에 대해 최대 13.1배 향상시킴을 보였다.
n-gram 역색인의 주요 응용들 중 하나인 근사 문자열 매칭(approximate string matching)은 질의 문자열과 에러 허용치 내에서 매치(match)하는 문자열들을 포함하는 문서들과 그 문자열들의 위치들을 찾는 문제이다. 색인을 사용한 근사 문자열 매칭 중 n-gram 역색인을 사용한 근사 문자열 매칭 방법(간단히 n-gram Matching)은 메인 메모리 알고리즘이 아니기 때문에 대용량 데이타베이스에 대해서도 사용할 수 있다는 장점을 가지고 있어 널리 사용되고 있다. 그러나, n-gram Matching은 질의 처리 성능이 좋지 않고, 에러 허용치가 크게 주어지는 경우에는 착오해답이 많이 발생하는 단점들을 가지고 있다.
본 학위논문의 두 번째 파트에서는 n-gram/2L 역색인을 근사 문자열 매칭을 위해 확장한 n-gram/2L-Approximation 역색인을 제안한다. n-gram/2L-Approximation 역색인은 n-gram/2L 역색인의 장점을 그대로 가지기 때문에 n-gram 역색인에 비해 색인 크기를 크게 감소시키고 질의 처리 성능을 향상시킨다. 또한, 에러 허용치가 큰 경우에도 n-gram 역색인에 비해 착오해답을 더 적게 발생시키는 바람직한 특성을 가진다. 1GByte의 텍스트 데이타와 단백질 시퀀스 데이타에 대한 실험을 통하여, n-gram/2L-Approximation 역색인은 n-gram 역색인에 비해 최대 1.8배 더 작은 크기의 색인을 유지하면서, 동시에 질의 처리 성능은 20∼100 범위의 길이를 가지는 질의들에 대해 최대 4.2배 향상시킴을 보였다.
요약하여, 본 학위논문에서는 n-gram 역색인을 개선한 새로운 색인 구조들을 제안하였다. n-gram 역색인에 존재하는 위치 정보의 중복을 제거함으로써 색인의 크기를 크게 줄이고 질의 처리 성능을 향상시킨 n-gram/2L 역색인을 제안하였다. 또한, 근사 문자열 매칭을 위해서 n-gram/2L 역색인을 확장한 n-gram/2L-Approximation 역색인을 제안하였다. 다양한 실험을 통해 제안한 색인 구조들의 유효성을 검증하였다. 제안한 색인 구조들은 정보 검색이나 바이오인포메틱스에서의 유사 시퀀스 매칭 등의 응용들에서 기존 n-gram 역색인을 대체하여 유용하게 활용될 수 있는 색인 구조들이라고 사료된다.
