Ｎ分木内部ノードの圧縮方法及び装置及びプログラム
【課題】 １つの比較キー（N分木のノードに設定される分岐判断の数値）のサイズを小さくする。
【解決手段】 本発明は、入力されたM個の整数列に対してN分木作成を行い、N分木をROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビットに縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納し、記憶手段からROOTノードを含むブロックを読み出し、入力された探索キーを初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する。
【解決手段】 本発明は、入力されたM個の整数列に対してN分木作成を行い、N分木をROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビットに縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納し、記憶手段からROOTノードを含むブロックを読み出し、入力された探索キーを初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、N分木内部ノードの圧縮方法及び装置及びプログラムに係り、特に、M個の整数列から任意の整数（探索キー）を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
探索対象となるM個の整数列は昇順に並んでおり、その整数列から探索キーと同じキー値を持つ整数が存在するかの判定を行う。探索処理は、最上位ノードに位置するROOTノードから順にノード内の比較キーと探索キーの比較処理を繰り返し、中間位置に存在するBRANCHノードを通過し、探索キーに対応する（整数列への位置情報を保持する）LEAFノードを計算し、最終的に探索キーの整数列内の有無を判定する。図９の例では、探索キーは"３２３"であるため、まず、ROOTノードの最左端の矢印を指すBRANCHノード（"２０１"、"３９３"）へ移動する。『"２０１"＜探索キー（"３２３"）＜"３９３"』であるため、BRANCHノード中間矢印の先にあるLEAFノードに移動する。最終的にLEAFノード内の探索キーと同じ比較キーが存在するため、この探索処理は成功と判定され、整数列内における"３２３"の位置情報が返却される。
【０００３】
M個の整数列の探索処理を高速化するためのN分木データ構造は『ポインタを利用するもの』（図１０）と『配列を利用するもの』（図１１）の２つある。前者の『ポインタを利用するもの』は図１０に示すように、BRANCHノードが探索キーの目的位置を特定するための（N-1）個の比較キーと、次のBRANCHノードを表すN個のポインタから構成される（例えば、特許文献１参照）。一方、後者の『配列を使用するもの』は、図１１に示すように、BRANCHノードが（N-1）個の比較キーのみで構成され（例えば、非特許文献１、２参照）、各BRANCHノードにおける比較結果から、次BRANCHノードへのオフセット数を算出し、移動する（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許０４３５１５３０号公報
【特許文献２】特開２００５−２３５２０９号公報
【非特許文献】
【０００５】
【非特許文献１】Changkyu K. et al.: FAST: fast architecture sensitive tree search on modern CPUs and GPUs, Proceedings of the 2010 international conference on Management of data (SIGMOD'10),2010.
【非特許文献２】Benjamin S. et al.: k-ary search on modern processors, Proceedings of the 19th International Workshop on Data Management on New Hardware, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
M個の整数列に対してN分木を構成した場合、N分木の高さは
【０００７】
【数１】
で表され、N分木内部ノード内の総比較キー数（Nkey）は初項（N-1）で、公比Nの等比級数となり、
【０００８】
【数２】
になる。N分木内部ノードの比較キーのデータサイズは、前述の従来技術の非特許文献１，２、特許文献２においては、N分木を構成する整数列と同じデータサイズ（このデータサイズをSバイトとする）になるため、整数列のデータサイズが４バイト（S=4）の場合は、内部ノードの総サイズはNkey×４バイトになり、８バイト（S=8）の場合は、Nkey×８バイトになる。このN分木の総ノードサイズは、整数列が少ない（Mが小）場合には問題にならないが、センサ情報や、アクセスログデータなど大規模データ内の整数列に対するN分木を構成する際、N分木の内部ノードサイズが非常に大きくなる問題がある。
【０００９】
本発明は、上記の点に鑑みなされたもので、１つの比較キー（N分木のノードに設定される分岐判断の数値）のサイズを小さくすることが可能なN分木内部ノードの圧縮方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明は、M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、
入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、
前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、を有する。
【００１１】
また、上記の初期化手段は、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する手段を含む。
【００１２】
また、上記の探索キー処理手段は、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、を含む。
【００１３】
また、上記の探索キー処理手段は、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む。
【発明の効果】
【００１４】
上記にように、N分木内部ノード内の単体比較キーが８×Sビットから、８×Tビットで表現可能となるため、N分木の全内部ノードサイズはNkey×SバイトからNkey×Tバイトとなり、総サイズが約T/S（メタデータ要の領域は相対的に小さいため無視した場合）になる。より具体的には、M個の整数列を４バイト（S＝4）として、Tを１とした場合、N分木の全内部ノードサイズが変換前の約２５％になる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態における装置構成図である。
【図２】本発明の一実施の形態におけるN分木初期化部における部分木への分解と幅優先並び替えを示す図である。
【図３】本発明の一実施の形態における四則演算を利用した比較キー縮退変換処理の具体例である。
【図４】本発明の一実施の形態における部分木内の比較キー変換処理モジュールの具合例の１つとしてのフローチャートである。
【図５】本発明の一実施の形態における探索処理のズレの問題(T=1)を示す図である。
【図６】本発明の一実施の形態における正しい位置への補正処理を示す図である。
【図７】本発明の一実施の形態におけるN分木初期株の処理のフローチャートである。
【図８】本発明の一実施の形態における探索キー処理部の処理のフローチャートである。
【図９】N分木の構成図である。
【図１０】ポインタを利用したN分木のデータ構造である。
【図１１】配列を利用したN分木のデータ構造である。
【発明を実施するための形態】
【００１６】
以下図面と共に、本発明の実施の形態を説明する。
【００１７】
図１は、本発明の一実施の形態における装置構成を示す。
【００１８】
同図に示す装置は、N分木初期化部１０、探索キー処理部２０、N分木記憶部３０から構成され、N分木初期化部１０にはM個の整数列を入力する整数列入力装置１が、探索キー処理部２０には探索キーを入力する探索キー入力装置２及び結果出力装置３が接続されている。
【００１９】
以下に上記の構成における処理を説明する。
【００２０】
N分木初期化部１０は、探索キーの高速な処理を行うために、整数列入力装置１から入力されたM個の整数列に対してN分木（Nはシステムパラメータ）作成を行う。N分木初期化部１０では、整数列入力装置１から入力された昇順並び替え済みのN分木対象整数列から従来通りのN分木を作成する。その後、図２に示すように、N分木を高さH毎の部分木に分解し、幅優先で部分木を並び替え、内部の比較キーを昇順に配列配置することでN分木のデータ構造（ブロック）とする。ブロックに変換する際に、ブロック毎の比較キーの表現空間を８×Sビットから８×Tビット（Tは本発明における任意のパラメータで、S＞Tとする）に縮退する点が本発明の特徴である。詳細については図７、図８で詳述する。部分木内の比較キー変換処理の具体例として、四則演算を利用して比較キー縮退変換処理の例を図３に示す。
【００２１】
探索キー処理部２０は、探索キー入力装置２から入力された探索キーが、整数列入力装置１から入力された整数列内に含まれているかどうかを判定し、その位置情報を返す。探索の際に、比較を行う各ブロック内に含まれているメタデータ（ブロック内の比較キーを変換するために利用した情報）を利用して、探索キーをそのブロック毎で比較可能な値に変換した後に、ブロック内の比較キーとの比較を行う。探索を行うべき次ブロックの決定を行い、次の部分木に移動しながら、目的位置までの探索処理を行う。探索処理においては、部分木内の比較キーを圧縮する際に発生する異なる比較キーが同一の値に変換されてしまう問題（具体例として図４のフローチャートを利用した、この問題の説明を図５に示す）に対処する必要（表現空間を縮退したことによるペナルティ）がある。より具体的には、異なる比較キーが同一の値に変換されてしまうことにより、本来探索すべき部分木からの"ズレ"が発生する点である。このズレに関しては、図６に示すように、LEAFノードに到着した際に、探索キーと内部の比較キーを比較することで、ズレを修正する処理に加える。
【００２２】
次に、N分木初期化部１０の詳細な処理を説明する。
【００２３】
図７は、本発明の一実施の形態におけるN分木初期化部の処理のフローチャートである。
【００２４】
ステップ５００） 整数列入力装置１から昇順のM個の整数列が入力される。
【００２５】
ステップ５０５） 入力されたM個の整数値に対して、従来技術の方法によりN分木を作成し、通常のN分木のデータ構造を得る。
【００２６】
ステップ５１０） ステップ５０５で得られたN分木を、図２に示すようにROOTノードから順に高さH毎の部分木に分解して、幅優先に並び替える。
【００２７】
ステップ５１５） ｉを値１で初期化する。
【００２８】
ステップ５２０） N分木を高さHごとに分解したS個の部分木からｉ番目の部分木を取り出す。
【００２９】
ステップ５２５） 『部分木内の比較キー変換処理』（例えば、図４のフローチャート）モジュールを利用し、ｉ番目の部分木内に含まれる比較キーを変換してブロック化する。この変換処理において、各部分木内比較キーの表現空間を８×Sビットから８×Tビットに縮退する任意の変換処理を行う。この縮退変換処理の１つの具体例として四則演算を利用した変換手法がある。この手法については後述する。
【００３０】
ステップ５３０） ステップ５２５で変換処理され圧縮されたブロックが入力されると、当該入力されたブロックをFIFOバッファ（図示せず）に格納する。
【００３１】
ステップ５３５） ｉに１を加算する。
【００３２】
ステップ５４０） FIFOバッファ（図示せず）内の全てのブロックを順に読み出し、N分木記憶部３０に格納する。
【００３３】
以下に、上記のステップ５２５の縮退変換処理について図４を用いて説明する。
【００３４】
ステップ６００） N分木初期化部１０において、部分木の比較キー集合が入力されると、部分木の比較キーを昇順に以下のように並び替える。
【００３５】
V1(Vmin)，V2,…，ＶN-1(Vmax)
ステップ６０５） 比較キー集合内の全ての比較キーを、比較キー内最小値Vminで減算し、ｘ（補正項）を加算する。補正項ｘは部分木内の最小値を"１"に対応付けるために存在し、図３に示すように、比較キーを変換後に（"greater than"比較処理を想定）左端の部分木への探索を可能にする。
【００３６】
ステップ６１０） 比較キー集合内の全ての比較キー（Vn−Vmin+ｘ）を、（Vmax−Vmin+ｘ）で割る。
【００３７】
ステップ６１５） 比較キー集合内の全ての比較キーに2８T(Tはシステムパラメータ)を掛け、小数点以下を切り捨てる。
【００３８】
上記のステップ６０５，６１０，６１５までの部分木内の比較キーは、
【００３９】
【数３】
で変換（T<Ｓ， Ｖ*nは右辺を四捨五入した値
【００４０】
【数４】
する。
【００４１】
ステップ６２０） 先頭にメタデータVmin、Vmaxを付与した変換処理後の昇順比較キーをブロックとして出力する。
【００４２】
次に、探索キー処理部２０の処理を図８のフローチャートに沿って説明する。
【００４３】
ステップ７００） 探索キー処理部２０は、探索キー入力装置２から探索キーが入力される。
【００４４】
ステップ７０５） Ｎ分木記憶部３０からROOTノードのブロックを読み出す。
【００４５】
ステップ７１０） 読み出したブロック内に含まれるメタデータ（ブロック内の比較キーを変換するために利用した情報）を読み出して、ブロック内の比較キーが変換処理された内容と同じ処理を探索キーに行い、変換処理された探索キーを出力する。
【００４６】
ステップ７１５） 変換処理された探索キーを利用して、例えば、「URL: http://www.geocities.jp/m_hiroi/light/abcruby13.html」に示される手法を用いて、ブロック内の比較キーと比較処理を行う。その後、次に読み出すブロックを決定し、Ｎ分木記憶部３０から次に探索を行うべきブロックを読み出す。次に読み出すブロックがLEAFノードである場合はステップ７２０に移行する。LEAFブロックで無い場合はステップ７１０に移行する。
【００４７】
ステップ７２０） LEAFノードを含むブロック情報を取得し、Ｎ分木内部ノードの比較キーの変換処理（図５）により発生する探索位置の"ズレ"の問題に対処するために、最初に探索されたLEAFノードが探索キーに対応する正しいLEAFノードかどうかをLEAFノード内の比較キーを利用することで判定する。正しくない場合には、本来探索されるべきLEAFノード位置を、LEAFノードを順に読み込むことで図６に示すように補正する。
【００４８】
ステップ７２５） LEAFノード内に、探索キーと同じ比較キーを持つものがあるかを調べ、もしある場合は、その比較キーに対応する整数列内のポインタを結果出力装置３に出力する。無い場合には、整数列には探索キーと同じ値を持つもの無しとして出力する。
【００４９】
上記のように、本発明では、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えた列からN分木の内部データ構造であるブロックに変換する際（ステップ５２０〜ステップ５３５）、ブロックごとの比較キーの表現空間を縮退する処理（ステップ５２５）を行うことが特徴である。なお、H(高さ)=1としてステップ５２５の部分木内の比較キー変換処理を行わない場合が従来技術に対応する。本発明のような比較キーの変換を行うことで、探索キーと比較可能な状態で表現空間（０〜２S−１から０〜２T-1-１)を縮退させ、比較キーを構成するN分木のノード圧縮を可能とする。
【００５０】
なお、上記の図１に示すN分木内部ノード圧縮装置の構成要素の動作をプログラムとして構築し、N分木内部ノード圧縮装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５２】
１ 整数列入力装置
２ 探索キー入力装置
３ 結果出力装置
１０ N分木初期化部
２０ 探索キー処理部
３０ N分木記憶部
【技術分野】
【０００１】
本発明は、N分木内部ノードの圧縮方法及び装置及びプログラムに係り、特に、M個の整数列から任意の整数（探索キー）を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
探索対象となるM個の整数列は昇順に並んでおり、その整数列から探索キーと同じキー値を持つ整数が存在するかの判定を行う。探索処理は、最上位ノードに位置するROOTノードから順にノード内の比較キーと探索キーの比較処理を繰り返し、中間位置に存在するBRANCHノードを通過し、探索キーに対応する（整数列への位置情報を保持する）LEAFノードを計算し、最終的に探索キーの整数列内の有無を判定する。図９の例では、探索キーは"３２３"であるため、まず、ROOTノードの最左端の矢印を指すBRANCHノード（"２０１"、"３９３"）へ移動する。『"２０１"＜探索キー（"３２３"）＜"３９３"』であるため、BRANCHノード中間矢印の先にあるLEAFノードに移動する。最終的にLEAFノード内の探索キーと同じ比較キーが存在するため、この探索処理は成功と判定され、整数列内における"３２３"の位置情報が返却される。
【０００３】
M個の整数列の探索処理を高速化するためのN分木データ構造は『ポインタを利用するもの』（図１０）と『配列を利用するもの』（図１１）の２つある。前者の『ポインタを利用するもの』は図１０に示すように、BRANCHノードが探索キーの目的位置を特定するための（N-1）個の比較キーと、次のBRANCHノードを表すN個のポインタから構成される（例えば、特許文献１参照）。一方、後者の『配列を使用するもの』は、図１１に示すように、BRANCHノードが（N-1）個の比較キーのみで構成され（例えば、非特許文献１、２参照）、各BRANCHノードにおける比較結果から、次BRANCHノードへのオフセット数を算出し、移動する（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許０４３５１５３０号公報
【特許文献２】特開２００５−２３５２０９号公報
【非特許文献】
【０００５】
【非特許文献１】Changkyu K. et al.: FAST: fast architecture sensitive tree search on modern CPUs and GPUs, Proceedings of the 2010 international conference on Management of data (SIGMOD'10),2010.
【非特許文献２】Benjamin S. et al.: k-ary search on modern processors, Proceedings of the 19th International Workshop on Data Management on New Hardware, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
M個の整数列に対してN分木を構成した場合、N分木の高さは
【０００７】
【数１】
で表され、N分木内部ノード内の総比較キー数（Nkey）は初項（N-1）で、公比Nの等比級数となり、
【０００８】
【数２】
になる。N分木内部ノードの比較キーのデータサイズは、前述の従来技術の非特許文献１，２、特許文献２においては、N分木を構成する整数列と同じデータサイズ（このデータサイズをSバイトとする）になるため、整数列のデータサイズが４バイト（S=4）の場合は、内部ノードの総サイズはNkey×４バイトになり、８バイト（S=8）の場合は、Nkey×８バイトになる。このN分木の総ノードサイズは、整数列が少ない（Mが小）場合には問題にならないが、センサ情報や、アクセスログデータなど大規模データ内の整数列に対するN分木を構成する際、N分木の内部ノードサイズが非常に大きくなる問題がある。
【０００９】
本発明は、上記の点に鑑みなされたもので、１つの比較キー（N分木のノードに設定される分岐判断の数値）のサイズを小さくすることが可能なN分木内部ノードの圧縮方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明は、M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、
入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、
前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、を有する。
【００１１】
また、上記の初期化手段は、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する手段を含む。
【００１２】
また、上記の探索キー処理手段は、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、を含む。
【００１３】
また、上記の探索キー処理手段は、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む。
【発明の効果】
【００１４】
上記にように、N分木内部ノード内の単体比較キーが８×Sビットから、８×Tビットで表現可能となるため、N分木の全内部ノードサイズはNkey×SバイトからNkey×Tバイトとなり、総サイズが約T/S（メタデータ要の領域は相対的に小さいため無視した場合）になる。より具体的には、M個の整数列を４バイト（S＝4）として、Tを１とした場合、N分木の全内部ノードサイズが変換前の約２５％になる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態における装置構成図である。
【図２】本発明の一実施の形態におけるN分木初期化部における部分木への分解と幅優先並び替えを示す図である。
【図３】本発明の一実施の形態における四則演算を利用した比較キー縮退変換処理の具体例である。
【図４】本発明の一実施の形態における部分木内の比較キー変換処理モジュールの具合例の１つとしてのフローチャートである。
【図５】本発明の一実施の形態における探索処理のズレの問題(T=1)を示す図である。
【図６】本発明の一実施の形態における正しい位置への補正処理を示す図である。
【図７】本発明の一実施の形態におけるN分木初期株の処理のフローチャートである。
【図８】本発明の一実施の形態における探索キー処理部の処理のフローチャートである。
【図９】N分木の構成図である。
【図１０】ポインタを利用したN分木のデータ構造である。
【図１１】配列を利用したN分木のデータ構造である。
【発明を実施するための形態】
【００１６】
以下図面と共に、本発明の実施の形態を説明する。
【００１７】
図１は、本発明の一実施の形態における装置構成を示す。
【００１８】
同図に示す装置は、N分木初期化部１０、探索キー処理部２０、N分木記憶部３０から構成され、N分木初期化部１０にはM個の整数列を入力する整数列入力装置１が、探索キー処理部２０には探索キーを入力する探索キー入力装置２及び結果出力装置３が接続されている。
【００１９】
以下に上記の構成における処理を説明する。
【００２０】
N分木初期化部１０は、探索キーの高速な処理を行うために、整数列入力装置１から入力されたM個の整数列に対してN分木（Nはシステムパラメータ）作成を行う。N分木初期化部１０では、整数列入力装置１から入力された昇順並び替え済みのN分木対象整数列から従来通りのN分木を作成する。その後、図２に示すように、N分木を高さH毎の部分木に分解し、幅優先で部分木を並び替え、内部の比較キーを昇順に配列配置することでN分木のデータ構造（ブロック）とする。ブロックに変換する際に、ブロック毎の比較キーの表現空間を８×Sビットから８×Tビット（Tは本発明における任意のパラメータで、S＞Tとする）に縮退する点が本発明の特徴である。詳細については図７、図８で詳述する。部分木内の比較キー変換処理の具体例として、四則演算を利用して比較キー縮退変換処理の例を図３に示す。
【００２１】
探索キー処理部２０は、探索キー入力装置２から入力された探索キーが、整数列入力装置１から入力された整数列内に含まれているかどうかを判定し、その位置情報を返す。探索の際に、比較を行う各ブロック内に含まれているメタデータ（ブロック内の比較キーを変換するために利用した情報）を利用して、探索キーをそのブロック毎で比較可能な値に変換した後に、ブロック内の比較キーとの比較を行う。探索を行うべき次ブロックの決定を行い、次の部分木に移動しながら、目的位置までの探索処理を行う。探索処理においては、部分木内の比較キーを圧縮する際に発生する異なる比較キーが同一の値に変換されてしまう問題（具体例として図４のフローチャートを利用した、この問題の説明を図５に示す）に対処する必要（表現空間を縮退したことによるペナルティ）がある。より具体的には、異なる比較キーが同一の値に変換されてしまうことにより、本来探索すべき部分木からの"ズレ"が発生する点である。このズレに関しては、図６に示すように、LEAFノードに到着した際に、探索キーと内部の比較キーを比較することで、ズレを修正する処理に加える。
【００２２】
次に、N分木初期化部１０の詳細な処理を説明する。
【００２３】
図７は、本発明の一実施の形態におけるN分木初期化部の処理のフローチャートである。
【００２４】
ステップ５００） 整数列入力装置１から昇順のM個の整数列が入力される。
【００２５】
ステップ５０５） 入力されたM個の整数値に対して、従来技術の方法によりN分木を作成し、通常のN分木のデータ構造を得る。
【００２６】
ステップ５１０） ステップ５０５で得られたN分木を、図２に示すようにROOTノードから順に高さH毎の部分木に分解して、幅優先に並び替える。
【００２７】
ステップ５１５） ｉを値１で初期化する。
【００２８】
ステップ５２０） N分木を高さHごとに分解したS個の部分木からｉ番目の部分木を取り出す。
【００２９】
ステップ５２５） 『部分木内の比較キー変換処理』（例えば、図４のフローチャート）モジュールを利用し、ｉ番目の部分木内に含まれる比較キーを変換してブロック化する。この変換処理において、各部分木内比較キーの表現空間を８×Sビットから８×Tビットに縮退する任意の変換処理を行う。この縮退変換処理の１つの具体例として四則演算を利用した変換手法がある。この手法については後述する。
【００３０】
ステップ５３０） ステップ５２５で変換処理され圧縮されたブロックが入力されると、当該入力されたブロックをFIFOバッファ（図示せず）に格納する。
【００３１】
ステップ５３５） ｉに１を加算する。
【００３２】
ステップ５４０） FIFOバッファ（図示せず）内の全てのブロックを順に読み出し、N分木記憶部３０に格納する。
【００３３】
以下に、上記のステップ５２５の縮退変換処理について図４を用いて説明する。
【００３４】
ステップ６００） N分木初期化部１０において、部分木の比較キー集合が入力されると、部分木の比較キーを昇順に以下のように並び替える。
【００３５】
V1(Vmin)，V2,…，ＶN-1(Vmax)
ステップ６０５） 比較キー集合内の全ての比較キーを、比較キー内最小値Vminで減算し、ｘ（補正項）を加算する。補正項ｘは部分木内の最小値を"１"に対応付けるために存在し、図３に示すように、比較キーを変換後に（"greater than"比較処理を想定）左端の部分木への探索を可能にする。
【００３６】
ステップ６１０） 比較キー集合内の全ての比較キー（Vn−Vmin+ｘ）を、（Vmax−Vmin+ｘ）で割る。
【００３７】
ステップ６１５） 比較キー集合内の全ての比較キーに2８T(Tはシステムパラメータ)を掛け、小数点以下を切り捨てる。
【００３８】
上記のステップ６０５，６１０，６１５までの部分木内の比較キーは、
【００３９】
【数３】
で変換（T<Ｓ， Ｖ*nは右辺を四捨五入した値
【００４０】
【数４】
する。
【００４１】
ステップ６２０） 先頭にメタデータVmin、Vmaxを付与した変換処理後の昇順比較キーをブロックとして出力する。
【００４２】
次に、探索キー処理部２０の処理を図８のフローチャートに沿って説明する。
【００４３】
ステップ７００） 探索キー処理部２０は、探索キー入力装置２から探索キーが入力される。
【００４４】
ステップ７０５） Ｎ分木記憶部３０からROOTノードのブロックを読み出す。
【００４５】
ステップ７１０） 読み出したブロック内に含まれるメタデータ（ブロック内の比較キーを変換するために利用した情報）を読み出して、ブロック内の比較キーが変換処理された内容と同じ処理を探索キーに行い、変換処理された探索キーを出力する。
【００４６】
ステップ７１５） 変換処理された探索キーを利用して、例えば、「URL: http://www.geocities.jp/m_hiroi/light/abcruby13.html」に示される手法を用いて、ブロック内の比較キーと比較処理を行う。その後、次に読み出すブロックを決定し、Ｎ分木記憶部３０から次に探索を行うべきブロックを読み出す。次に読み出すブロックがLEAFノードである場合はステップ７２０に移行する。LEAFブロックで無い場合はステップ７１０に移行する。
【００４７】
ステップ７２０） LEAFノードを含むブロック情報を取得し、Ｎ分木内部ノードの比較キーの変換処理（図５）により発生する探索位置の"ズレ"の問題に対処するために、最初に探索されたLEAFノードが探索キーに対応する正しいLEAFノードかどうかをLEAFノード内の比較キーを利用することで判定する。正しくない場合には、本来探索されるべきLEAFノード位置を、LEAFノードを順に読み込むことで図６に示すように補正する。
【００４８】
ステップ７２５） LEAFノード内に、探索キーと同じ比較キーを持つものがあるかを調べ、もしある場合は、その比較キーに対応する整数列内のポインタを結果出力装置３に出力する。無い場合には、整数列には探索キーと同じ値を持つもの無しとして出力する。
【００４９】
上記のように、本発明では、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えた列からN分木の内部データ構造であるブロックに変換する際（ステップ５２０〜ステップ５３５）、ブロックごとの比較キーの表現空間を縮退する処理（ステップ５２５）を行うことが特徴である。なお、H(高さ)=1としてステップ５２５の部分木内の比較キー変換処理を行わない場合が従来技術に対応する。本発明のような比較キーの変換を行うことで、探索キーと比較可能な状態で表現空間（０〜２S−１から０〜２T-1-１)を縮退させ、比較キーを構成するN分木のノード圧縮を可能とする。
【００５０】
なお、上記の図１に示すN分木内部ノード圧縮装置の構成要素の動作をプログラムとして構築し、N分木内部ノード圧縮装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５２】
１ 整数列入力装置
２ 探索キー入力装置
３ 結果出力装置
１０ N分木初期化部
２０ 探索キー処理部
３０ N分木記憶部
【特許請求の範囲】
【請求項１】
M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、
入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、
前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、
を有することを特徴とするN分木内部ノードの圧縮装置。
【請求項２】
前記初期化手段は、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する手段を含む
請求項１記載のN分木内部ノードの圧縮装置。
【請求項３】
前記探索キー処理手段は、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、
を含む請求項１記載のN分木内部ノードの圧縮装置。
【請求項４】
前記探索キー処理手段は、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む
請求項１または３記載のN分木内部ノードの圧縮装置。
【請求項５】
M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮方法であって、
初期化手段が、入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化ステップと、
探索キー処理手段が、前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理ステップと、
を行うことを特徴とするN分木内部ノードの圧縮方法。
【請求項６】
前記初期化ステップにおいて、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する
請求項５記載のN分木内部ノードの圧縮方法。
【請求項７】
前記探索キー処理ステップにおいて、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換し、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する
請求項５記載のN分木内部ノードの圧縮方法。
【請求項８】
前記探索キー処理ステップにおいて、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する
請求項５または７記載のN分木内部ノードの圧縮方法。
【請求項９】
請求項１乃至４のいずれか1項に記載のN分木内部ノードの圧縮装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【請求項１】
M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、
入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、
前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、
を有することを特徴とするN分木内部ノードの圧縮装置。
【請求項２】
前記初期化手段は、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する手段を含む
請求項１記載のN分木内部ノードの圧縮装置。
【請求項３】
前記探索キー処理手段は、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、
を含む請求項１記載のN分木内部ノードの圧縮装置。
【請求項４】
前記探索キー処理手段は、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む
請求項１または３記載のN分木内部ノードの圧縮装置。
【請求項５】
M個の整数列から任意の整数(探索キー)を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮方法であって、
初期化手段が、入力された前記M個の整数列に対してN(Nはシステムパラメータ)分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化ステップと、
探索キー処理手段が、前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理ステップと、
を行うことを特徴とするN分木内部ノードの圧縮方法。
【請求項６】
前記初期化ステップにおいて、
前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を８×Sビットから８×Tビット(但し、Tは任意のパラメータ、S>T)に縮退する
請求項５記載のN分木内部ノードの圧縮方法。
【請求項７】
前記探索キー処理ステップにおいて、
前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換し、
前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する
請求項５記載のN分木内部ノードの圧縮方法。
【請求項８】
前記探索キー処理ステップにおいて、
前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する
請求項５または７記載のN分木内部ノードの圧縮方法。
【請求項９】
請求項１乃至４のいずれか1項に記載のN分木内部ノードの圧縮装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−１５０５６２（Ｐ２０１２−１５０５６２Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１１−７１９６（Ｐ２０１１−７１９６）
【出願日】平成２３年１月１７日（２０１１．１．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２３年１月１７日（２０１１．１．１７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]