シグネチャファイルによる集合値検索のコスト評価

概要

論文の詳細を見る
集合データは基本的なデータ構造であり,複数オブジェクトの部分構造としても頻繁に現れる.このため,集合値に関する検索条件を効率的に支援する索引機構は,先進的な応用分野を対象としたデータベースシステムにおいて重要なものとなる.筆者らは,テキスト検索で従来用いられてきたシグネチャファイルの手法を集合値検索に適用することを提案し,比較的小規模のデータベースを想定し,コスト評価や効率的な問い合わせ処理方式などの検討を行ってきた.本論文では,中規模データベースに対するシグネチャファイルの有用性の評価を行う.シグネチャファイルの構成手法としては,ビットスライストシグネチャファイル(bit-sliced signatue file, BSSF)を対象とし,入れ子型インデックス(nested index)を比較の対象とする.中規模データベースにおける検索コスト,記憶コスト,更新コストの評価を行い,小規模データベースにおける評価結果と比較する.また,中規模データベースにおけるシグネチャファイルの性能向上のためには,ビットスライストシグネチャファイルに圧縮を用いることが有効であると考え,ファイル圧縮時のコストについても評価を行い,その有効性を示す.
1995-02-15