分割シグネチャファイル構成法とそれに基づく効率的検索手法の提案と評価

集合は複雑なデータ構造を支援するデータベース中において、頻繁に現れる基本的なデータ構造である。 そのため、各種のデータベース応用において集合値を効率良く支援する索引機構が要求される。 我々は、従来テキスト検索に用いられてきたシグネチャファイルを集合値検索機構として取り上げ、検索コストなど各種コストの評価を行なってきた。 本論文では大規模データベースを対象とした、水平分割と垂直分割の概念に基づく一般化された分割シグネチャファイル構成法である、 Partitioned Frame-Sliced Signature File(P-FSSF)の提案を行ない、集合値検索における検索、更新、格納の各コストの評価を行なう。 さらに、シグネチャファイル作成時のパラメタ設定について議論を行ない、P-FSSFの特殊な場合である Partitioned Bit-Sliced Signature File(P-BSSF)が多くの場合で最適になることを示す。

Design and Evaluation of Partitioned Signature File Organizations

Sets are primitive data objects and often appear in advanced databases which support complex data structures. Therefore, it is desirable to have access facilities which support set-valued object retrieval efficiently. In this paper, we propose the Partitioned Frame-Sliced Signature File(P-FSSF), which is based on horizontal and vertical partitioning, and estimate its retrieval, update and storage costs for set-valued object retrieval. Furthermore, we show that the Partitioned Bit-Sliced Signature File(P-BSSF), which is a special case of the P-FSSF, is an appropriate organization in general investigating the optimal selections of parameter values.