TWO-LEVEL N-GRAM INDEX STRUCTURE, METHOD OF BUILDING INDEX, METHOD OF PROCESSING QUERY, AND METHOD OF DERIVING INDEX

摘要

PROBLEM TO BE SOLVED: To build a two-level n-gram inverted index structure that reduces the size of an n-gram inverted index and improves the query performance by eliminating the redundancy of the position information that exists in the n-gram inverted index. SOLUTION: The inverted index comprises a back-end inverted index using subsequences extracted from documents as a term, and a front-end inverted index using n-grams extracted from the subsequences as a term. The back-end inverted index uses the subsequences of a specific length extracted from the documents to be overlapped with each other by n-1 (n: the length of n-gram) as a term, and stores occurrence position information in posting lists for the respective subsequences. The front-end inverted index uses the n-grams of a specific length extracted from the subsequences using a 1-sliding technique as a term, and stores position information of the n-grams occurring in the subsequences in posting lists for the respective n-grams. COPYRIGHT: (C)2007,JPO&INPIT