(57)【特許請求の範囲】
【請求項１】
ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する木構造保持手段と、
前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶するデータ間の関係保持手段と、
階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶するリンク間の関係保持手段と、
前記変形木構造から、入力されたデータ集合を包含するデータ集合に関連付けられたノードである目的ノードを探索するノード探索手段と、
を備え、
当該ノード探索手段は、ａ）目的ノードに逆リンクが有れば、当該逆リンクに関連付けられている前記仮置きリンク先のノードを更に探索し、ｂ）目的ノードでないノードに逆リンクが有れば、当該逆リンク先のノードを更に探索する
データ管理システム。
【請求項２】
前記原木構造または変形木構造から前記回転操作の対象となるリンクを選択し、選択した当該リンクが、逆リンクでない正リンクであれば、選択した当該リンクで結ばれる２つのノードの階層を逆転し、元下位ノード直下のリンクである移動リンクを元上位ノード直下に移して木構造を変形し、選択した当該リンクを前記データ間の関係保持手段に前記逆リンクとして格納し、当該移動リンクを前記逆リンクに関連付けて前記リンク間の関係保持手段に前記仮置きリンクとして格納する、回転操作手段を、さらに備える、
請求項１に記載のデータ管理システム。
【請求項３】
前記変形木構造から、逆リンクと、逆リンクでない正リンクの両者を有するノードを検出すると、当該逆リンク配下のサブ木構造を前記木構造保持部から、他の記憶手段である分割木構造保持手段に移動させる、分割手段を、さらに備える、
請求項１または請求項２に記載のデータ管理システム。
【請求項４】
前記データ集合の包含関係は、データ要素の類似性に基づいて決定され、下位のノードに関連付けられたデータ集合は、上位のノードに関連付けられたデータ集合の部分集合であって、より強い類似性を持つデータ要素からなる集合である、
請求項１乃至３の何れか１項のデータ管理システム。
【請求項５】
ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する木構造保持手段と、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶するデータ間の関係保持手段と、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶するリンク間の関係保持手段と、に接続されて、
前記変形木構造から、入力されたデータ集合を包含するデータ集合に関連付けられたノードである目的ノードを探索する手段であって、ａ）目的ノードに逆リンクが有れば、当該逆リンクに関連付けられている前記仮置きリンク先のノードを更に探索し、ｂ）目的ノードでないノードに逆リンクが有れば、当該逆リンク先のノードを更に探索するノード探索手段を備える、データ管理装置。
【請求項６】
ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶し、
前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶し、
階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶し、
前記変形木構造から、入力されたデータ集合を包含するデータ集合に関連付けられたノードである目的ノードを探索する過程で、
ａ）目的ノードに逆リンクが有れば、当該逆リンクに関連付けられている前記仮置きリンク先のノードを更に探索し、ｂ）目的ノードでないノードに逆リンクが有れば、当該逆リンク先のノードを更に探索する、データ管理方法。
【請求項７】
前記原木構造または変形木構造から前記回転操作の対象となるリンクを選択し、選択した当該リンクが、逆リンクでない正リンクであれば、選択した当該リンクで結ばれる２つのノードの階層を逆転し、元下位ノード直下のリンクである移動リンクを元上位ノード直下に移して木構造を変形し、選択した当該リンクを前記逆リンクとして記憶し、当該移動リンクを前記逆リンクに関連付けて前記仮置きリンクとして記憶する、
請求項６に記載のデータ管理方法。
【請求項８】
ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶し、
前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶し、
階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶し、
前記変形木構造から、入力されたデータ集合を包含するデータ集合に関連付けられたノードである目的ノードを探索することにおいて、
ａ）目的ノードに逆リンクが有れば、当該逆リンクに関連付けられている前記仮置きリンク先のノードを更に探索し、ｂ）目的ノードでないノードに逆リンクが有れば、当該逆リンク先のノードを更に探索する、
ことをコンピュータに実行させるプログラム。
【請求項９】
前記原木構造または変形木構造から前記回転操作の対象となるリンクを選択し、選択した当該リンクが、逆リンクでない正リンクであれば、選択した当該リンクで結ばれる２つのノードの階層を逆転し、元下位ノード直下のリンクである移動リンクを元上位ノード直下に移して木構造を変形し、選択した当該リンクを前記逆リンクとして記憶し、当該移動リンクを前記逆リンクに関連付けて前記仮置きリンクとして記憶する、
請求項８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ管理システム、データ管理装置、データ管理方法、および、プログラムに関し、特に、階層的な包含関係を持つデータ集合の探索に用いられる木構造のデータを管理するデータ管理システム、データ管理装置、データ管理方法、および、プログラムに関する。
【背景技術】
【０００２】
画像や映像の探索システムは、木構造の探索インデックスを用いることがある。探索システムは、この木構造を効率的にアクセスする必要がある。この為の様々な技術が開示されている。【０００３】
特許文献１に開示されている装置は、木の高さが高いノードに対して、早見表を用意して、アクセスの効率化を図る。【０００４】
非特許文献１は、画像や映像など（以下、データ要素）の類似探索を高速化する為のインデックスデータの構造を開示する。データ要素の類似探索においては、例えば、当該データ要素の特徴を表す特徴量とよばれるデータが用いられる。2つのデータ要素の特徴量間の距離が当該2つのデータ要素の類似性の尺度となるのである。すなわち、探索において、特徴量間の距離が近いデータ要素が類似すると判断される。【０００５】
非特許文献１が開示する木構造は、類似性が高いデータ要素の集合Ａが、同一ノード配下の部分木に対応するように構成されている。この時、この部分木の中間ノードは、或る狭い類似の範囲内にあるデータ要素の集合Ｂ、すなわち部分木全体に対応する集合Ａのサブセット集合Ｂを表現している。この木構造で直接リンクが張られている２つのノードにおいて、根に近いノードが表現するデータ集合は、根から遠いノードが表現するデータ集合を包含する。つまり、この木構造は、類似関係の階層的構造を表現する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開昭５８−３０３２号公報
【非特許文献】
【０００７】
【非特許文献１】劉 健全, 西村 祥治, 荒木 拓也. 類似度の階層関係に基づく木構造索引を用いた効率的な類似探索. 第5回データ工学と情報マネジメントに関するフォーラム (DEIM2013)，2013年3月3日−3月5日，A9-1
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１が開示するような包含関係を表現する木構造は、データ要素の特徴量の分布によっては、根から各葉までのリンクの数にばらつきが出る。つまり、非特許文献１が開示する木構造は、非平衡木になる。【０００９】
一般的に、木構造に対するデータの探索などの操作の計算コストは、根から葉までのリンク数に比例する。木構造が平衡であれば、データ数をN（Ｎは整数）としたとき、そのリンク数はO(log N)となり、効率的なデータ操作が可能である。しかしながら、非平衡木であれば、最悪、根から葉までのリンク数はO(N)となり、効率的なデータ操作ができない。【００１０】
このような状況を避けるため、木の回転が用いられる。木の回転により、木構造を平衡に保つことが可能である。【００１１】
図７は、木の回転の具体例を示す。木の回転には３つのノード（例ではノードA,B,D）と３つのリンクが関わる。この例において、木の回転は、ノードBをノードAの位置にもっていく操作である。すなわち、木の回転により、ノードＡへのリンクαはノードBを参照するリンクα’に変更され、ノードAからノードBへのリンクβはノードAからノードDへのリンクγ’に変更される。さらに、ノードBからノードDへのリンクγは、ノードBからノードAへのリンクβ’に変更される。【００１２】
この例は、時計回りの木の回転操作の例である。反時計回りの木の回転操作は、この逆手順である。木の回転は、片方の部分木の高さを一つ減らし、もう一方の部分木の高さを一つ増やす。適切な中間ノードが選択されて、木の回転操作が実施されると、すべての葉ノードに至るまでのリンク数は同程度にそろう。木の回転により木の高さを平衡させる具体例として、赤黒木やAVL木（Adelson-Velskii and Land’s tree）などの平衡木がよく知られている。【００１３】
しかしながら、非特許文献１の木構造に対して、木の回転を適用することはできない。なぜなら、非特許文献１の木構造は木構造上の上下関係で類似関係の階層的構造を表現しているからである。木の回転により変形された木構造は、データ要素の集合の正しい階層的構造を表現できなくなる。図７で示している通り、木の回転によりノードAとBの上下関係が反転する。また、ノードBとノードDの関係が、ノードAとノードDへの関係に変更される。【００１４】
木の回転が実行できない結果、非特許文献１の木構造は平衡を保つことができず、この木構造を対象とした効率的なデータ操作の実現は困難だった。【００１５】
なお、特許文献１の装置は、木の高いところで多く枝分かれするなど木の高さの高いノードが多くなる場合、早見表をチェックするコストがかかるため、アクセスの効率が悪化する。【００１６】
本願発明は、上述の課題を解決するためのデータ管理システム、データ管理装置、データ管理方法、および、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明にかかる一実施形態のデータ管理システムは、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する木構造保持手段と、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶するデータ間の関係保持手段と、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶するリンク間の関係保持手段と、を有する。【００１８】
本発明にかかる一実施形態のデータ管理装置は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する木構造保持手段と、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶するデータ間の関係保持手段と、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶するリンク間の関係保持手段と、に接続されて、前記変形木構造から、入力されたデータ集合を包含するデータ集合に関連付けられたノードである目的ノードを探索する手段であって、ａ）目的ノードに逆リンクが有れば、当該逆リンクに関連付けられている前記仮置きリンク先のノードを更に探索し、ｂ）目的ノードでないノードに逆リンクが有れば、当該逆リンク先のノードを更に探索するノード探索手段を備える。【００１９】
本発明にかかる一実施形態のデータ管理方法は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶し、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶し、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶する。【００２０】
本発明にかかる一実施形態の記憶媒体は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する処理と、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶する処理と、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶する処理と、をコンピュータに実行させるプログラムを記録する。
【発明の効果】
【００２１】
本発明にかかるデータ管理装置は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造の回転操作を実行できる。その結果、当該装置は、当該木構造の平衡化が可能であり、データ要素の検索、挿入操作を効率よく実行できる。
【図面の簡単な説明】
【００２２】
【図１】図１は、第１の実施の形態のデータ管理システム30の構成図である。
【図２Ａ】図２Ａは、ノード選択部13の動作フローチャートである（１／２）。
【図２Ｂ】図２Ｂは、ノード選択部13の動作フローチャートである（２／２）。
【図３】図３は、回転操作部14の動作フローチャートである。
【図４】図４は、第２の実施の形態にかかるデータ管理システム40の構成図である。
【図５】図５は、データ分割部29の動作フローチャートである。
【図６】図６は、第３の実施の形態にかかるデータ管理システム30の構成図である。
【図７】図７は、木の回転の具体例を示す。
【図８】図８は、データ管理システム30が木構造に対して行う変換の概略を示す。
【図９】図９は、木の回転操作の２つのケースを示す。
【図１０】図１０は、仮置きリンクに対する回転操作を示す。
【図１１】図１１は、コンピュータ装置50の構成図である。
【発明を実施するための形態】
【００２３】
＜第１の実施の形態＞
＜概要＞
本実施の形態のデータ管理システム30は、データ要素の探索を行う為、非特許文献１に記載された木構造を用いる。ここで、データ要素は、画像や映像等であり、探索目的となるデータである。データ管理システム30は、データ要素を探索するためのインデックスとして非特許文献１に記載された木構造を用いる。
【００２４】
この木構造は、ノードに関連付けられたデータ要素の集合の階層的な包含関係を示す。この木構造で直接リンクが張られている２つのノードにおいて、根に近いノードに関連付けられているデータ要素の集合Ａは、根から遠いノードに関連付けられているデータ要素の集合Ｂを包含する。集合の階層的な包含関係が、類似性に基づく場合、集合Ｂは集合Ａの部分集合であって、より強い類似性を持つデータ要素の集合である。例えば、集合Ａが自動車の画像の集合である場合、集合Ｂは乗用車の画像の集合、あるいは、乗用車以外の自動車の画像の集合である。
【００２５】
非特許文献１に記載された木の高さが平衡にならないのは、その木が、データ要素の階層関係という論理的な関係と、木構造という物理的な関係を一対一に対応させて表現していたからである。そこで、本実施形態のデータ管理システム30は、平衡木という物理的な構造に付加的な情報を追加し、木構造に対する操作過程でその情報を利用することで、平衡木によって、データ要素の階層関係を表現する。
【００２６】
すなわち、データ管理システム30が用いる木構造は、ノード間の関係を、木構造上の上下関係として表現するのではなく、ノード間のリンクに付与された関係の向きによって表現する。また、データ管理システム30は、平衡木と表現したい構造とのギャップを表現する情報を保持する。そして、データ管理システム30は、これらの情報を用いたノードの探索手段および木の回転操作手段を備えることで探索システムを実現する。
【００２７】
図８は、データ管理システム30が木構造に対して行う変換の概略を示す。データ管理システム30がもともと備えている木構造（以下、原木構造）は、図８の(a)が示すように、木構造の上下関係でデータ間の階層関係を示す。
【００２８】
データ管理システム30は、まず、木構造上の上下関係とデータ間の階層関係を分離するため、リンクに階層関係を表す情報を付与する。図８の(b)は、付与された情報を矢印として示す。データ管理システム30は、次にこれを平衡木に変換する。言い換えれば、データ管理システム30は、階層関係を表す矢印の向きを維持したまま、平衡木になるように木の回転操作をする。図８の(c)は回転操作の結果を示す。
【００２９】
この時、平衡木ではないものが平衡木として表現されるため、ギャップが発生する。例えば、ノードDは本来ノードBの下に直接つながるべきものがノードAの下につながっている。ノードAからノードDへのリンクは本来の直接的な階層関係を表すものではない。図８の(c)は、当該リンクを点線の矢印として示している。
【００３０】
そのリンクが本来あるべき場所は、ノードBとノードAのリンクのある場所である。図８の(c)の両矢印は、点線の矢印で示したリンクが本来あるべき場所にある別のリンクに付与された、点線の矢印で示したリンクへの関連付けを示す。
【００３１】
図８の(c)は、適切な情報が付加されれば、回転操作後の木構造（以下、変換木構造）である平衡木は、元の階層関係と等価な木構造を表現することができることを示す。ここで、適切な情報とは、例えば、階層関係を表すノード間の関係の向きの情報（リンクの矢印の向き）と、元の木構造とのギャップの情報（点線矢印と関連付けの両矢印）である。つまり、木の回転操作時にこの付加情報を正しくメンテナンスし、探索時にこの付加情報を利用して平衡木をたどることで、データ管理システム30は、元の階層関係に対する操作を平衡木上の操作として実現する。
【００３２】
以下の説明において、正リンクは、木構造上の上下関係と階層関係が一致しているリンク（図８において、下向きの矢印で表現されるリンク）を意味する。逆リンクは、木構造上の上下関係と階層関係が逆方向になっているリンク（図８において、上向きの矢印で表現されるリンク）を意味する。また、仮置きリンクは、図８の(c)のノードAからノードDへのリンクのように、本来の階層関係を示す場所にないリンク（図８で点線で示されるリンク）を意味する。
【００３３】
この時、仮置きリンクと関連付けられるリンクは必ず逆リンクになる。なぜなら、仮置きリンクは、木の回転により逆リンクが発生するときだけ発生するからである。
【００３４】
木の回転操作には、２つのケースが存在する。回転に関わる３つのリンクがα、β、γである場合、第１のケースは、図９の（左側）が示すようなリンクβが正リンクのケース、第２のケースは、逆リンクのケース（図９の右側）である。
【００３５】
まず、リンクβが正リンクの場合、データ管理システム30は、そのリンクを逆リンクとし、そのリンクの両端ノードの位置関係を入れ替える。そして、データ管理システム30は、γを仮置きリンクに変え、仮置きリンクを逆リンクに関連付ける。次にリンクβが逆リンクの場合、データ管理システム30は、その逆リンクに関連付けられたリンクをリンクγとして選び、前述と逆の手順を実行する。
【００３６】
前述の手順で木の回転操作をする時、データ管理システム30は、リンクβが仮置きリンクであるかどうかは考慮しなくても良い。その理由は、正リンク、逆リンクの何れであるかと、仮置きリンクであるかどうかは、リンクに独立に与えられる属性だからである。例えば図１０で示す通り、リンクβが仮置きリンクであってもなくても、データ管理システム30は、上述した通り、同様の手順で木の回転操作を実行できる。
【００３７】
以上が、データ管理システム30が行う、木の回転操作である。一方、データ管理システム30は、木の探索操作を次のように実行する。
【００３８】
あるノードの下位側のリンクが正リンクの場合、データ管理システム30は、元の階層構造に対する操作と同じく、正リンクをたどる条件を満たすリンクをたどる。逆リンクがある場合、データ管理システム30は、その逆リンクと関連付けられた仮置きリンクをたどる条件を満たすかどうかを判定し、満たすなら仮置きリンク先をたどる。正リンク、仮置きリンクをたどる条件を満たさなかった場合、データ管理システム30は、逆リンク先のノードに移動し、その逆リンクに関連付けられた仮置きリンク以外のリンクをたどる条件を判定する。
【００３９】
この木の探索操作は、平衡木の根ノードから葉ノードの方へ後戻りすることなく実行される。したがって、この木の探索操作は、木のノード数Nに対してO(log N)で実行可能である。
【００４０】
木の探索操作は、木へのデータ挿入、及び、木からのデータ探索などのデータ操作の基本操作である。上述したように、本実施形態のデータ管理システム30は、木の回転により木を平衡に保ち、かつ、その平衡木に対して効率的な木の探索操作を行う。したがって、本実施形態のデータ管理システム30は、データの操作を高速化できる。
【００４１】
なお、上述した木の回転操作は、データ管理システム30の回転操作部14によって実行される。木の探索操作は、ノード選択部13によって実行される。回転操作部14、及び、ノード選択部13については、後述する。
【００４２】
木が平衡に保たれていることから、データ管理システム30は、根ノードに近いリンクを選択して、木のデータを概ね等分することができる。これについては、第２の実施形態で説明する。
【００４３】
＜構成＞
図１は、本実施の形態のデータ管理システム30の構成を示す図である。データ管理システム30は、データ管理装置10と、データ管理装置10に接続されたデータ保持部15、木構造保持部16、データ間の関係保持部17、及び、リンク間の関連保持部18と、を包含する。データ管理装置10は、データ挿入部11と、データ探索部12と、ノード選択部13と、回転操作部14とを含む。
【００４４】
データ挿入部11は、データ要素をデータ保持部15に追加して、木にノードを追加する場所を決定する。データ探索部12は、目的のデータ要素がある場所を木から探索する。
【００４５】
ノード選択部13は、木構造保持部16とデータ間の関係保持部17とリンク間の関連保持部18を参照し、次にたどるべきノードを選択する。回転操作部14は、木構造保持部16とデータ間の関係保持部17とリンク間の関連保持部18を操作し、木の高さが平衡するように、木に対して木の回転操作を実行する。
【００４６】
データ保持部15は、データ要素を記憶する。木構造保持部16は、ノードとリンクから構成される木を記憶する。両者は、統合されても良い。
【００４７】
データ間の関係保持部17は、木構造保持部16が記憶する木のリンクが正リンクであるか逆リンクであるかの区別情報を記憶する。データ間の関係保持部17は、逆リンクまたは正リンクの何れか一方を記憶しているだけでも良い。さらに、データ間の関係保持部17は、木のリンクが、仮置きリンクであるか否かの区別情報を記憶していても良い。
【００４８】
リンク間の関連保持部18は、逆リンクごとに、当該逆リンクに関連付けられた仮置きリンクを記憶している。
【００４９】
ここで、データ保持部15、木構造保持部16、データ間の関係保持部17、リンク間の関連保持部18は、ディスク装置、半導体メモリ装置等の、記憶装置である。
【００５０】
データ挿入部11、データ探索部12、ノード選択部13、及び、回転操作部14は、論理回路で構成される。
【００５１】
なお、データ管理装置10は、コンピュータ装置50により実装されても良い。図１１は、コンピュータ装置50の構成図である。コンピュータ装置50は、プロセッサ51、および、主記憶部52を備え、補助記憶装置54と接続されている。主記憶部52は、半導体メモリ装置等の記憶装置である。補助記憶装置54は、ディスク装置、半導体メモリ装置等の、記憶装置である。プロセッサ51は、主記憶部52、および、補助記憶装置54の読み書きが可能である。
【００５２】
データ挿入部11、データ探索部12、ノード選択部13、または、回転操作部14は、主記憶部52に格納され、プロセッサ51によって実行されるプログラム53によって実現されても良い。すなわち、プロセッサ51が、プログラム53を実行することで、データ探索部12、ノード選択部13、または、回転操作部14が行う処理を実行しても良い。
【００５３】
この場合、データ保持部15、木構造保持部16、データ間の関係保持部17、リンク間の関連保持部18は、補助記憶装置54により実現されても良い。なお、プログラム53は、当初、補助記憶装置54に格納されており、例えば、コンピュータ装置50の初期設定時に主記憶部52にロードされても良い。
【００５４】
本実施の形態のデータ管理システム30は、木構造の情報に加え、ノード間の関係や逆向きリンクの情報を保持、利用することでデータの類似性の階層関係を平衡木として表現できる。これにより、データ管理システム30は、アクセスの効率化を可能にする。
【００５５】
＜インプリメント上の補足＞
木構造保持部16は、木構造のノードをオブジェクト、リンクをノードへの参照として記憶しても良い。この場合、木の探索における、リンクをたどる処理は、あるノードが参照するノードにアクセスする処理として実現できる。また、回転操作は、参照の付け替えで実現できる。
【００５６】
データ間の関係保持部17は、リンクに正リンクか逆リンクかのフラグを備えることで実現されても良い。リンクがノードへの参照として実現された場合、リンク自体がそのフラグを備えることはできない。この場合、例えば、参照元のノードが、そのフラグを保持するフィールドを備えればよい。
【００５７】
リンク間の関連保持部18は、逆リンクを持つノードのオブジェクトに、仮置きリンクを保持するフィールドへの参照を保持するフィールドを備えることで実現されても良い。データ探索部12等は、このフィールドを通じて、仮置きリンク先の子ノードへアクセスしたり、たどるべきではない仮置きリンクを識別したりすれば良い。
【００５８】
オブジェクトがリンクを表現し、そのリンクが、データ間の関係を表すフラグや関連づけられたリンクへの参照を持つフィールドを備えても良い。
【００５９】
＜動作＞
データ挿入部11およびデータ探索部12は、ａ）追加されたデータ要素の情報等を挿入すべきノード、または、ｂ）探索対象のデータ要素の情報が記録されているノード、を判定する条件をノード選択部13に与える。それを受けて、ノード選択部13は目的のノードを木構造保持部16から探索する。ここで、ノードに登録されるデータ要素の情報とは、例えば、データ要素へのポインタ、データ要素の特徴量である。
【００６０】
データ挿入部11は、外部から入力されたデータ要素をデータ保持部に登録するとき、上記動作を行う。データ探索部12は、上記動作後、得られたノードに格納されているポインタから目的となるデータ要素を得る。
【００６１】
データ挿入部11およびデータ探索部12は、非特許文献１等に記載された手順で動作すればよい。ただし、データ挿入部11は、データ要素の追加により木構造が変化した場合は、回転操作部14を通じて木構造を平衡に保つ。
【００６２】
図２Ａおよび図２Ｂは、ノード選択部13の動作フローチャートである。
【００６３】
まず、ノード選択部13は木構造保持部16より根ノードを取り出し、それを探索ノードリストに追加する（ステップＡ１）。ノード選択部13は探索ノードリストが空になるまで以下の一連の操作を繰り返す（ステップＡ２）。
【００６４】
ノード選択部13は、探索ノードリストから探索ノードを１つ取り出し、当該ノードがデータ挿入部11もしくはデータ探索部12より渡された探索条件を満たしているかどうかを判定する（ステップＡ３）。
【００６５】
ノードは、当該ノードに関連付けられたデータ要素の集合が、探索の目的であるデータ要素またはその集合を含んでいる可能性がある場合、探索条件を満たす。例えば、探索条件が「タクシー」であり、ノードが「乗用車」のデータ要素集合に関連付けられている場合、当該ノードは探索条件を満たす。ノードには、関連付けられている集合を規定する条件、例えば、「乗用車」を表現するデータが含まれている。ノード選択部13は、両条件を比較して、ノードに含まれている条件を満たす集合が、探索条件を満たす集合を包含するとき、「当該ノードが探索条件を満たしている」と判断する。
【００６６】
ステップＡ３で探索ノードリストから取り出したノードが、探索条件を満たしていれば（ステップＡ３で「はい」）、ノード選択部13は、当該ノードを探索結果に追加する（ステップＡ４）。そして、ノード選択部13はデータ間の関係保持部17を参照し、当該ノードが逆リンクを持っているかを検査する（ステップＡ５）。持っていれば、ノード選択部13はリンク間の関連保持部18を参照し、その逆リンクに関連付けられた仮置きリンクを取得し、木構造保持部16を参照してその仮置きリンクの先にある子ノードを探索ノードリストに追加する（ステップＡ６）。
【００６７】
次に、ステップＡ３で探索ノードリストから取り出したノードに正リンクがあれば、ノード選択部13は、その正リンクの先にある子ノードを探索ノードリストに追加する（ステップＡ７）。その後、ノード選択部13は、ステップＡ２に戻る。
【００６８】
なお、ステップＡ３で探索ノードリストから取り出したノードに逆リンクが無い場合も（ステップＡ５で「いいえ」）、当該ノードに正リンクがあれば、ノード選択部13は、そのリンクの先にある子ノードを探索ノードリストに追加する（ステップＡ７）。当該ノードに、２本の正リンクが有る場合、ノード選択部13は、両者のリンク先子ノードを探索ノードリストに追加する。
【００６９】
ステップＡ３で探索ノードリストから取り出したノードが探索条件を満たさなければ（ステップＡ３で「いいえ」）、ノード選択部13はデータ間の関係保持部17を参照し、当該ノードが逆リンクを持っているかどうかを検査する（ステップＡ８）。持っていれば、ノード選択部13は、逆リンク先にあるノードを探索リストに追加するとともに、その関連する仮置きリンク先のノードを探索ノードリストから除外する（ステップＡ９）。その後、ノード選択部13は、ステップＡ２に戻る。
【００７０】
当該ノードが逆リンクを持っていない場合（ステップＡ８で「いいえ」）、ノード選択部13は、ステップＡ２に戻る。
【００７１】
図３は、回転操作部14の動作フローチャートである。
【００７２】
まず回転操作部14は、平衡にするためにどのリンクを回転するかを決める（ステップＢ１）。回転操作部14は、木の回転の際に用いられる公知の方法でこの決定をすればよい。
【００７３】
次に、回転操作部14はデータ間の関係保持部17を参照し、当該リンクが正リンクかどうかを判定する（ステップＢ２）。正リンクであれば、回転操作部14は木構造保持部16を操作し木の回転操作をする。さらに、回転操作部14はデータ間の関係保持部17にそのリンクが逆リンクになったことを記録し、その逆リンクと仮置きリンクになったリンクを関連付けて、リンク間の関連保持部18に記録する（ステップＢ３）。
【００７４】
回転するリンクが逆リンクであれば（ステップＢ２で「いいえ」）、回転操作部14は木構造保持部16を操作し、木の回転操作をする。さらに、回転操作部14は、データ間の関係保持部17にそのリンクが正リンクになったことを記録し、当該リンクと仮置きリンクであったリンクとの関連付けをリンク間の関連保持部18から削除する（ステップＢ４）。
【００７５】
＜効果＞
本実施形態のデータ管理システム30は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造の回転操作を実行できる。その結果、当該木構造の平衡化が可能であり、データ要素の検索、挿入操作が効率よく実行できる。
【００７６】
その理由は、平衡木にノード間の関係とリンク間の関連の情報を付加して保持し、それらを利用して木を探索するからである。
【００７７】
＜変形例＞
データ保持部15、木構造保持部16、データ間の関係保持部17、及び、リンク間の関連保持部18は、その一部または全部を統合して構成しても良い。
【００７８】
木構造保持部16に格納される回転操作前の木構造は、上述したように、ノードに関連付けられたデータ要素の集合の階層的な包含関係を示す。この包含関係は、必ずしも、類似性に基づいて決定されていなくても良い。包含関係は、例えば、映像データの撮影場所の近接関係に基づいて決定されるなど、他の基準に基づいて決定されていても良い。
【００７９】
＜第２の実施形態＞
＜構成＞
図４は、第２の実施の形態にかかるデータ管理システム40の構成図である。本実施の形態のデータ管理システム40のデータ管理装置20は、分散環境で動作する。このため、本実施の形態のデータ管理装置20は、第１の実施の形態の構成に加えて、データ分割部29を備える。データ分割部29は、各分散サーバ装置に配置するデータ要素および木構造の分割を決定する。データ分割部29は、データを概ね等分に分割出来る。
【００８０】
データ挿入部21、データ探索部22、ノード選択部23、及び、回転操作部24は、断りのない限り各々第１の実施形態におけるデータ挿入部11、データ探索部12、ノード選択部13、及び、回転操作部14と同様に機能する。
【００８１】
データ保持部25、木構造保持部26、データ間の関係保持部27、及び、リンク間の関連保持部28も、断りのない限り、各々第１の実施形態のデータ保持部15、木構造保持部16、データ間の関係保持部17、及び、リンク間の関連保持部18と同様に機能する。
【００８２】
ここで、データ保持部25、木構造保持部26、データ間の関係保持部27、及び、リンク間の関連保持部28は、ディスク装置、半導体メモリ装置等の、記憶装置である。
【００８３】
データ挿入部21、データ探索部22、ノード選択部23、回転操作部24、データ分割部29は、論理回路で構成される。データ挿入部21、データ探索部22、ノード選択部23、回転操作部24、または、データ分割部29は、図１１のコンピュータ装置50の主記憶部52に格納され、プロセッサ51によって実行されるプログラム53によって実現されても良い。
【００８４】
本実施の形態のデータ管理システム40は、第１の実施の形態と同様に、木構造の情報に加え、ノード間の関係や逆向きリンクの情報を保持、利用することでデータの類似性の階層関係を平衡木として表現できる。これにより、データ管理システム40は、アクセスの効率化に加え、データの等分割を可能にする。
【００８５】
＜動作＞
図５は、データ分割部29の動作フローチャートである。
【００８６】
まず、データを分割するデータ管理装置20のデータ分割部29は、木構造保持部26にアクセスし、根ノードを取り出す（図５のステップＣ１）。次に、今までにすでに行われた分割の結果、当該ノードにリンクが１つしか残っていないかどうかをチェックする（ステップＣ２）。もし１つしか残っていなければ（ステップＣ２で「はい」）、データ分割部29は、そのリンクをたどり下位のノードを取り出す（ステップＣ３）。
【００８７】
この一連のステップにより、データ分割部29は、複数のリンクが残っている根ノードに最も近いノードを見つける。
【００８８】
複数リンクが残っている木を見つけると（ステップＣ２で「いいえ」）、データ分割部29は、データ間の関係保持部27にアクセスし、逆リンクがあれば逆リンクを、無ければ、正リンクを、分割するリンクとして選択する（ステップＣ４）。
【００８９】
データ分割部29は、選択したリンク以下の部分木と当該部分木のノードに関連付けられたデータ要素を、他の装置、例えば、分散配置されている別のデータ管理装置20に送信する。
【００９０】
＜効果＞
データ分割部29は、データを概ね等分に分割できる。その理由は、データ分割部29は、木構造の上位で分割するからである。末端ノード対応のデータ数が概ね同じであれば、分割された部分木のデータ要素数は概ね等しくなる。さらに、データ分割部29は、階層関係が近いノードをまとめて分割することができる。その理由は、データ分割部29は、分割するリンクとして逆リンクを優先して選ぶためである。
【００９１】
＜第３の実施の形態＞
図６は、第３の実施の形態にかかるデータ管理システム30の構成図である。このデータ管理システム30は、木構造保持部16と、データ間の関係保持部17と、リンク間の関連保持部18と、を備える。
【００９２】
木構造保持部16は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造である原木構造が、回転操作により変形された変形木構造を記憶する。データ間の関係保持部17は、前記回転操作により階層が逆転されたノード間のリンクである逆リンクを記憶する。リンク間の関連保持部18は、階層が逆転された元下位ノード直下から元上位ノード直下に移されたノードへのリンクである仮置きリンクを、前記逆リンクに関連付けて記憶する。
【００９３】
木構造保持部16、データ間の関係保持部17、および、リンク間の関連保持部18は、ディスク装置、半導体メモリ装置等の、記憶装置である。したがって、本実施の形態にかかるデータ管理システム30は、いわゆるデータベースと呼ばれる構造化データを記憶媒体に格納したものである。
【００９４】
本実施形態のデータ管理システム30が格納する木構造は、ノードに関連付けられたデータ集合の階層的な包含関係を示す木構造でありながら、回転操作により平衡化されていても良い。その結果、この木構造にアクセスする装置は、データ要素の検索、挿入操作が効率よく実行できる。
【００９５】
その理由は、本実施形態のデータ管理システム30が格納する木構造は、平衡木にノード間の関係とリンク間の関連の情報を付加して保持しており、この木構造にアクセスする装置は、それらを利用して木を探索できるからである。
【００９６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００９７】
この出願は、2014年09月09日に出願された日本出願特願2014-182816を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００９８】
10    データ管理装置
11    データ挿入部
12    データ探索部
13    ノード選択部
14    回転操作部
15    データ保持部
16    木構造保持部
17    データ間の関係保持部
18    リンク間の関連保持部
30    データ管理システム
20    データ管理装置
21    データ挿入部
22    データ探索部
23    ノード選択部
24    回転操作部
25    データ保持部
26    木構造保持部
27    データ間の関係保持部
28    リンク間の関連保持部
29    データ分割部
40    データ管理システム
50    コンピュータ装置
51    プロセッサ
52    主記憶部
53    プログラム
54    補助記憶装置
【図１】
0006561993.tif 000002
【図２Ａ】
0006561993.tif 000003
【図２Ｂ】
0006561993.tif 000004
【図３】
0006561993.tif 000005
【図４】
0006561993.tif 000006
【図５】
0006561993.tif 000007
【図６】
0006561993.tif 000008
【図７】
0006561993.tif 000009
【図８】
0006561993.tif 000010
【図９】
0006561993.tif 000011
【図１０】
0006561993.tif 000012
【図１１】
0006561993.tif 000013