Incremental Updating Scheme of a Full-Text Index Structure for WWW Text Search Engines

IPSJ Web Site 4 Citations 9 References

Bibliographic Information

Other Title
  • WWW検索エンジンのためのインクリメンタルな全文検索インデックス更新方式
  • WWW ケンサク エンジン ノ タメ ノ インクリメンタル ナ ゼンブン ケンサク インデックス コウシン ホウシキ

Search this article

Description

suffix arrayはテキストの接尾辞のポインタを接尾辞の辞書順に並べたもので 任意の部分文字列検索を高速に行うことができる.しかし更新のオーバーヘッドが大きく 日本語の全文検索を行うWWW検索エンジンにsuffix array を用いるには 頻繁に起こる更新によるオーバーヘッドが問題となる.本論文ではsuffix array の効率的な更新方法を提案する.この方式では 既存の巨大なsuffix array はすぐには更新せず 差分のテキストを元に差分suffix array を作る.検索は複数のsuffix array 全てに対して行い それらの結果をマージする.もとのsuffix array と差分suffix array をマージすることにより検索処理の際のマージオーバヘッドを軽減する.suffix array を使ったWWW検索エンジンを実装して実験を行い 提案方式の有効性を検証した.

A suffix array is a full-text index data structure, and is an array of pointers to lexicographic-ordered suffixes of text data. A suffix array is efficient for retrieving any substring of text, but requires a lot of overhead for updating it. In general, constant update operations are required in Web search engines, so the development of an efficient updating technique for suffix arrays is an important research issue. In this paper, we propose an efficient updating scheme of suffix arrays. The scheme is based on the following two ideas. First, instead of maintaining a single large suffix array, several small differential suffix arrays are created when new text data are obtained. At the processing of a retrieval operation, all the suffix arrays are retrieved and the retrieved results are merged into one. Second, when the number or the amount of differential suffix arrays exceeds the predetermined threshold, the differential suffix arrays are merged into one. We conducted experiments using an implementation and real WWW data and we verified the effectiveness of the proposed scheme.

Journal

Citations (4)*help

See more

References(9)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top