【課題】カップルドノードツリーを応用した検索手法において、重複キーの取り扱いを可能とする。
【解決手段】最後尾のキーをユニークキーとする複数のキーをキー列として組み合わせてインデックスキーとし、検索キーは複数のキーをキー列として組み合わせ、キー列の最後尾のキーがユニークな検索キー列とする。ブランチノードに、ビット列検索を行う検索キー列中の、ビット列比較をするキーの位置情報を示す第１の弁別位置とそのキーの第２の弁別位置を持たせ、またリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含む。検索キー列からブランチノードの第１の弁別位置のキーを取り出し、該キーの第２の弁別位置のビット値に応じてリンク先のノート対の一方のノードにリンクすることをインデックスキーと対応付けられたリーフノードに至るまで行いインデックスキーを検索する。 （もっと読む）

【課題】既存のデータベースのインデックスキーに対してそれと置き換えられる新しいデータベース用のインデックスキーが供給されたときに、効率よくデータベースのインデックスキーの更新を行う。
【解決手段】旧データのインデックスキーをリーフノードのインデックスキーとして格納したカップルドノードツリーから新データのインデックスキーにより削除処理を行って挿入キーと削除キーからなる新データと旧データの差分データを作成し、旧データのインデックスキーをリーフノードのインデックスキーとして格納したカップルドノードツリーに、差分データから取り出した削除キーと挿入キー削除処理と挿入処理を行って新データを作成する。 （もっと読む）

【課題】カップルドノードツリーを応用した高速なマージソート手法を実現する。
【解決手段】ソート済みのビット列からなるキーを格納した複数のソート済みキー記憶領域からそれぞれ最小あるいは最大のキーを取り出すとともに、取り出し元であるソート済みキー記憶領域を識別する処理元識別子を付加してマージ用のカップルドノードツリーを生成し、カップルドノードツリーの最小値あるいは最大値検索によるキーのマージ済みキー記憶領域への書き出しと削除処理、及び、ソート済みキー記憶領域からキーを取り出しての挿入処理を繰り返し実行することにより、マージソートを実現する。 （もっと読む）

【課題】記憶容量が小さく検索速度が高速でデータメンテナンスの容易なビット列検索装置を提供する。
【解決手段】インデックスキーの集合のインデックスキーを検索キーとしてリーフノードを検索し、リーフノードに至るリンク経路のブランチノードとリーフノードが格納された配列番号をスタックに格納し、検索キーとリーフノードに含まれるインデックスキーの間で大小比較とビット列比較をし、ビット列比較で異なるビット値となる先頭のビット位置とスタックに格納されているブランチノードの弁別ビット位置の相対的位置関係で挿入するインデックスキーを含むリーフノードのノード対の挿入位置を決定し、大小関係で挿入するインデックスキーを含むリーフノードがノード対のどちらのノードかを決定することを、インデックスキーの集合に含まれるインデックスキーについて繰り返して生成したカップルドノードツリーを用いる。 （もっと読む）

【課題】ドントケアビットを扱うのに好適な検索方法を提供する。
【解決手段】カップルドノードツリーはルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなる。ブランチノードは、ドントケアビットと有意ビットを識別するよう符号化されているビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含む。リーフノードは、符号化された／されていない状態のビット列からなるインデックスキーを含む。ブランチノードにおいて弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のいずれかのノードにリンクすることを順次リーフノードに至るまで繰り返し、必要に応じてリーフノードに至る経路を遡ることにより、ドントケアビットを考慮した検索が行われる。 （もっと読む）

【課題】カップルドノードツリーを検索対象とする最長一致／最短一致検索の方法を提供する。
【解決手段】カップルドノードツリーは、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対とからなる。ブランチノードは検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す情報を含み、リーフノードは検索対象のビット列からなるインデックスキーを含む。最長一致／最短一致検索キーを用いてカップルドノードツリーを検索し、検索結果のインデックスキーと最長一致／最短一致検索キーとの差分ビット位置と、検索時に記憶したルートノードからの検索経路上のブランチノードの弁別ビット位置との比較に基づいて、最長一致／最短一致ノードを決定する。 （もっと読む）

【課題】カップルドノードツリーを退避／復元する。
【解決手段】カップルドノードツリーはルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなる。ブランチノードはビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含む。リーフノードは検索対象のビット列からなるインデックスキーを含む。カップルドノードツリーのノードは深さ優先探索順に退避される。退避された順にノードを読み出し、ノードを復元すべき位置の位置情報をスタックに格納し、ブランチノードが続く間は子ノードを順次復元し、リーフノードが読み出されたらリーフノードを復元して、スタックを遡って次に復元すべきノードを決定する処理の繰り返しにより、カップルドノードツリーは復元される。 （もっと読む）

【課題】インデックスキーの長さが、予め決められていなくてもよく、長くても記憶領域の利用効率が良いようにする。
【解決手段】カップルドノードツリーはルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなる。ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す第一の位置情報を含み、リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報を含む。検索は、ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかもう一方のノードにリンクすることを順次リーフノードに至るまで繰り返すことにより行われる。 （もっと読む）

【課題】カップルドノードツリーの規模が大きくなっても、カップルドノードツリーを利用した処理の効率が低下することを少なくする手法を提供する。
【解決手段】基本検索や最大値あるいは最小値検索において、検索履歴を格納する探索経路スタックにノードの配置されたアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。 （もっと読む）

【課題】カップルドノードツリーを２つに分割し、また２つのカップルドノードツリーを結合する手法を提供する。
【解決手段】処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を求めてそれらインデックスキーを順次分割点となるインデックスキーまで削除し、削除したインデックスキーを処理先のカップルドノードツリーに挿入することによりカップルドノードツリーを分割する。一方のカップルドノードツリーを上記分割方法の処理元として削除処理を行い、他方を処理先として挿入処理を行ってカップルドノードツリーを結合する。 （もっと読む）