N-gram索引における複合検索条件の効率的な処理方法

IPSJ Web Site Web Site 5 Citations 19 References

Bibliographic Information

Other Title
  • N-gram サクイン ニ オケル フクゴウ ケンサク ジョウケン ノ コウリツテキ ナ ショリ ホウホウ
  • Efficient evaluation method of complex queries in n-gram indexing

Search this article

Description

N-gram索引のための単一検索語の効率的な処理方法として冗長n-gram法が提案されている。これは検索処理を、検索語から抽出される複数のn-gramを含む文書を検索する候補文書特定と、n-gram が文書中で連続位置にあるか調べる位置検査の2段階に分離し、位置検査をできる限り省略することで検索を高速化するものである。本論文では、位置検査の省略という考えをAND OR ANDNOT演算子に対して拡張し、複合検索条件処理を高速化する。さらに、AND OR演算子が入れ子になっている場合には、子ノード数に応じてOR標準形に変換することで検索処理を高速化する。新聞記事5年分を用いた評価により、これら手法の有効性が確認できた。

In the redundant n-gram method proposed for query processing in n-gram indexing, retrieval is accelerated by dividing the processing into two steps - one is finding the potential documents that have all the n-grams in the query word, and the other is checking the proximity constraints among the n-grams - and by reducing the unnecessary proximity check. This paper extends this method to complex queries with AND, OR, ANDNOT operators. In addition, we selectively convert complex queries with both AND and OR operators to the OR normal form according to the number of child nodes in these operators. The results of experiments using five years of newspapers showed that the extensions worked quite well.

Journal

Citations (5)*help

See more

References(19)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top