情報蓄積検索方法及び情報蓄積検索プログラム

発明者： , ,
出願人/特許権者：
代理人 (2件)：志賀正武 , 村山靖彦
公報種別：公開公報
出願番号（国際出願番号）：特願2010-031795
公開番号（公開出願番号）：特開2011-170461
出願日： 2010年02月16日
公開日（公表日）： 2011年09月01日
要約：

【課題】多種多次元のタプルに対する検索において効率的な検索を可能とする。【解決手段】蓄積検索対象の情報の単位であるタプルから検索キーがインデックス化され検索木が構築されるものであり、インデックスの構築において、インデックスのノードに子ノードまたはタプル識別子とキーからなるエントリXを挿入する際、操作対象ノードにおいて、「操作対象ノードがすでに含む既存エントリに対し、エントリXを挿入した場合のペナルティ」が例えば最も小さい既存エントリを選出する場合に、ペナルティが、操作対象ノードがすでに含む既存エントリAに対し、エントリBを挿入する際、エントリBを挿入する前のエントリAと、挿入した後のエントリAとを比べた場合の、エントリAが検索される確率に対応した値の増分を示す値として定義される、情報蓄積検索方法である。【選択図】図13

請求項（抜粋）：

蓄積検索対象の情報の単位であるタプルは、属性-値の組の並びを少なくとも含む1以上の長さを有するものであり、該属性の種類や該並びの長さが同じまたは異なる1つ以上の該タプルが複数記憶されるものであり、該タプルから検索キーがインデックス化され検索木が構築されるものであり、該検索木はノードを階層的に有する構成であり、該ノードの内最下層のリーフノードはエントリとして該タプルを識別するタプル識別子とキーを有するものであり、該ノードの内該リーフノードより上位のインナーノードはエントリとして下位ノードである子ノードの位置情報であるポインタとキーを有するものであり、該インデックスの構築において、エントリをノードに挿入する際、 1つの挿入すべきエントリXと、該エントリを挿入すべきレベル数L(前記リーフノードを0として階層が上がるごとに1増える階層数)が与えられた際、はじめにルートノードを操作対象ノードとし、操作対象ノードにおいて、「該操作対象ノードがすでに含む既存エントリに対し、該エントリXを挿入した場合のペナルティ」に基づいて1つの該既存エントリを選出し、該既存エントリに含まれるポインタが指し示す子ノードを次の操作対象ノードと選定し、該次の操作対象ノードのレベル数がLより大きい場合は、該次の操作対象ノードからさらに次の操作対象ノードを選定することを再帰的に繰り返し、該次の操作対象ノードのレベル数がLに到達した場合は、このノードを選択ノードに決定するステップと、前記選択ノードが許容できる最大数のエントリを持っていない場合において、前記選択ノードに対し、前記エントリXを追加するステップと、前記選択ノードが既に許容できる最大数のエントリを持っている場合において、前記エントリXを追加しつつ前記選択ノードの分割を行うステップと、前記分割を行った場合において、前記選択ノードの上位ノードのエントリを更新するステップと、を含むことを特徴とする情報蓄積検索方法。

IPC (2件)：

G06F 17/30 , G06F 12/00

FI (3件)：

G06F17/30 414A , G06F17/30 180D , G06F12/00 520A

Fターム (3件)：

5B075NK43 , 5B075NR12 , 5B082EA05

引用文献：

審査官引用 (4件)

Generalized Search Trees for Database Systems
時空間データベースインデックス正規化R*-treeの実装と性能テスト
RW-Tree:非軸直交一次元範囲検索のための索引手法

全件表示

前のページに戻る