項関係における高速検索手法
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,単一化(Unincation)を使って知識ベースの検索をするRBU(Retrieval By Unincation)演算の高速化の手段として,項関係に対するインデクスの実現方法について報告する.項関係とは,変数も取り扱うことが可能な構造体である項(Term)を格納したテーブルである.また,関係代数演算に単一化を導入して項関係から適当な項を検索する演算をRBU演算と呼ぶ.項関係上のRBU演算により,大容量の知識ベースを対象とした各種の推論が行える.ここで提案するインデクスは,ハッシングとトライ(Trie)構造と呼ばれる一種の木構造を組み合わせてRBUにおける比較処理ならびにパックトラック処理の回数を抑えるものである.トライ構造によるインデクスの効果を高めるため,項をLOSRのセル構造で表現し,FIFOを用いてLOSRの項どうしを単一化するアルゴリズムを示す.また,試作したプロトタイプの検索処理に要する時間を計測し,インデクスの検索処理における高速化の効果を確かめる特に,各種形態の項関係に対して,トライ構造とハッシングの組み合わせが有効であることを示す.さらに,挿入処理に要する時間を計測し,更新処理におけるインデクスの維持のためのオーバヘッドがわずかであることを示す.
- 一般社団法人情報処理学会の論文
- 1991-04-15
著者
関連論文
- 論理型プログラミング言語Prologによる知識ベース管理システム
- 並列推論マシンPIM/pのアーキテクチャ
- 並列推論マシンPIM/pの要素プロセッサにおける分岐機能の高速化のためのアーキテクチャ
- 並列推論マシンPIM/pのネットワーク
- 並列推論マシンPIM/pの概要
- 並列UnixOSの試作と評価
- Prologの動作特性に関する考察
- 大規模知識ベースマシン実験機の開発(4) : 単一化エンジンの評価
- 大規模知識ベースマシン実験機の開発(3) : 単一化エンジンの構成方式について
- 大規模知識ベースマシン実験機の開発(1) : 開発の背景と方針
- 大規模知識ベースマシン実験機の開発(2) : ハードウェアシミュレータ
- 実時間GCの実現方式と評価
- 並列推論マシンPIM/pの要素プロセッサのアーキテクチャ
- FGHC処理システムのメモリ使用特性と世代別ガーベジ・コレクション
- 密結合マルチプロセッサ上のKL1並列処理系の評価
- 項関係における高速検索手法
- 知識ベース指向の並列推論処理システム
- 知識ベース指向並列処理システム
- 項関係上での単一化検索を使ったホーン節推論アルゴリズム
- 知識ベース指向の並列推論処理システム
- 知識ベース指向並列処理システム
- 知識処理向き並列推論メカニズム
- 項インデクスによる知識検索の高速化
- 論理型言語によるメタ推論とその応用(情報の構造化と意味に関する研究)
- 論理データベース向きの知識同化方式の一提案(モデル表現とその構築に関する理論と実際の研究)
- 並列推論マシンPIM : 中期構想
- Lispマシン (「AIマシン」)