分割による高次元類似ジョイン方法
【課題】相対的に短い実行時間で大量のストレージ空間を要せず、高次元データに対する類似ジョインを効率よく行うことができる分割による高次元類似ジョイン方法を提供すること。
【解決手段】高次元データ空間を分割するステップと、所定のデータセット間のジョインを行うステップを含み、前記高次元データ空間の分割を行う前に、高次元データ空間を分割するための次元、及び次元の個数を予め決定し、前記データセットの各セルは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合のみにジョインを行う。
【解決手段】高次元データ空間を分割するステップと、所定のデータセット間のジョインを行うステップを含み、前記高次元データ空間の分割を行う前に、高次元データ空間を分割するための次元、及び次元の個数を予め決定し、前記データセットの各セルは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合のみにジョインを行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高次元類似ジョイン（high-dimensional similarity join）方法に関し、より詳しくは、動的に空間分割次元及び分割次元の個数を予め指定することにより、効率的な類似性（similarity）測定を可能にする次元選択手法を利用した分割による高次元類似ジョイン方法に関する。
【背景技術】
【０００２】
一般に、オーディオ、ビデオ、イメージ、テキストなどのマルチメディアデータ、時間的な順序を表す時系列データ、及び種々のデータウェアハウスに使用される膨大な量のビジネス上のデータは、図６に示すように、前処理過程を経て、検索、管理などが遂行されるように、高次元上の一つのポイント（point）としてマッピングされ、マッピングされたデータ間の類似性は、高次元空間においてユークリッド距離（euclidean distance）により測定される。例えば、二つのイメージファイルの類似性は、高次元の空間上にマッピングされた二つのポイントの間の距離により測定される。
【０００３】
さらに、前記「類似ジョイン」とは、膨大な量のマルチメディアのデータベース、医学のデータベース、科学のデータベース、時系列のデータベースなどから高次元データが入力として提供されるとき、それらのデータセット間の相互類似なデータを効率的に検索することに定義され、特に、イメージ及びマルチメディアのデータシステムと、時系列のデータシステムなどのような高次元データシステムにおいて必須に求められる。
【０００４】
この類似ジョインは、次のようにモデリングすることができる。
【０００５】
まず、ｄ-次元空間上のデータセットＲ、及びＳが存在し、Ｒと、Ｓとに対する任意の元素ｒと、ｓとがそれぞれｒ=[r1,r2,...rd]とｓ=[s1,s2,...sd]とに表れると仮定すれば、類似ジョインは、下記の数１のように公式化される。
【０００６】
【数１】
【０００７】
ここで、pは、特定の距離マトリック（metric）を表し、εは、使用者により定義されたパラメータであって、限界類似度を表すが、RとSとからなるデータ対のうち、空間上の距離がε値よりも小さいデータ対のみを結果として返還する。
【０００８】
現在通用の類似ジョイン方法は、低次元データの場合に効率的であるが、10、100、更に10000に至る非常に大きい次数を求める高次元データに対しては、実行時間、及び所要のシステムストレージの面で極めて非効率的である。
【０００９】
従来の類似ジョイン方法は、代表的なものとして、ε-kdBツリーに基づいた類似ジョイン手法（K.Shim, R.Srikant, 及びR.Agrawalらによる“高次元類似ジョイン”、Proceedings of the 1997 IEEE International Conference on Data Engineering, 1997）と、イプシロン(ε)-グリッドオーダを利用した類似ジョイン手法（C.Bohm,B.Braunmuller,F.Krebs,及びH.-P.Kriegelによる“ε-グリッドオーダ”（epsilon grid order）、大量の高次元データに対する類似ジョインのためのアルゴリズム”、Proceedings of the 2001 ACM-SIGMOD Conference, 2001）などが挙げられる。
【００１０】
ε-kdBツリーに基づく類似ジョイン手法は、データ空間を一つの次元軸に対してイプシロン（ε）面積のセルにそれぞれ分割してデータを格納した後、それらセルに対して多次元インデックス構造のε-kdBツリーを構成する。
【００１１】
このような手法は、データ分割のためのパーティション領域をε単位に制限することにより、ジョイン回数を効率的に低減するが、それぞれのパーティションを表すε-kdBツリー構造をシステムストレージ内に保持すべきであって、データ空間の次元数が増加するほど、所要のシステムストレージも増大することになり、類似ジョインの実行時間も比例して増加することになる。
【００１２】
また、ε-グリッドオーダを利用する類似ジョイン手法においては、データ空間上にセルの長さがεのグリッドを配置し、それらグリッドセルを辞典編纂順に比較することで得られるデータの特別な整列順序に基づいて、高次元データに対する類似ジョインを行う。しかし、このような手法は、ε-ｋｄＢツリーを利用する方法とは異なって、制限されたストレージでも極めて大きいデータセットの効率的なスケーリングを提供するが、図７に示すように、ｐのジョイン対を探し出すするために、 p-[ε.ε. .ε] と p+ [ε.ε. .ε] 間の全てのポイントを考慮しなければならず、次元の増加に伴い、所定の区間内の検索すべきセルの個数が増大することとなり、実行時間も増加するという問題点がある。
【００１３】
一方、低次元空間データシステムにおいて利用される空間分割手法は、高次元データ空間での類似ジョインに適用可能ではあるが、全ての次元軸に対する空間分割が求められ、実用化の側面からみて好ましくない。すなわち、分割されるセルの数は、分割すべき次元軸の数の増加に従い急激に増加し（例えば、各次元軸が10等分される場合、8,16,32,64の各次元に対して生成されるセルの個数は、108,1016,1032,1064となる）、元のデータセットの個数よりも分割されたセルの個数が多くなる結果をもたらす。分割されたセルの個数が増大すると、データスキュー（data skew）現象が甚だしくなり、さらに、空間分割に基づく手法そのものが非効率的になってしまう。ここで、前記「データスキュー現象」とは、図８に示すように、高次元データ空間を各セルにそれぞれ分割する際、セル内のデータ分布が均一でないことを意味する。
【００１４】
従って、短い実行時間で効率的な高次元データの類似ジョインを行い、類似ジョインの実行の際に大量のストレージ空間を必要としない類似ジョイン方法が求められる。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明は、上記問題点に鑑みなされたものであって、相対的に短い実行時間で大量のストレージ空間を要せず、高次元データに対する類似ジョインを効率良く行うことができる分割による高次元類似ジョイン方法を提供することを目的とする。
【００１６】
また、本発明は、類似ジョインの性能を向上し得る分割次元の選択手法を提供することを他の目的とする。このとき、前記分割次元の選択手法は、与えられた複数のデータセットの各軸に対する分布値を用い、動的に最も効率良くデータ空間を分割する次元、及び次元の個数を指定することである。
【課題を解決するための手段】
【００１７】
上記の目的を達成するため、本発明に係る高次元類似ジョイン方法においては、高次元データ空間を分割するステップを含み、前記高次元データ空間を分割する前に、高次元データ空間を分割するための次元、及び次元の個数が予め決定され、所定のデータセット間のジョインを行うステップを含み、前記データセットの各セールは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合のみにジョインを行うことを特徴とする。
【００１８】
そして、前記データセットの各セル間のジョインの際に発生可能なジョイン演算回数を計算するステップを更に含むことを特徴とする。
【００１９】
さらに、前記高次元データ空間を分割するための次元は、前記ジョイン演算回数に基づいて決定されることを特徴とする。
【００２０】
また、前記高次元データ空間を分割するための次元の個数（dp）は、データセットの大きさと、データセットの格納されたディスクブロックの大きさとを比較して求め、下記の式より求められる。
【００２１】
【数２】
【００２２】
ここで、|R|blockと、|S|blockとは、ジョインを行うデータセットRとSとの総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさ、[1/ε]は、各セルの個数である。
【００２３】
さらに、前記ジョイン演算の回数は、各次元に対し、各セルに含まれたデータセットR及びSのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められる。
【００２４】
さらに、前記ジョイン演算の回数は、各次元に対し、サンプリングされた一部のセルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められる。
【００２５】
これらの目的、特徴および利点は、本発明の詳細な説明および添付図面に照らして明らかとなろう。
【発明の効果】
【００２６】
以上のとおり、本発明によると、低次元空間で通用されていた空間分割手法を高次元の空間でも適用可能にし、空間分割によるセルの個数が急激に増加しても、CPU及びIOコストを最適化しながら類似ジョインを行い得るという効果がある。
【００２７】
また、与えられたデータセットの各軸に対する分布値を利用して、動的に最も効率良く空間を分割する次元、及び次元の個数を予め指定することにより、類似ジョインの実行時間を短縮し得るという効果がある。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の好ましい実施の形態を、添付図面に基づいて詳しく説明する。
【００２９】
図１は、本発明を適用するハードウェアの一実施例を示す構成図である。
【００３０】
図1に示すように、システムバス１６を介して、単一、もしくは多重プロセッサ（P1,P2,P3…Pn；１１）、主記憶装置のメモリ領域１２及び入出力処理器１５がそれぞれ連結されており、前記主記憶装置のメモリ領域１２の内には、共有メモリ領域１３が設けられ、前記入出力処理器１５は、補助記憶装置のディスク１４と連結されている。このように、本発明は、単一プロセッサ、もしくは多重プロセッサと、共有メモリ領域とを含む一般のハードウェア環境で作動し得るものである。
【００３１】
以下、本発明に係る分割による高次元類似ジョイン方法について、図２に基づいて説明する。
【００３２】
本発明に係る分割による高次元類似ジョイン方法においては、高次元データ空間を分割するステップ（S100）と、該空間分割を行う前に、高次元データ空間を分割するための次元の個数を決定するステップ（S200〜S220）と、高次元データ空間を分割するための次元を決定するステップ（S300〜S320）と、所定のデータセット間のジョインを行うステップ（S400）とを含んでいる。
【００３３】
そして、前記各ステップについて、より詳しく説明すると、次の通りである。
【００３４】
前記分割ステップ(S100)においては、全データ空間が、限界類似度を表すε単位のセルにそれぞれ分割されており、データ空間上の全てのエントリが単位ハイパーキューブ（hypercube）の内に存在すると仮定するとき、すなわち、各次元軸の範囲が［0，1］の間の場合、各次元は、［1/ε］個のセルに分けられる。さらに、類似ジョインを行うデータセットR及びSの各エントリは、データの前処理過程を経て該当のセルに分散し、格納される。図３は、2次元に対する分割ステップを経た後のデータ空間を示し、図中の小さい正方形は、それぞれ分割されたセルを表す。
【００３５】
また、前記類似ジョインステップ（S400）においては、類似ジョインを行う二つのデータセットから特定の類似性の要求を満足するデータ対を検索するが、このとき、一つのデータセットの各セルを他の一つのデータセットの全てのセルと対を組み合う必要はなく、データ空間上で重なり合っているか、もしくは、隣り合っているセルのみに対を組み合う。一般に、d-次元上での単位ハイパーキューブの境界に存在しない任意のセルが、対を組み合う相手側のセットのセルの数は、3ｄ個となり、例えば、図3の2次元空間でのセルPは、相手側のセットのセルのうち、斜線部分の9個のセルと類似ジョインを行うための対を組み合う。
【００３６】
前述のとおり、高次元類似ジョインを行う場合に、全次元に対してデータ空間を分割すると、分割されたセルの数が急増し、これによりデータスキュー現象が甚だしくなり、ディスクのIO費用が増加することになる。さらに、分割次元の個数が増加すると、データを該当のセルにマッピングするためのハッシュ関数の計算コストも、さらに他の費用負担として作用する。従って、全次元に対して空間を分割せず、次元のうち、データの「均一な分布」を示す幾つかの次元のみを選択して、空間分割を行うことが好ましい。ここで、「均一な分布」は、相対的な概念であって、何れの次元が一つのデータセットに対して均一な分布を示すとしても、他のデータセットに対しては、均一でない分布を示すこともある。また、限界類似度が変わるに従い、次元の分布の均一度も変わる。すなわち、次元の分布の均一度は、与えられた二つのデータセット及び限界類似度に従い、動的に決定される。
【００３７】
従って、本発明においては、全次元に対して空間分割を行わず、次元のうち、データの「均一な分布」示す幾つかの次元のみを選択して空間の分割を行う。
【００３８】
以下、前記空間の分割を行う前に、高次元データ空間を分割するための次元の個数を決めるステップ（S200〜S220）と、高次元データ空間を分割するための次元を決めるステップ（S300〜S320）とについて説明する。
【００３９】
分割次元の個数
高次元空間での二つのデータセットＲ及びＳに対する類似ジョイン処理の際、データの分布が均一であると仮定し、分割次元の個数がdpのとき、R及びSのデータエントリ数をそれぞれ対組み合わせする回数として測定されるCPUコスト（Cost(CPU)）は、下記の数３のように計算される。
【００４０】
【数３】
【００４１】
さらに、R及びSの格納された総ディスクブロック数をそれぞれ、|R|block, |S|blockとすると、ディスクへの接近コストのディスクI/Oコスト（Cost(IO)）は、下記の数４のように計算される。
【００４２】
【数４】
【００４３】
前記数３と数４とによると、分割次元の個数（dp）が増加するほど、CPUコストは減少するが（
【００４４】
【数５】
【００４５】
を仮定するとき）、ディスクI/Oコストはむしろ増加することが分かる。つまり、CPUコストとディスクI/Oコストとは、類似ジョインの性能に関わってお互いに相反する。
【００４６】
このような点を考慮して、本発明においては、データセットの大きさとディスクブロックの大きさとを比較することにより、分割次元の個数を決定する。
【００４７】
例えば、各セルの平均の大きさを、ディスクの一つのブロックと仮定すると、総分割セルの個数（Np）は、下記の数６のように計算される（S200）。
【００４８】
【数６】
【００４９】
ここで、|R|block, |S|blockは、Ｒ及びＳのそれぞれ格納された総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさである。
【００５０】
さらに、空間を所定次元の個数（dp）に分割する際に得られるセルの個数（Np´）は、下記の数７のように計算される（S210）。
【００５１】
【数７】
【００５２】
従って、Np ＝ Np´が成立され、その結果、分割次元の個数（dp）は、下記の数８のように推論される（S220）。
【００５３】
【数８】
【００５４】
分割次元の選択
高次元データ空間でデータが存在できるドメインの大きさは、指数的に膨張することになり（いわゆる“次元の呪い”現象）、従って、高次元データ空間上で存在する実際のデータの分布は均一でない。
【００５５】
前述のとおり、次元の分布の均一度は、与えられた二つのデータセットと、限界類似度により動的に決定されるので、類似ジョインのための分割次元は、複数のデータセット間の連関関係を考慮して選択されるべきである。つまり、一つのデータセットに対するデータ分布は、類似ジョイン処理を行うための効率的な分割次元の選択基準ではない。
【００５６】
このような点を考慮して、本発明においては、類似ジョイン処理を行うための効率的な分割次元の選択基準として、二つのデータセットを該当の次元軸にジョインする際、データセットのエントリが対を組み合う回数、すなわち、分割されたセル間のジョインの際の距離計算の回数、つまり、ジョイン演算回数が使用されている。このとき、前記ジョイン演算回数は、各次元軸に対するセル間のジョインコストとして見なされ、各次元軸に対して予め計算されたジョインコストに基づき分割次元を選択するようになる。
【００５７】
図4(a)は、特定のデータセットRとSとに対して予想される距離計算の回数を算出する概念を説明するための概略図である。
【００５８】
データセットR及びSの内の各エントリは、一つの次元軸に対する空間プロジェクションを通して該次元軸の座標値に従いε単位で分割された[1/ ε]個のセルのうち、何れの一つとしてマッピングされる。その後、各次元に対し、各セルに含まれたデータセットR及びSのエントリ数を計算する（S300）。
【００５９】
次に、前記エントリ数を利用して、分割されたセル間のジョインの際の距離計算回数が得られる（S310）が、このとき、 自分と隣り合っているデータセットRのセルと、もしくは、重なっているデータセットSの三つのセル部とのジョインが行われる。すなわち、データセットRの任意の各セルは、自分の左方、自分、及び自分の右方に位置するデータセットSのセルとそれぞれジョインを行う。
【００６０】
例えば、図4(b)に示すように、特定の次元に対してデータセットRがそれぞれ 1個、3個、0個、5個,……のエントリを有し、データセットSがそれぞれ1個、3個、4個、2個,5個……のエントリを有すると仮定すると、距離の計算回数は、{（1x1）＋（1x3）}＋{（3x1）＋（3x3）＋（3x4）}＋{（0x3）＋（0x4）＋（0x2）}＋{（5x4）＋（5x2）＋（5x5）}＋…のように求められる。
【００６１】
最終的に、各次元軸に対して得られた予想の距離の計算回数が小さいほどジョインコストが低いと見なされ、更に、ジョインコストの最も低い次元が分割次元として指定される（S320）。
【００６２】
一方、前記距離の計算回数の算出の際に、実際にデータを分割して格納する必要はなく、ただ、二つのデータセットに対して各セルに属するデータの個数のみを記録すれば良い。すなわち、分割次元を選択するとき、ジョイン演算を実際に行わず、各セルに指定されたエントリ数のみを利用してジョインに必要な距離の計算回数を算出する。
【００６３】
さらに、前記エントリ数を求める際に、全てのデータセットに対して、各セルに指定されたエントリ数を求めるか、もしくはデータセットの一部のみをサンプリングしてエントリ数を求めても良い。
【００６４】
図5は、データセットRとSとに対する分割次元の選択のためのアルゴリズムを示す。図中、アルゴリズムの7〜11ライン、及び12〜16ラインは、各次元に対して各セルに含まれているデータセットRとSのエントリ数を算出する過程を示し、18〜24ラインは、各次元に対してセル間のジョインの際の距離の計算回数を算出する過程を示す。
【図面の簡単な説明】
【００６５】
【図１】本発明を適用するハードウェアの一例を示す構成図である。
【図２】本発明に係る分割による高次元類似ジョイン方法を説明するフローチャートである。
【図３】2次元に対して分割ステップを経た後のデータ空間を示す図である。
【図４】図４(a)と、図４(b)は、特定のデータセットRとSとに対する予想の距離の計算回数を算出する概念を説明するための概略図である。
【図５】データセットR及びSに対する分割次元の選択のためのアルゴリズムを示す図である。
【図６】高次元データが前処理過程を経て、検索、管理されるように、高次元上の一つのポイントにマッピングされる概念を示す図である。
【図７】従来のε-グリッドオーダを利用した類似ジョインにおけるデータ空間を示す図である。
【図８】高次元の空間をセルに分割する際のセル内のデータ分布の不均一さを示す図である。
【符号の説明】
【００６６】
１１ 多重プロセッサ
１２ 主記憶装置のメモリ領域
１５ 入出力処理器
１６ システムバス
【技術分野】
【０００１】
本発明は、高次元類似ジョイン（high-dimensional similarity join）方法に関し、より詳しくは、動的に空間分割次元及び分割次元の個数を予め指定することにより、効率的な類似性（similarity）測定を可能にする次元選択手法を利用した分割による高次元類似ジョイン方法に関する。
【背景技術】
【０００２】
一般に、オーディオ、ビデオ、イメージ、テキストなどのマルチメディアデータ、時間的な順序を表す時系列データ、及び種々のデータウェアハウスに使用される膨大な量のビジネス上のデータは、図６に示すように、前処理過程を経て、検索、管理などが遂行されるように、高次元上の一つのポイント（point）としてマッピングされ、マッピングされたデータ間の類似性は、高次元空間においてユークリッド距離（euclidean distance）により測定される。例えば、二つのイメージファイルの類似性は、高次元の空間上にマッピングされた二つのポイントの間の距離により測定される。
【０００３】
さらに、前記「類似ジョイン」とは、膨大な量のマルチメディアのデータベース、医学のデータベース、科学のデータベース、時系列のデータベースなどから高次元データが入力として提供されるとき、それらのデータセット間の相互類似なデータを効率的に検索することに定義され、特に、イメージ及びマルチメディアのデータシステムと、時系列のデータシステムなどのような高次元データシステムにおいて必須に求められる。
【０００４】
この類似ジョインは、次のようにモデリングすることができる。
【０００５】
まず、ｄ-次元空間上のデータセットＲ、及びＳが存在し、Ｒと、Ｓとに対する任意の元素ｒと、ｓとがそれぞれｒ=[r1,r2,...rd]とｓ=[s1,s2,...sd]とに表れると仮定すれば、類似ジョインは、下記の数１のように公式化される。
【０００６】
【数１】
【０００７】
ここで、pは、特定の距離マトリック（metric）を表し、εは、使用者により定義されたパラメータであって、限界類似度を表すが、RとSとからなるデータ対のうち、空間上の距離がε値よりも小さいデータ対のみを結果として返還する。
【０００８】
現在通用の類似ジョイン方法は、低次元データの場合に効率的であるが、10、100、更に10000に至る非常に大きい次数を求める高次元データに対しては、実行時間、及び所要のシステムストレージの面で極めて非効率的である。
【０００９】
従来の類似ジョイン方法は、代表的なものとして、ε-kdBツリーに基づいた類似ジョイン手法（K.Shim, R.Srikant, 及びR.Agrawalらによる“高次元類似ジョイン”、Proceedings of the 1997 IEEE International Conference on Data Engineering, 1997）と、イプシロン(ε)-グリッドオーダを利用した類似ジョイン手法（C.Bohm,B.Braunmuller,F.Krebs,及びH.-P.Kriegelによる“ε-グリッドオーダ”（epsilon grid order）、大量の高次元データに対する類似ジョインのためのアルゴリズム”、Proceedings of the 2001 ACM-SIGMOD Conference, 2001）などが挙げられる。
【００１０】
ε-kdBツリーに基づく類似ジョイン手法は、データ空間を一つの次元軸に対してイプシロン（ε）面積のセルにそれぞれ分割してデータを格納した後、それらセルに対して多次元インデックス構造のε-kdBツリーを構成する。
【００１１】
このような手法は、データ分割のためのパーティション領域をε単位に制限することにより、ジョイン回数を効率的に低減するが、それぞれのパーティションを表すε-kdBツリー構造をシステムストレージ内に保持すべきであって、データ空間の次元数が増加するほど、所要のシステムストレージも増大することになり、類似ジョインの実行時間も比例して増加することになる。
【００１２】
また、ε-グリッドオーダを利用する類似ジョイン手法においては、データ空間上にセルの長さがεのグリッドを配置し、それらグリッドセルを辞典編纂順に比較することで得られるデータの特別な整列順序に基づいて、高次元データに対する類似ジョインを行う。しかし、このような手法は、ε-ｋｄＢツリーを利用する方法とは異なって、制限されたストレージでも極めて大きいデータセットの効率的なスケーリングを提供するが、図７に示すように、ｐのジョイン対を探し出すするために、 p-[ε.ε. .ε] と p+ [ε.ε. .ε] 間の全てのポイントを考慮しなければならず、次元の増加に伴い、所定の区間内の検索すべきセルの個数が増大することとなり、実行時間も増加するという問題点がある。
【００１３】
一方、低次元空間データシステムにおいて利用される空間分割手法は、高次元データ空間での類似ジョインに適用可能ではあるが、全ての次元軸に対する空間分割が求められ、実用化の側面からみて好ましくない。すなわち、分割されるセルの数は、分割すべき次元軸の数の増加に従い急激に増加し（例えば、各次元軸が10等分される場合、8,16,32,64の各次元に対して生成されるセルの個数は、108,1016,1032,1064となる）、元のデータセットの個数よりも分割されたセルの個数が多くなる結果をもたらす。分割されたセルの個数が増大すると、データスキュー（data skew）現象が甚だしくなり、さらに、空間分割に基づく手法そのものが非効率的になってしまう。ここで、前記「データスキュー現象」とは、図８に示すように、高次元データ空間を各セルにそれぞれ分割する際、セル内のデータ分布が均一でないことを意味する。
【００１４】
従って、短い実行時間で効率的な高次元データの類似ジョインを行い、類似ジョインの実行の際に大量のストレージ空間を必要としない類似ジョイン方法が求められる。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明は、上記問題点に鑑みなされたものであって、相対的に短い実行時間で大量のストレージ空間を要せず、高次元データに対する類似ジョインを効率良く行うことができる分割による高次元類似ジョイン方法を提供することを目的とする。
【００１６】
また、本発明は、類似ジョインの性能を向上し得る分割次元の選択手法を提供することを他の目的とする。このとき、前記分割次元の選択手法は、与えられた複数のデータセットの各軸に対する分布値を用い、動的に最も効率良くデータ空間を分割する次元、及び次元の個数を指定することである。
【課題を解決するための手段】
【００１７】
上記の目的を達成するため、本発明に係る高次元類似ジョイン方法においては、高次元データ空間を分割するステップを含み、前記高次元データ空間を分割する前に、高次元データ空間を分割するための次元、及び次元の個数が予め決定され、所定のデータセット間のジョインを行うステップを含み、前記データセットの各セールは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合のみにジョインを行うことを特徴とする。
【００１８】
そして、前記データセットの各セル間のジョインの際に発生可能なジョイン演算回数を計算するステップを更に含むことを特徴とする。
【００１９】
さらに、前記高次元データ空間を分割するための次元は、前記ジョイン演算回数に基づいて決定されることを特徴とする。
【００２０】
また、前記高次元データ空間を分割するための次元の個数（dp）は、データセットの大きさと、データセットの格納されたディスクブロックの大きさとを比較して求め、下記の式より求められる。
【００２１】
【数２】
【００２２】
ここで、|R|blockと、|S|blockとは、ジョインを行うデータセットRとSとの総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさ、[1/ε]は、各セルの個数である。
【００２３】
さらに、前記ジョイン演算の回数は、各次元に対し、各セルに含まれたデータセットR及びSのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められる。
【００２４】
さらに、前記ジョイン演算の回数は、各次元に対し、サンプリングされた一部のセルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められる。
【００２５】
これらの目的、特徴および利点は、本発明の詳細な説明および添付図面に照らして明らかとなろう。
【発明の効果】
【００２６】
以上のとおり、本発明によると、低次元空間で通用されていた空間分割手法を高次元の空間でも適用可能にし、空間分割によるセルの個数が急激に増加しても、CPU及びIOコストを最適化しながら類似ジョインを行い得るという効果がある。
【００２７】
また、与えられたデータセットの各軸に対する分布値を利用して、動的に最も効率良く空間を分割する次元、及び次元の個数を予め指定することにより、類似ジョインの実行時間を短縮し得るという効果がある。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の好ましい実施の形態を、添付図面に基づいて詳しく説明する。
【００２９】
図１は、本発明を適用するハードウェアの一実施例を示す構成図である。
【００３０】
図1に示すように、システムバス１６を介して、単一、もしくは多重プロセッサ（P1,P2,P3…Pn；１１）、主記憶装置のメモリ領域１２及び入出力処理器１５がそれぞれ連結されており、前記主記憶装置のメモリ領域１２の内には、共有メモリ領域１３が設けられ、前記入出力処理器１５は、補助記憶装置のディスク１４と連結されている。このように、本発明は、単一プロセッサ、もしくは多重プロセッサと、共有メモリ領域とを含む一般のハードウェア環境で作動し得るものである。
【００３１】
以下、本発明に係る分割による高次元類似ジョイン方法について、図２に基づいて説明する。
【００３２】
本発明に係る分割による高次元類似ジョイン方法においては、高次元データ空間を分割するステップ（S100）と、該空間分割を行う前に、高次元データ空間を分割するための次元の個数を決定するステップ（S200〜S220）と、高次元データ空間を分割するための次元を決定するステップ（S300〜S320）と、所定のデータセット間のジョインを行うステップ（S400）とを含んでいる。
【００３３】
そして、前記各ステップについて、より詳しく説明すると、次の通りである。
【００３４】
前記分割ステップ(S100)においては、全データ空間が、限界類似度を表すε単位のセルにそれぞれ分割されており、データ空間上の全てのエントリが単位ハイパーキューブ（hypercube）の内に存在すると仮定するとき、すなわち、各次元軸の範囲が［0，1］の間の場合、各次元は、［1/ε］個のセルに分けられる。さらに、類似ジョインを行うデータセットR及びSの各エントリは、データの前処理過程を経て該当のセルに分散し、格納される。図３は、2次元に対する分割ステップを経た後のデータ空間を示し、図中の小さい正方形は、それぞれ分割されたセルを表す。
【００３５】
また、前記類似ジョインステップ（S400）においては、類似ジョインを行う二つのデータセットから特定の類似性の要求を満足するデータ対を検索するが、このとき、一つのデータセットの各セルを他の一つのデータセットの全てのセルと対を組み合う必要はなく、データ空間上で重なり合っているか、もしくは、隣り合っているセルのみに対を組み合う。一般に、d-次元上での単位ハイパーキューブの境界に存在しない任意のセルが、対を組み合う相手側のセットのセルの数は、3ｄ個となり、例えば、図3の2次元空間でのセルPは、相手側のセットのセルのうち、斜線部分の9個のセルと類似ジョインを行うための対を組み合う。
【００３６】
前述のとおり、高次元類似ジョインを行う場合に、全次元に対してデータ空間を分割すると、分割されたセルの数が急増し、これによりデータスキュー現象が甚だしくなり、ディスクのIO費用が増加することになる。さらに、分割次元の個数が増加すると、データを該当のセルにマッピングするためのハッシュ関数の計算コストも、さらに他の費用負担として作用する。従って、全次元に対して空間を分割せず、次元のうち、データの「均一な分布」を示す幾つかの次元のみを選択して、空間分割を行うことが好ましい。ここで、「均一な分布」は、相対的な概念であって、何れの次元が一つのデータセットに対して均一な分布を示すとしても、他のデータセットに対しては、均一でない分布を示すこともある。また、限界類似度が変わるに従い、次元の分布の均一度も変わる。すなわち、次元の分布の均一度は、与えられた二つのデータセット及び限界類似度に従い、動的に決定される。
【００３７】
従って、本発明においては、全次元に対して空間分割を行わず、次元のうち、データの「均一な分布」示す幾つかの次元のみを選択して空間の分割を行う。
【００３８】
以下、前記空間の分割を行う前に、高次元データ空間を分割するための次元の個数を決めるステップ（S200〜S220）と、高次元データ空間を分割するための次元を決めるステップ（S300〜S320）とについて説明する。
【００３９】
分割次元の個数
高次元空間での二つのデータセットＲ及びＳに対する類似ジョイン処理の際、データの分布が均一であると仮定し、分割次元の個数がdpのとき、R及びSのデータエントリ数をそれぞれ対組み合わせする回数として測定されるCPUコスト（Cost(CPU)）は、下記の数３のように計算される。
【００４０】
【数３】
【００４１】
さらに、R及びSの格納された総ディスクブロック数をそれぞれ、|R|block, |S|blockとすると、ディスクへの接近コストのディスクI/Oコスト（Cost(IO)）は、下記の数４のように計算される。
【００４２】
【数４】
【００４３】
前記数３と数４とによると、分割次元の個数（dp）が増加するほど、CPUコストは減少するが（
【００４４】
【数５】
【００４５】
を仮定するとき）、ディスクI/Oコストはむしろ増加することが分かる。つまり、CPUコストとディスクI/Oコストとは、類似ジョインの性能に関わってお互いに相反する。
【００４６】
このような点を考慮して、本発明においては、データセットの大きさとディスクブロックの大きさとを比較することにより、分割次元の個数を決定する。
【００４７】
例えば、各セルの平均の大きさを、ディスクの一つのブロックと仮定すると、総分割セルの個数（Np）は、下記の数６のように計算される（S200）。
【００４８】
【数６】
【００４９】
ここで、|R|block, |S|blockは、Ｒ及びＳのそれぞれ格納された総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさである。
【００５０】
さらに、空間を所定次元の個数（dp）に分割する際に得られるセルの個数（Np´）は、下記の数７のように計算される（S210）。
【００５１】
【数７】
【００５２】
従って、Np ＝ Np´が成立され、その結果、分割次元の個数（dp）は、下記の数８のように推論される（S220）。
【００５３】
【数８】
【００５４】
分割次元の選択
高次元データ空間でデータが存在できるドメインの大きさは、指数的に膨張することになり（いわゆる“次元の呪い”現象）、従って、高次元データ空間上で存在する実際のデータの分布は均一でない。
【００５５】
前述のとおり、次元の分布の均一度は、与えられた二つのデータセットと、限界類似度により動的に決定されるので、類似ジョインのための分割次元は、複数のデータセット間の連関関係を考慮して選択されるべきである。つまり、一つのデータセットに対するデータ分布は、類似ジョイン処理を行うための効率的な分割次元の選択基準ではない。
【００５６】
このような点を考慮して、本発明においては、類似ジョイン処理を行うための効率的な分割次元の選択基準として、二つのデータセットを該当の次元軸にジョインする際、データセットのエントリが対を組み合う回数、すなわち、分割されたセル間のジョインの際の距離計算の回数、つまり、ジョイン演算回数が使用されている。このとき、前記ジョイン演算回数は、各次元軸に対するセル間のジョインコストとして見なされ、各次元軸に対して予め計算されたジョインコストに基づき分割次元を選択するようになる。
【００５７】
図4(a)は、特定のデータセットRとSとに対して予想される距離計算の回数を算出する概念を説明するための概略図である。
【００５８】
データセットR及びSの内の各エントリは、一つの次元軸に対する空間プロジェクションを通して該次元軸の座標値に従いε単位で分割された[1/ ε]個のセルのうち、何れの一つとしてマッピングされる。その後、各次元に対し、各セルに含まれたデータセットR及びSのエントリ数を計算する（S300）。
【００５９】
次に、前記エントリ数を利用して、分割されたセル間のジョインの際の距離計算回数が得られる（S310）が、このとき、 自分と隣り合っているデータセットRのセルと、もしくは、重なっているデータセットSの三つのセル部とのジョインが行われる。すなわち、データセットRの任意の各セルは、自分の左方、自分、及び自分の右方に位置するデータセットSのセルとそれぞれジョインを行う。
【００６０】
例えば、図4(b)に示すように、特定の次元に対してデータセットRがそれぞれ 1個、3個、0個、5個,……のエントリを有し、データセットSがそれぞれ1個、3個、4個、2個,5個……のエントリを有すると仮定すると、距離の計算回数は、{（1x1）＋（1x3）}＋{（3x1）＋（3x3）＋（3x4）}＋{（0x3）＋（0x4）＋（0x2）}＋{（5x4）＋（5x2）＋（5x5）}＋…のように求められる。
【００６１】
最終的に、各次元軸に対して得られた予想の距離の計算回数が小さいほどジョインコストが低いと見なされ、更に、ジョインコストの最も低い次元が分割次元として指定される（S320）。
【００６２】
一方、前記距離の計算回数の算出の際に、実際にデータを分割して格納する必要はなく、ただ、二つのデータセットに対して各セルに属するデータの個数のみを記録すれば良い。すなわち、分割次元を選択するとき、ジョイン演算を実際に行わず、各セルに指定されたエントリ数のみを利用してジョインに必要な距離の計算回数を算出する。
【００６３】
さらに、前記エントリ数を求める際に、全てのデータセットに対して、各セルに指定されたエントリ数を求めるか、もしくはデータセットの一部のみをサンプリングしてエントリ数を求めても良い。
【００６４】
図5は、データセットRとSとに対する分割次元の選択のためのアルゴリズムを示す。図中、アルゴリズムの7〜11ライン、及び12〜16ラインは、各次元に対して各セルに含まれているデータセットRとSのエントリ数を算出する過程を示し、18〜24ラインは、各次元に対してセル間のジョインの際の距離の計算回数を算出する過程を示す。
【図面の簡単な説明】
【００６５】
【図１】本発明を適用するハードウェアの一例を示す構成図である。
【図２】本発明に係る分割による高次元類似ジョイン方法を説明するフローチャートである。
【図３】2次元に対して分割ステップを経た後のデータ空間を示す図である。
【図４】図４(a)と、図４(b)は、特定のデータセットRとSとに対する予想の距離の計算回数を算出する概念を説明するための概略図である。
【図５】データセットR及びSに対する分割次元の選択のためのアルゴリズムを示す図である。
【図６】高次元データが前処理過程を経て、検索、管理されるように、高次元上の一つのポイントにマッピングされる概念を示す図である。
【図７】従来のε-グリッドオーダを利用した類似ジョインにおけるデータ空間を示す図である。
【図８】高次元の空間をセルに分割する際のセル内のデータ分布の不均一さを示す図である。
【符号の説明】
【００６６】
１１ 多重プロセッサ
１２ 主記憶装置のメモリ領域
１５ 入出力処理器
１６ システムバス
【特許請求の範囲】
【請求項１】
分割による高次元類似ジョイン方法において、
高次元データ空間を分割するための次元、及び次元の個数を予め決定するステップと、
前記決定された次元及び次元の個数に従い、高次元データ空間を分割するステップと、
前記分割された次元に従い、各データセット間のジョインを行うステップとを含み、
前記各データセットの各セルは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合にのみジョインを行うことを特徴とする分割による高次元類似ジョイン方法。
【請求項２】
前記データセットの各セル間のジョインの際に発生可能なジョイン演算回数を計算するステップを更に含むことを特徴とする請求項１に記載の分割による高次元類似ジョイン方法。
【請求項３】
前記高次元データ空間を分割するための次元は、前記ジョイン演算回数に基づいて決定されることを特徴とする請求項２に記載の分割による高次元類似ジョイン方法。
【請求項４】
前記高次元データ空間を分割するための次元の個数dpは、
データセットの大きさと、データセットの格納されたディスクブロックの大きさとを比較して求め、下記の式より求められることを特徴とする請求項２または３に記載の分割による高次元類似ジョイン方法。
【数１】
ここで、|R|blockと、|S|blockとは、ジョインを行うデータセットＲとＳとの総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさ、[1/ε]は、各セルの個数である。
【請求項５】
前記ジョイン演算回数は、各次元に対し、各セルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められることを特徴とする請求項４に記載の分割による高次元類似ジョイン方法。
【請求項６】
前記ジョイン演算の回数は、各次元に対し、サンプリングされた一部のセルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められることを特徴とする請求項４に記載の分割による高次元類似ジョイン方法。
【請求項１】
分割による高次元類似ジョイン方法において、
高次元データ空間を分割するための次元、及び次元の個数を予め決定するステップと、
前記決定された次元及び次元の個数に従い、高次元データ空間を分割するステップと、
前記分割された次元に従い、各データセット間のジョインを行うステップとを含み、
前記各データセットの各セルは、前記データ空間上で重なり合っているか、もしくは隣り合っている場合にのみジョインを行うことを特徴とする分割による高次元類似ジョイン方法。
【請求項２】
前記データセットの各セル間のジョインの際に発生可能なジョイン演算回数を計算するステップを更に含むことを特徴とする請求項１に記載の分割による高次元類似ジョイン方法。
【請求項３】
前記高次元データ空間を分割するための次元は、前記ジョイン演算回数に基づいて決定されることを特徴とする請求項２に記載の分割による高次元類似ジョイン方法。
【請求項４】
前記高次元データ空間を分割するための次元の個数dpは、
データセットの大きさと、データセットの格納されたディスクブロックの大きさとを比較して求め、下記の式より求められることを特徴とする請求項２または３に記載の分割による高次元類似ジョイン方法。
【数１】
ここで、|R|blockと、|S|blockとは、ジョインを行うデータセットＲとＳとの総ディスクブロック数であり、BlockSizeは、ディスクブロックの大きさ、[1/ε]は、各セルの個数である。
【請求項５】
前記ジョイン演算回数は、各次元に対し、各セルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められることを特徴とする請求項４に記載の分割による高次元類似ジョイン方法。
【請求項６】
前記ジョイン演算の回数は、各次元に対し、サンプリングされた一部のセルに含まれたデータセットＲ及びＳのエントリ数を計算した後、各次元に対し、各セル間のジョインの際の距離計算の回数を算出することにより求められることを特徴とする請求項４に記載の分割による高次元類似ジョイン方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００４−１０３０００（Ｐ２００４−１０３０００Ａ）
【公開日】平成１６年４月２日（２００４．４．２）
【国際特許分類】
【出願番号】特願２００３−２８９２６４（Ｐ２００３−２８９２６４）
【出願日】平成１５年８月７日（２００３．８．７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【Ｆターム（参考）】
【公開日】平成１６年４月２日（２００４．４．２）
【国際特許分類】
【出願日】平成１５年８月７日（２００３．８．７）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【Ｆターム（参考）】
[ Back to top ]