DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Min-Soo | - |
dc.contributor.author | Whang, Kyu-Young | - |
dc.contributor.author | Lee, Jae-Gil | - |
dc.contributor.author | Lee, Min-Jae | - |
dc.date.accessioned | 2009-09-16T01:54:18Z | - |
dc.date.available | 2009-09-16T01:54:18Z | - |
dc.date.issued | 2008-11 | - |
dc.identifier.citation | VLDB Journal, Vol. 17, No. 6, pp. 1485-1507 | en |
dc.identifier.issn | 1066-8888 | - |
dc.identifier.uri | http://hdl.handle.net/10203/11243 | - |
dc.description.abstract | As the amount of text data grows explosively, an efficient index structure for large text databases becomes ever important. The n-gram inverted index (simply, the n-gram index) has been widely used in information retrieval or in approximate string matching due to its two major advantages: language-neutral and error-tolerant. Nevertheless, the n-gram index also has drawbacks: the size tends to be very large, and the performance of queries tends to be bad. In this paper, 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 by using the relational normalization theory. We first identify that, in the (full-text) n-gram index, there exists redundancy in the position information caused by a non-trivial multivalued dependency. The proposed index eliminates such redundancy by constructing the index in two levels: the front-end index and the back-end index. We formally prove that this two-level construction is identical to the relational normalization process. We call this process structural optimization of the n-gram index. The n-gram/2L index has excellent properties: (1) it significantly reduces the size and improves the performance compared with the n-gram 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 real databases of 1 GB 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 is improved by up to 13.1 times compared with those of the n-gram index. We also compare the n-gram/2L index with Makinen’s compact suffix array (CSA) (Proc. 11th Annual Symposium on Combinatorial Pattern Matching pp. 305–319, 2000) stored in disk. Experimental results show that the n-gram/2L index outperforms the CSA when the query length is short (i.e., less than 15–20), and the CSA is similar to or better than the n-gram/2L index when the query length is long (i.e., more than 15–20). | en |
dc.language.iso | en_US | en |
dc.publisher | Springer Verlag (Germany) | en |
dc.subject | Text search | en |
dc.subject | Inverted index | en |
dc.subject | n-gram | en |
dc.subject | Multivalued dependency | en |
dc.title | Structural optimization of a full-text n-gram index using relational normalization | en |
dc.type | Article | en |
dc.identifier.doi | 10.1007/s00778-007-0082-x | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.