(57)【要約】【課題】ｑバケット分割方式に基づく結合処理で使用するメモリ領域が割り当てられた作業スペースを超えないような分割パラメタｑの範囲を見積もり、適切な分割パラメタｑを設定する技術を提供する。【解決手段】結合対象となる複数の入力データに含まれる複数のタプルを対象に分割パラメタｑ（ｑは自然数）と編集距離閾値τ（τは自然数）とを用いてｑバケット分割方式で類似結合処理を実行する結合処理システムであって、入力データのサイズを含む第１の要約情報に基づいて類似結合処理で使用される使用メモリ領域の最大値を示す空間モデルを構築し、類似結合処理に割り当てられる割り当てメモリ領域に相当する作業領域と空間モデルとを用いて、使用メモリ領域の大きさが作業領域の大きさを越えないように分割パラメタｑの範囲を設定する空間最適化手段を備える結合処理システムとする。【選択図】      図２
2015049561.tif 000002
【特許請求の範囲】
【請求項１】
結合対象となる複数の入力データに含まれる複数のタプルを対象に分割パラメタｑ（ｑは自然数）と編集距離閾値τ（τは自然数）とを用いてｑバケット分割方式で類似結合処理を実行する結合処理システムであって、
前記入力データのサイズを含む第１の要約情報に基づいて前記類似結合処理で使用される使用メモリ領域の最大値を示す空間モデルを構築し、前記類似結合処理に割り当てられる割り当てメモリ領域に相当する作業領域と前記空間モデルとを用いて、前記使用メモリ領域の大きさが前記作業領域の大きさを越えないように前記分割パラメタｑの範囲を設定する空間最適化手段を備えることを特徴とする結合処理システム。
【請求項２】
前記空間最適化手段によって設定された前記分割パラメタｑの範囲を取得し、少なくとも前記入力データに含まれる文字列の数を含む第２の要約情報に基づいて前記類似結合処理に要する処理時間を示す時間モデルを構築し、前記分割パラメタｑと前記時間モデルとを用いて、前記類似結合処理の処理時間が最小となる前記分割パラメタｑを設定する時空間最適化手段を備えることを特徴とする請求項１に記載の結合処理システム。
【請求項３】
前記空間最適化手段は、
前記第１の要約情報を取得する第１のデータ観測部と、
前記第１の要約情報を格納する第１のモデル構成要素格納部と、
前記第１の要約情報を用いて前記空間モデルを構築する空間モデル構築部と、
前記空間モデルを用いて、前記使用メモリ領域の大きさが前記作業領域の大きさを越えないように前記分割パラメタｑの範囲を設定する空間最適化部と、を備えることを特徴とする請求項１又は２に記載の結合処理システム。
【請求項４】
前記時空間最適化手段は、
前記第２の要約情報を取得する第２のデータ観測部と、
前記第２の要約情報を格納する第２のモデル構成要素格納部と、
前記第２の要約情報を用いて前記時間モデルを構築する時間モデル構築部と、
前記時間モデル及び前記分割パラメタの範囲を用いて、前記類似結合処理に要する処理時間が最小となる前記分割パラメタｑを設定する時間最適化部と、を備えることを特徴とする請求項２又は３に記載の結合処理システム。
【請求項５】
結合対象となる複数の前記入力データを管理し、前記入力データに含まれる前記タプルに関する情報として少なくとも前記タプルを結合するために用いられる結合キー文字列の文字配置情報、前記結合キー文字列における前記文字シーケンスの位置情報及び前記結合キー文字列を含む前記タプルの識別情報を含む結合キー情報を抽出し、抽出した前記結合キー文字列を前記文字シーケンスが付されたバケットに振り分けるデータ管理手段と、
前記バケットを有し、前記結合キー情報を取得し、前記バケット内で複数の前記結合キー情報同士を前記編集距離閾値τを用いて突き合わせる結合処理手段と、を備えることを特徴とする請求項１乃至４のいずれか一項に記載の結合処理システム。
【請求項６】
前記空間モデル構築部は、
全ての前記文字シーケンスに含まれる文字のうち再頻出文字をｚｉｐｆ関数によって近似し、
前記入力データの大きさ、前記文字シーケンスの数及び前記ｚｉｐｆ関数による近似を基に、前記空間モデルを構築することを特徴とする請求項３乃至５のいずれか一項に記載の結合処理システム。
【請求項７】
前記空間モデル構築部は、
特定の範囲に属する整数値を前記分割パラメタｑとして設定し、前記入力データに含まれる少なくとも一つの文字列を特定の確率で選択することによって生成された部分データを用いて前記分割パラメタに対応する仮の空間モデルを構築し、前記仮の空間モデルを前記特定の確率で除すことによって前記空間モデルを構築することを特徴とする請求項３乃至６のいずれか一項に記載の結合処理システム。
【請求項８】
複数の中央演算処理装置を持つ情報処理装置を用いて前記結合処理を並列処理する結合処理システムであって、
それぞれの前記複数の中央演算処理装置に対応して少なくとも１つの前記バケットが設定され、前記文字シーケンスが付された前記バケットに前記結合キー情報が収容されると、
前記空間最適化手段は、
前記複数の中央演算処理装置で並列して前記使用メモリ領域の大きさの総和が前記作業領域を越えないように前記分割パラメタｑの範囲を設定することを特徴とする請求項５乃至７のいずれか一項に記載の結合処理システム。
【請求項９】
前記時空間最適化手段は、
前記入力データに含まれる全ての前記結合キー情報を前記バケットに振り分けるのに要する処理時間と、全ての前記バケット内において前記結合キー情報のペアを付き合わせるのに要する処理時間と、前記バケット内で結合された前記結合キー情報のペアを基に前記入力データに含まれる前記タプルのペアを結合してマージするのに要する処理時間との総和によって前記時間モデルを構築することを特徴とする請求項５乃至８のいずれか一項に記載の結合処理システム。
【請求項１０】
結合対象となる複数の入力データに含まれる複数のタプルを対象に分割パラメタｑ（ｑは自然数）と編集距離閾値τ（τは自然数）とを用いてｑバケット分割方式で類似結合処理を実行する結合処理方法であって、
前記入力データのサイズを含む第１の要約情報に基づいて前記類似結合処理で使用される使用メモリ領域の最大値を示す空間モデルを構築し、前記類似結合処理に割り当てられる割り当てメモリ領域に相当する作業領域と前記空間モデルとを用いて、前記使用メモリ領域の大きさが前記作業領域の大きさを越えないように前記分割パラメタｑの範囲を設定することを特徴とする結合処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似した文字列を結合する技術を用いた結合処理システム及び文字列結合処理方法に関する。特に、本発明は、類似した文字列を含むタプル同士を結合する文字列類似結合技術に用いられる結合処理システム及び結合処理方法に関する。
【背景技術】
【０００２】
文字列類似結合（Ｓｔｒｉｎｇ  Ｓｉｍｉｌａｒｉｔｙ  Ｊｏｉｎ）は、類似する文字列を含むタプル同士を結合する処理である。文字列類似結合においては、完全に一致した文字列を持たなくても、特定の閾値条件を満たす類似した文字列を持つタプル同士であれば結合する。
【０００３】
図１９及び図２０は、文字列間の編集距離を閾値条件とした文字列類似結合に関する図である。編集距離とは、文字列間の距離を測る尺度の一つであり、ある文字列を別の文字列に変換させるのに必要となる手順の最小回数のことを言う。ある文字列を別の文字列に変換させる手順としては、文字の挿入、削除及び置換を挙げられる。
【０００４】
ここで、２つの文字列「ｋｉｔｔｅｎ」と「ｓｉｔｔｉｎｇ」との変換の例を挙げて、編集距離について説明する。第１に、「ｋｉｔｔｅｎ」の左から１文字目の「ｋ」を「ｓ」に置換する。第２に、「ｋｉｔｔｅｎ」の左から５文字目の「ｅ」を「ｉ」に置換する。第３に、「ｋｉｔｔｅｎ」の右端に「ｇ」を挿入する。以上の３つの手順を組み合わせることによって、文字列「ｋｉｔｔｅｎ」が文字列「ｓｉｔｔｉｎｇ」に変換される。すなわち、「ｋｉｔｔｅｎ」から「ｓｉｔｔｉｎｇ」への変換においては、少なくとも２回の置換と１回の挿入からなる３つの手順が必要となり、編集距離は３となる。
【０００５】
図１９において、要素集合であるテーブルＡ１００は、それぞれのＩＤに対応させた名前と年代とを属性として持つ複数のタプルから構成されている（ＩＤ：Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）。また、図１９において、要素集合であるテーブルＢ２００は、それぞれのＩＤに対応させた名前’と住所とを属性として持つ複数のタプルから構成されている。そして、図２０のテーブルＣ３００は、テーブルＡ１００の「名前」属性とテーブルＢ２００の「名前’」属性を結合キー文字列として、編集距離閾値条件に基づいて文字列類似結合を施した結果である。図１９及び図２０の例では、編集距離が２以下（編集距離閾値２）となる各タプル同士が結合される例を示しており、テーブルＡ１００及びテーブルＢ２００において類似する文字列を含むタプル同士が結合されていることを示す。
【０００６】
文字列類似結合は、結合したい文字列のデータが与えられたら、潜在的にあらゆる文字列のペアに対して類似度又は距離を計算する必要がある。そのため、一般的な文字列類似結合においては、処理時間に無駄があるという問題点がある。
【０００７】
特許文献１、非特許文献１及び非特許文献２には、編集距離を用いた文字列類似結合を高速化するために、文字列を複数のバケットに分配し、バケットごとに独立して結合処理を施す並列化手法が提案されている。
【０００８】
特許文献１及び非特許文献１で提案されている方法によれば、結合対象となる文字列データ及び編集距離閾値τを取得する。そして、各文字列の先端文字又は末端文字からτ＋１個までの文字をチェックし、当該文字列をτ＋１個の各文字に１対１対応するバケットへそれぞれ分配する。さらに、バケットごとに独立して結合処理を行った後、各バケットの結合結果を１つにまとめて最終的な結合結果を出力する。
【０００９】
非特許文献２で提案されている方法によれば、結合対象となる文字列データと、編集距離閾値τと、２以上の整数ｒと、を取得する。次に、各文字列の先端文字又は末端文字からτ＋ｒ個までの文字をチェックし、τ＋ｒ個の文字の中からｒ個の文字を、順番を維持したままで選択して長さｒのシーケンス（以下、文字シーケンス）を生成し、当該文字列を当該シーケンスに１対１対応するバケットへそれぞれ分配する。そして、バケットごとに独立して文字列結合を行った後、各バケットにおける結合結果を１つにまとめて最終的な結合結果を出力する。
【００１０】
特許文献１、非特許文献１及び２で提案されている技術には、以下のような共通点がある。まず、文字列の先端文字又は末端文字からτ＋ｑ（ｑは１以上の整数）個の文字をチェックし、その中から文字の順番を維持したままｑ個の文字を選択して文字シーケンスを生成する。そして、文字シーケンスをラベルとして付されたバケットに、文字シーケンスに基づいて文字列を分配し、バケットごとに独立して結合処理を行う。このような３文献に共通する結合処理の方式を、これ以降「ｑバケット分割方式」と呼ぶ。また、文字シーケンスの長さ（文字の数）ｑを分割パラメタｑと呼ぶ。
【００１１】
ｑバケット分割方式においては、文字列データに含まれる各文字列が同時に複数のバケットに分配されうる。また、ｑバケット分割方式には、分割パラメタｑが大きいほど、１つのバケットに含まれる文字列の数の平均は小さくなり、バケットの総数が大きくなる性質がある。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】国際公開２０１２／１０４９４３号公報
【非特許文献】
【００１３】
【非特許文献１】成田和世、中台慎二、「編集距離制約下におけるトライを用いた高速並列類似結合」、第３回データ工学と情報マネジメントに関するフォーラム（ＤＥＩＭ）（２０１１）
【非特許文献２】Ｋ．Ｎａｒｉｔａ、Ｓ．Ｎａｋａｄａｉ  ａｎｄ  Ｔ．Ａｒａｋｉ，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  １４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｗａｒｅｈｏｕｓｉｎｇ  ａｎｄ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  （ＤａＷａＫ）、ｐ．８０−１９１（２０１２）
【発明の概要】
【発明が解決しようとする課題】
【００１４】
一般的なｑバケット分割方式に基づいて文字列類似結合を行う場合、分割パラメタｑが小さいと、１つのバケットに含まれる文字列の数が膨大になる。そのため、バケットに割り当てられるメモリ上の領域の大きさが、計算機に割り当てられた作業スペースを超えてしまい、処理できなくなるという課題がある。特許文献１及び非特許文献１においては、分割パラメタｑは常に１と小さいため、特にこの課題に直面しやすい。また、非特許文献２においては、分割パラメタｑに小さい整数を設定した場合、同じ課題が発生しやすい。
【００１５】
また、上述の課題を回避するために非特許文献２の方法を選択し、分割パラメタｑをあまりにも大きく設定すると、処理時間が延びるという課題がある。分割パラメタｑが大きすぎると、１つの文字列がより多くのバケットに分配され、全く同じ文字列ペアの編集距離計算が多くのバケットで行われる確率が高くなる。このような冗長な計算の回数が増大することにより、余計な処理時間が掛かってしまう。
【００１６】
本発明の第１の目的は、ｑバケット分割方式に基づく結合処理で使用するメモリ領域が割り当てられた作業スペースを超えないような分割パラメタｑの範囲を見積もり、適切な分割パラメタｑを設定する技術を提供することにある。
【００１７】
また、本発明の第２の目的は、ｑバケット分割方式に基づいて文字列類似結合を行う場合において、処理時間が最も小さくなるように、得るべき分割パラメタｑを適切に算出する技術を提供することにある。
【課題を解決するための手段】
【００１８】
本発明の結合処理システムは、結合対象となる複数の入力データに含まれる複数のタプルを対象に分割パラメタｑ（ｑは自然数）と編集距離閾値τ（τは自然数）とを用いてｑバケット分割方式で類似結合処理を実行する結合処理システムであって、入力データのサイズを含む第１の要約情報に基づいて類似結合処理で使用される使用メモリ領域の最大値を示す空間モデルを構築し、類似結合処理に割り当てられる割り当てメモリ領域に相当する作業領域と空間モデルとを用いて、使用メモリ領域の大きさが作業領域の大きさを越えないように分割パラメタｑの範囲を設定する空間最適化手段を備える。
【００１９】
本発明の結合処理方法は、結合対象となる複数の入力データに含まれる複数のタプルを対象に分割パラメタｑ（ｑは自然数）と編集距離閾値τ（τは自然数）とを用いてｑバケット分割方式で類似結合処理を実行する結合処理方法であって、入力データのサイズを含む第１の要約情報に基づいて類似結合処理で使用される使用メモリ領域の最大値を示す空間モデルを構築し、類似結合処理に割り当てられる割り当てメモリ領域に相当する作業領域と空間モデルとを用いて、使用メモリ領域の大きさが作業領域の大きさを越えないように分割パラメタｑの範囲を設定する。
【発明の効果】
【００２０】
本発明によれば、ｑバケット分割方式に基づく結合処理で使用するメモリ領域が割り当てられた作業スペースを超えないような分割パラメタｑの範囲を見積もり、適切な分割パラメタｑを設定することが可能となる。そのため、結合処理で使用するバケットに割り当てられる最大メモリ量が計算機の作業スペースを超えて処理が途中で止まることを回避することができるという第１の効果を得られる。
【００２１】
また、本発明によれば、ｑバケット分割方式に基づく結合処理において、処理時間が最も小さくなるように、得るべき分割パラメタｑを適切に算出することができる。そのため、第１の効果を享受しつつ、処理時間が最小となる分割パラメタｑの値を自動的に最適化できるという第２の効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施形態に係る結合処理システムの構成を示すブロック図である。
【図２】本発明の第１の実施形態に係る空間最適化装置の構成を示すブロック図である。
【図３】本発明の第１の実施形態に係る空間最適化処理を説明するための図である。
【図４】本発明の第１の実施形態に係る結合処理システムの動作を示すフローチャートである。
【図５】本発明の第１の実施形態に係る空間最適化装置の動作を示すフローチャートである。
【図６】本発明の第２の実施形態に係る結合処理システムの構成を示すブロック図である。
【図７】本発明の第２の実施形態に係る時空間最適化装置の構成を示すブロック図である。
【図８】本発明の第２の実施形態に係る時空間最適化処理を説明するための図である。
【図９】本発明の第２の実施形態に係る時空間最適化処理を説明するための図である。
【図１０】本発明の第２の実施形態に係る結合処理システムの動作を示すフローチャートである。
【図１１】本発明の第２の実施形態に係る空間最適化装置の動作を示すフローチャートである。
【図１２】本発明の第２の実施形態に係る時空間最適化装置の動作を示すフローチャートである。
【図１３】本発明の実施例１に係る数理モデルに基づく空間モデル構築法を説明するための図である。
【図１４】本発明の実施例２に係るサンプリングに基づく空間モデル構築法を説明するための図である。
【図１５】本発明の実施形態に係る処理を単一の計算機で実行するための概念図である。
【図１６】本発明の実施形態に係る処理を複数の計算機で実行するための概念図である。
【図１７】本発明の実施例３に係る処理をＮコア計算機で実行するための概念図である。
【図１８】本発明の実施例４に係る処理時間モデルの構築を説明するための図である。
【図１９】本発明の実施例４に係る時間モデルの構築を説明するための図である。
【図２０】一般的な文字列類似結合を説明するための図である。
【発明を実施するための形態】
【００２３】
以下に、本発明を実施するための形態について図面を用いて説明する。ただし、以下に述べる実施形態には、本発明を実施するために技術的に好ましい限定がされているが、発明の範囲を以下に限定するものではない。
【００２４】
（ｑバケット分割方式）
初めに、本発明の実施形態に係るｑバケット分割方式について説明する（ｑは自然数）。
【００２５】
本発明の実施形態に係る文字列類似結合処理において結合対象となるデータ（表）は、複数のタプル（行）を含む表である。それぞれのタプルは、例えば、タプル識別子、結合キー文字列、データ情報などといった複数の属性値を含む。
【００２６】
タプル識別子は、それぞれのタプルを特定するための識別情報（ＩＤ）であり、ＩＤの属性値となる。結合キー文字列は、異なるデータに属するタプル同士を結合するためのキーとなる文字列であり、文字列類似結合処理においては、編集距離を考慮して突き合わせを行う対象となる。結合キー文字列は、例えば、名前などの属性値である。データ情報は、タプルに含まれる情報である。なお、データにはここで挙げた属性値以外の要素を含んでいてもよい。
【００２７】
ｑバケット分割方式では、まず、文字列の端部文字（先端文字又は末端文字）からτ＋ｑ（ｑは１以上の整数）個の文字をチェックし、その中から順番を維持したままｑ個の文字を選択してシーケンス（文字シーケンス）を生成する。そして、各文字シーケンスをラベルとして持つバケットを生成する。さらに、ラベルとなる文字シーケンスに基づいて文字列をバケットに分配し、バケットごとに独立して結合処理を行う。バケットに付された文字シーケンスを含む文字列は、その文字シーケンスが付されたバケットに振り分けられる。単一のバケット内には、同じ文字シーケンスを含む文字列が分配されることになる。なお、文字シーケンスに含まれる文字がその並び順を維持しながら間隔を空けて配置された文字列も、その文字シーケンスを含む文字列であり、その文字シーケンスを付されたバケットに振り分けられる。
【００２８】
文字シーケンスとは、結合キー文字列の端部文字列（先端部文字列又は末端部文字列）から抽出される並び順が維持されたｑ個の文字からなる文字列である。文字シーケンスの長さに相当するｑは、分割パラメタｑとも呼ぶ。結合キー文字列とは、結合対象となる入力データを構成するタプル同士を結合するためのキーとなる文字列である。結合キー文字列の端部文字列とは、例えば、結合キー文字列の端部文字（先端文字又は末端文字）を起点とし、その端部文字を起点として数えた（τ＋ｑ）個の文字を、並び順を変えずに抜き出した文字列である。端部文字列は、結合キー文字列の両端部（先端部及び末端部）から一つずつ抽出することができる。なお、本実施形態においては、結合キー文字列を単に文字列と記載することもある。
【００２９】
ここで、「ＡＢＣＤ・・・ＷＸＹＺ」という結合キー文字列を例として説明する。編集距離閾値τが１で、分割パラメタｑが３とすると、編集距離閾値τと分割パラメタｑとの和（τ＋ｑ）は４になる。すなわち、端部文字列（先端部文字列又は末端部文字列）は４個の文字から構成される。
【００３０】
先端を起点とする場合、結合キー文字列「ＡＢＣＤ・・・ＷＸＹＺ」の先端文字「Ａ」を基点とする４文字である「ＡＢＣＤ」が先端部文字列に設定され、「ＡＢＣ」、「ＡＢＤ」、「ＡＣＤ」、「ＢＣＤ」という４個の文字シーケンスが生成される。なお、末端を起点とする場合は、結合キー文字列「ＡＢＣＤ・・・ＷＸＹＺ」の末端文字「Ｚ」を基点とする４文字である「ＷＸＹＺ」が末端部文字列に設定され、「ＷＸＹ」、「ＷＸＺ」、「ＷＹＺ」、「ＸＹＺ」という４個の文字シーケンスが生成される。
【００３１】
先端部文字列「ＡＢＣＤ」から生成される文字シーケンスの数は、４個の文字の中から３個の文字を順不問で組み合わせる数に相当するため、４となる。同様に、結合対象となる他の文字列に対しても文字シーケンスを生成する。そして、結合対象となる文字列から生成された各文字シーケンスをラベルとして持つバケットを、各文字シーケンスに対して一対一に対応するように設定する。
【００３２】
ｑバケット分割方式では、結合対象となる文字列のうち、対応する文字シーケンスを結合キー情報に含む全ての結合キー情報を、その文字シーケンスをラベルとするバケットに振り分ける。同じ文字シーケンスを持つ結合キー情報の集まりがバケットを形成すると言い換えることもできる。ここで、結合キー情報とは、文字シーケンスを基に生成される結合キー文字列の文字配置情報を含むとともに、各結合キー文字列を含むタプルへの紐付けを持つ情報であり、特許文献１のＳＩＰタプルに相当する。各バケット内では、全ての結合キー情報同士で突き合わせが実行され、編集距離閾値条件を満たす結合キー情報同士が結合される。最終的には、実行した突き合わせの結果を反映させて、元となるタプル同士を結合することができる。なお、結合された結合キー情報同士は、結合キー情報の元となる結合キー文字列同士の間で編集距離閾値τが所定の値（この例においては１）以上に離れている場合は、結合を解消することになる。
【００３３】
例えば、結合キー文字列「ＡＢＣＤ・・・ＷＸＹＺ」、「ＡＢＣＥ・・・ＷＸＸＺ」及び「ＡＢＤＥ・・・ＷＸＺＺ」を入力する。編集距離閾値τを１、分割パラメタｑを３とすると、例えば、文字シーケンス「ＡＢＣ」というラベルを持つバケットには、「ＡＢＣＤ・・・ＷＸＹＺ」及び「ＡＢＣＥ・・・ＷＸＸＺ」の結合キー情報が振り分けられる。
【００３４】
結合キー情報としては、例えば、キー情報文字列の一端から文字シーケンスを生成する場合、他端を含む文字列からなる部分文字列と、キー情報文字列中における文字シーケンスの位置情報と、タプルの識別子とが含まれればよい。また、結合キー情報を複数の装置間で共有する場合、処理を実行する装置のネットワークアドレス情報（例えば、ＩＰアドレス）を結合キー情報に含めてもよい（ＩＰ：Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）。なお、本発明の実施形態においては、同じバケット内で突き合わせが実行可能となり、その突き合わせの結果を基に、元となるタプル同士を結合することができさえすれば、バケットに振り分ける結合キー情報の形態に限定は加えない。また、結合キー情報自体が、結合対象の文字列そのものであっても構わない。
【００３５】
各バケットにおいては、各バケットに振り分けられた結合キー情報同士で突き合わせを実行する。なお、同一のバケット内に結合キー情報が一つしかない場合は、突き合わせは実行されない。また、突き合わせが実行されなかったバケットに振り分けられた結合キー情報については、編集距離閾値条件を満たす結合キー情報を持つ文字列が存在しないことを意味するため、それらの結合キー情報の元となるタプル同士を結合する必要はない。そのため、バケット内に振り分けられ、かつ突き合わせによって結合された結合キー情報の元となるタプル同士のみについて、結合キー文字列の全文字に関して突き合わせを実行すればよい。
【００３６】
最終的なタプルの結合に関しては、各バケットにおいて結合されたタプルペアに対して、結合キー文字列を構成する全ての文字について突き合わせを実行すればよい。そのため、各バケット内では結合されたものの、最終的な突き合わせの段階で編集距離閾値条件を満たさずに結合されないタプルペアが存在しても構わない。
【００３７】
以上が、本発明の実施形態に係るｑバケット分割方式についての説明である。なお、上述の説明は一例であって、ここで挙げた例によって本発明の範囲を限定するわけではない。
【００３８】
以下においては、本発明の実施形態について、具体的な構成及び動作について説明する。なお、本発明の第１の実施形態に係る結合処理システムは、ｑバケット分割方式に基づいた結合処理で使用するメモリ領域（使用メモリ領域とも呼ぶ）が、割り当てられたメモリ領域である作業スペース（割り当てメモリ領域とも呼ぶ）のサイズＭを越えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを設定する空間最適化手段を備える。さらに、本発明の第２の実施形態に係る結合処理システムは、空間最適化手段によって設定された範囲ｑ＿ｒａｎｇｅを基に、処理時間が最小となる分割パラメタｑを自動的に最適化する時空間最適化手段を備える。
【００３９】
（第１の実施形態）
まず、本発明の第１の実施形態に係る結合処理システム１について説明する。図１は、第１の実施形態に係る結合処理システム１の構成例を概念的に表すブロック図である。
【００４０】
図１のように、第１の実施形態に係る結合処理システム１は、空間最適化装置１０（空間最適化手段）と、結合処理装置３０（結合処理手段）と、データ管理装置４０（データ管理手段）と、を備える。なお、図１には、２つのデータ管理装置４０（４０−１、４０−２）を図示したが、データ管理装置４０は単独であってもよく、３つ以上で構成されていてもよく、その数は限定しない。また、空間最適化装置１０及び結合処理装置３０も、複数の装置で構成されていてもよく、その数は限定しない。
【００４１】
空間最適化装置１０と、結合処理装置３０と、データ管理装置４０とは、それぞれ少なくともＣＰＵ６、メモリ７及び入出力Ｉ／Ｆ８を含む（Ｉ／Ｆ：Ｉｎｔｅｒｆａｃｅ）。なお、空間最適化装置１０、結合処理装置３０及びデータ管理装置４０が有するＣＰＵ６、メモリ７及び入出力Ｉ／Ｆ８は、それぞれの構成要素に関して異なる性能等を有するとしても、本明細書中では同一の符号で示す。空間最適化装置１０、結合処理装置３０及びデータ管理装置４０は、例えば、コンピュータやサーバなどによって実現される。
【００４２】
空間最適化装置１０と、結合処理装置３０と、データ管理装置４０とは、互いにネットワーク５を介してデータ授受できるように接続されている。例えば、ネットワーク５としては、インターネットや電話回線などの公衆回線、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、無線通信ネットワークなどによって実現される。また、結合処理システム１は、必要に応じて、結合処理システム１を制御するシステム制御装置（図示しない）を備えていてもよい。また、空間最適化装置１０、結合処理装置３０及びデータ管理装置４０が同一のコンピュータやサーバ内に構成された要素としてもよい。その場合、ネットワーク５の機能の一部は、コンピュータやサーバを構成する内部配線や接続ケーブル等に負わせればよく、単一のコンピュータ又はサーバ内部に結合処理システム１を含めた構成としてもよい。なお、結合処理システム１の各構成要素間を接続する手段は、ここに挙げたものに限定されない。
【００４３】
（空間最適化装置）
次に、本発明の第１の実施形態に係る空間最適化装置１０について説明する。図２は、第１の実施形態に係る空間最適化装置１０の構成を示すブロック図である。
【００４４】
図２のように、空間最適化装置１０は、空間最適化部１１と、データ観測部１２（第１のデータ観測部）と、モデル構成要素格納部１３（第１のモデル構成要素格納部）と、空間モデル構築部１４とを有する。なお、図２においては、各構成要素間の主な接続関係のみを線で示しており、全ての接続を図示しているわけではない。
【００４５】
本実施形態における空間モデルとは、結合処理装置３０がｑバケット分割方式に基づく文字列類似結合を完了させるまでに使用するメモリ領域の最大値をモデル化したものである。具体的な空間モデルＢ（ｑ）の設定方法については、後述の実施例において説明する。
【００４６】
空間最適化部１１と、データ観測部１２と、空間モデル構築部１４とは、例えば、ＣＰＵによりメモリに格納されるプログラムが実行されることで実現される（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）。また、モデル構成要素格納部１３は、例えば、メモリ上に実現される。
【００４７】
空間最適化部１１は、外部からパラメタ推定命令を取得すると、データ観測部１２及び空間モデル構築部１４に対して、パラメタ推定命令を実行するための推定実行命令を送る。パラメタ推定命令は、例えば、システム制御装置（図示しない）や外部の管理端末（図示しない）などから出され、結合処理対象となる入力データに関して、分割パラメタｑを設定するための空間モデルＢ（ｑ）を構築する命令を含む。なお、分割パラメタｑは、文字シーケンスの文字数（長さ）に相当するパラメタである。
【００４８】
また、空間最適化部１１は、後述する空間モデル構築部１４が生成した空間モデルＢ（ｑ）を受信し、結合処理に用いるメモリ上の最大使用領域が設定された作業スペースの大きさＭを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを推定する。なお、作業スペースとは、結合処理を実行するためにメモリ上に割り当てられた処理領域である。
【００４９】
図３は、本発明の第１の実施形態における分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）を示している。実際には、空間最適化部１１によって、分割パラメタｑの範囲ｑ＿ｒａｎｇｅの下限が設定されることになる。なお、必要に応じて、分割パラメタｑの範囲ｑ＿ｒａｎｇｅの上限を設定してもよい。
【００５０】
空間モデル構築部１４によって空間モデルＢ（ｑ）が設定されると、空間最適化部１１は、結合処理で使用するメモリ領域が、割り当てられた作業スペースのサイズＭを越えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）を推定する。
【００５１】
図３では、空間モデルＢ（ｑ）に関する曲線と、作業スペースのサイズＭに関する直線（破線）との交点の横軸座標ｑｍが下限となり、分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）が設定される様子を示している。本実施形態においては、ｑ＿ｒａｎｇｅに属する任意の整数を、分割パラメタｑとして設定することができる。なお、必要に応じて分割パラメタｑの上限を定めてもよい。
【００５２】
また、空間最適化部１１は、当該ｑ＿ｒａｎｇｅに属する任意の整数を分割パラメタｑとして推定し、推定された分割パラメタｑを結合処理装置３０に送信する。
【００５３】
データ観測部１２は、空間最適化部１１から推定実行命令を受け取ると、入出力Ｉ／Ｆ８の通信インタフェースを介して、データ管理装置４０が管理する結合対象データから、空間モデルＢ（ｑ）を構築するために必要となるデータの要約情報（第１の要約情報）を観測する。そして、データ観測部１２は、観測した要約情報（第１の要約情報）をモデル構成要素格納部１３に格納する（Ｉ／Ｆ：Ｉｎｔｅｒｆａｃｅ）。
【００５４】
本実施形態における要約情報（第１の要約情報）は、例えば、入力データサイズ等を含む。また、本実施形態における要約情報（第１の要約情報）としては、編集距離閾値τ、処理対象文字列の総数、処理対象文字列に出現する特徴的な文字の出現頻度分布、処理対象文字列に含まれる文字列の長さの出現頻度分布、処理対象文字列に含まれる最長の文字列長などを含んでいてもよい。ただし、本実施形態における要約情報は、空間モデルＢ（ｑ）を推定するのに必要な情報であればここで挙げたものに限らない。
【００５５】
モデル構成要素格納部１３は、データ観測部１２によって観測された要約情報を格納・管理する。
【００５６】
空間モデル構築部１４は、モデル構成要素格納部１３に要約情報が格納されると、当該要約情報を用いて空間モデルＢ（ｑ）を構築する。
【００５７】
以上が、本発明の第１の実施形態に係る空間最適化装置１０の構成に関する説明である。
【００５８】
（結合処理装置）
続いて、本発明の第１の実施形態に係る結合処理装置３０について説明する。
【００５９】
結合処理装置３０は、結合対象となる文字列データと、編集距離閾値τと、分割パラメタｑとを取得し、ｑバケット分割方式に基づき結合処理を実施する装置である。なお、結合処理装置３０は、少なくともバケットに振り分けられた結合キー情報について突き合わせを実行すればよい。結合キー情報の元となるタプル同士の結合は、例えば、図示しないシステム制御装置又は管理装置に実行させればよい。
【００６０】
結合処理装置３０は、例えば、結合処理システム１の管理者や図示しないシステム制御装置によって設定された編集距離閾値τを取得する。結合処理装置３０は、空間最適化装置１０から分割パラメタｑを取得し、データ管理装置４０から結合対象となる文字列データを取得する。なお、本実施形態においては、データ管理装置４０によって生成された後述するキー情報タプル（結合キー情報）を文字列データとし、結合処理装置３０がキー情報タプルを用いて結合処理を実行するように記載している。しかしながら、結合処理装置３０が、キー情報タプルを生成し、生成したキー情報タプルを用いて結合処理を実行するように構成させてもよい。
【００６１】
本発明の実施形態における編集距離とは、文字の挿入・削除・置換を組み合わせて、一つの文字列を別の文字列に変形するのに必要な編集手順の最小回数のことを呼ぶ。なお、本実施形態の編集距離においては、挿入・削除・置換の他に、転置・移動・複写などの編集手順も適用し、これらの編集手順を任意に組み合わせたものであってもよい。また、挿入・削除・置換といった編集手順に対して、例えば、挿入には３、削除には１などというように重み付けを設定し、その重み付けを考慮した編集距離を用いてもよい。さらには、編集距離を文字列の長さで割って標準化した編集距離を用いてもよい。
【００６２】
結合処理装置３０は、複数のタプルを対象にして、ｑバケット分割方式によって類似結合処理を実行する。結合処理装置３０は、類似結合処理を実行し得る単位を示しており、例えば、ＣＰＵ６、メモリ７、入出力Ｉ／Ｆ８を含む一つのコンピュータで実現することができる。また、複数のＣＰＵからなるコンピュータであれば、１つのＣＰＵに結合処理装置３０の機能を負わせ、単一のコンピュータ内部に複数の結合処理装置が形成されるように実現してもよい。
【００６３】
結合処理装置３０は、ネットワーク５を介して、空間最適化装置１０及びデータ管理装置４０と通信可能に接続されており、処理ホストの役割を負う。
【００６４】
一般的な結合処理においては、類似する文字列データを含む全てのタプルペアに対して、以下の式１に示した閾値条件を満たすタプルペアを全て列挙する。なお、式１において、ｅｄ（Ｘ、Ｙ）は文字列Ｘと文字列Ｙの編集距離である。
ｅｄ（Ｘ、Ｙ）≦τ・・・（１）
一般的な結合処理において、式１の閾値条件を満たすタプルペアを全て列挙するには、全てのタプルペアに対して突き合わせを行う必要があり、処理コストが増大することになる。本実施形態によれば、例えば、複数のタプルの結合キー文字列における先端文字又は末端文字の端部分に共通する文字を持たないタプルペアを、編集距離計算対象から除外することによって、結合処理における処理コストを低減することができる。
【００６５】
また、本実施形態に係る結合処理において、結合処理装置３０は、結合対象となるデータから抽出したキー情報タプル同士で突き合わせを実行すればよい。この場合、結合処理装置３０は、キー情報タプル同士の突き合わせの結果を外部のシステム制御装置や管理装置に出力し、システム制御装置や管理装置によって、キー情報タプルに含まれる識別子情報を基に実サイズのタプル同士を結合させればよい。
【００６６】
以上が、本発明の第１の実施形態に係る結合処理装置３０についての説明である。
【００６７】
（データ管理装置）
続いて、本発明の第１の実施形態に係るデータ管理装置４０について説明する。
【００６８】
データ管理装置４０は、結合対象データを管理する装置である。図１には、２つのデータ管理装置４０（４０−１、４０−２）を示しているが、データ管理装置４０は単一であってもよく、また、３つ以上の複数で構成されていてもよい。
【００６９】
データ管理装置４０は、結合処理対象となる少なくとも１つのデータを管理し、例えば、ＣＰＵ６、メモリ７及び入出力Ｉ／Ｆ８を含む一つのコンピュータによって実現できる。なお、データ管理装置４０は、ハードディスク等の大容量記憶装置を内蔵し、ストレージ機能を有することが好ましい。
【００７０】
データ管理装置４０が管理するデータは、例えば、複数のタプルからなる表（タプル集合）である。データを構成する各タプルは、タプル識別子、結合キー文字列、データ情報などの複数の属性値を含む。
【００７１】
以下の説明においては、データ管理装置４０がキー情報タプルを生成するものとする。なお、キー情報タプルを結合処理装置３０で生成する構成とする場合、格納したタプルを加工せずに結合処理装置３０に送信するようにすればよい。
【００７２】
タプル識別子は、タプルを特定するための識別情報（ＩＤ：Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）であり、各タプルに対して異なる値が設定される。例えば、タプル識別子は、整数型のデータとして構成することができる。図８においては、「ＩＤ」がタプル識別子に相当する。
【００７３】
結合キー文字列は、タプルを結合するためのキーとなる文字列であり、タプルの名前などの属性を用いる。例えば、結合キー文字列は、文字列型のデータとして構成できる。図８では、「名前」と「名前’」が結合キー文字列に相当する。本実施形態に係るｑバケット分割方式においては、「名前」と「名前’」などの結合キー文字列を基に、結合処理を実行する。
【００７４】
データ情報は、タプルに含まれる特定の情報である。例えば、図８では、「住所」と「年代」がデータ情報に相当する。
【００７５】
データ管理装置４０は、ネットワーク５を介して、空間最適化装置１０及び結合処理装置３０と通信可能に接続されており、データホストの役割を負う。
【００７６】
データ管理装置４０は、例えば、データ管理装置４０自身で管理するデータを構成する各キー情報タプルの分配先（結合処理装置３０）を決定し、それらの分配先（結合処理装置３０）に各キー情報タプルを分配する。例えば、結合処理装置３０が複数あれば、それぞれの結合処理装置３０が分配先として指定される。
【００７７】
結合処理対象となる複数のタプルは、単一のデータ管理装置４０に格納される単一のタプル集合（表）から抽出されてもよいし、複数のタプル集合（表）から抽出されてもよい。また、データ管理装置４０を複数とし、複数のデータ管理装置４０に格納される複数のタプル集合（表）から、類似結合の処理対象となる複数のタプルを抽出してもよい。
【００７８】
また、データ管理装置４０は、編集距離計算対象となるタプルペアのみについて、結合キー文字列の特徴的な情報や識別子などを含むキー情報タプルを生成し、生成したキー情報タプルを結合処理装置３０に送信するように構成してもよい。
【００７９】
キー情報タプル（結合キー情報）には、文字配置情報、端部文字列、タプル特定識別子などが特徴的な情報として含まれればよい。文字配置情報とは、結合キー文字列の一端部（末端部又は先端部）に含まれる文字から構成される文字シーケンスに関する情報である。端部文字列とは、文字シーケンスと隣接した文字から結合キー文字列の他端部（先端部又は末端部）の文字で構成される文字列である。タプル特定識別子とは、各キー情報タプルを特定し、それらのキー情報タプルを元のタプルに紐付けるための識別子である。キー情報タプル、文字配置情報、端部文字列、タプル特定識別子は、例えば特許文献１に記載された方法を基にして設定すればよい。
【００８０】
データ管理装置４０は、まず、結合キー文字列の端部文字からτ＋ｑ（ｑは１以上の整数）個の文字をチェックし、その中から順番を維持したままｑ個の文字を選択して文字シーケンスを生成する。
【００８１】
そして、データ管理装置４０は、当該文字シーケンスに基づいて、対応する結合キー文字列から結合キー情報を生成する。結合キー情報は、各タプルに関して、結合キー文字列の一端部の（τ＋ｑ）個の文字からｑ個の文字を並び順を替えずに選択できる数の分だけ生成することができる。
【００８２】
さらに、データ管理装置４０は生成した結合キー情報を対応するバケットに分配する。すなわち、バケットは、一つの文字シーケンスをラベルとして持ち、その文字シーケンスを含む結合キー情報の集合となる。なお、文字シーケンスに含まれる文字の並び順を維持しながら、文字間に文字シーケンスには含まれない文字を含むように配置された文字列を含む結合キー情報も、文字シーケンスを含む結合キー情報であり、その文字シーケンスを付されたバケットに振り分けられる。
【００８３】
例えば、編集距離閾値τが１、分割パラメタｑが３の場合について説明する。ある文字列の結合キー文字列を「ａｂｃｄ」とすると、「ａｂｃ」、「ａｂｄ」、「ａｃｄ」、「ｂｃｄ」が文字シーケンスとして生成される。また、別の文字列の結合キー文字列を「ａｂｃｅ」とすると、「ａｂｃ」、「ａｂｅ」、「ａｃｅ」、「ｂｃｅ」が文字シーケンスとして生成される。ここで、バケットのラベルとしては、「ａｂｃ」、「ａｂｄ」、「ａｃｄ」、「ｂｃｄ」、「ａｂｅ」、「ａｃｅ」、「ｂｃｅ」が設定される。２つの結合キー文字列「ａｂｃｄ」と「ａｂｃｅ」との間では、「ａｂｃ」というラベルを持つバケットのみが共有される。そのため、データ管理装置４０によって「ａｂｃ」というラベルを持つバケットに振り分けられたキー情報タプル同士に関して、結合処理装置３０が突き合わせを実行すればよい。文字列が３つ以上の場合でも、同様に、結合処理装置３０が同一のバケット内で突き合わせを実行すればよい。
【００８４】
なお、本実施形態の説明においては、データ管理装置４０によってキー情報タプルを生成する構成としたが、データ管理装置４０はデータを格納するのみであって、結合処理装置３０においてキー情報タプルを生成する構成としてもよい。最終的な結合対象となるタプルの結合は、例えば、図示しないシステム制御装置や管理装置によって、結合されたキー情報タプルのペア同士について、結合キー文字列を構成する全ての文字に関して編集距離閾値τを用いた突き合わせを実行すればよい。
【００８５】
以上が、本発明の第１の実施形態に係るデータ管理装置４０についての説明である。
【００８６】
以上、本発明の第１の実施形態に係る結合処理システム１の構成について説明してきたが、上述の構成は一例であって本発明の範囲を限定するものではない。本発明が解決しようとする課題を解決するため、本発明の第１の実施形態に係る結合処理システム１に種々の変更・追加を加えた構成についても、本発明の範囲に含むものとする。
【００８７】
（システム動作）
次に、本発明の第１の実施形態に係る結合処理システム１の動作について説明する。図４は、第１の実施形態に係る結合処理システム１の動作を示すフローチャートである。なお、図４のフローチャートは、本実施形態の結合処理システム１の特徴的な動作を抜き出して示したものである。
【００８８】
まず、図４において、結合処理システム１は、入力データ、編集距離閾値τ及び作業スペースのサイズＭの指定を受ける（ステップＳ１１）。このとき、データ管理装置４０は、結合対象データのうち、空間モデルＢ（ｑ）を構築するために必要となるデータの要約情報（第１の要約情報）を空間最適化装置１０に送信する。
【００８９】
空間最適化装置１０は、結合処理において使用する最大使用メモリ領域の大きさが、設定された作業スペースのサイズＭを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを推定する。そして、空間最適化装置１０は、範囲ｑ＿ｒａｎｇｅに含まれる任意の整数のうちいずれかを分割パラメタｑとして設定する（ステップＳ１２）。
【００９０】
最後に、結合処理装置３０は、編集距離閾値τ及び分割パラメタｑを用いて、ｑバケット分割方式に基づく文字列類似結合を行い、結果を出力する（ステップＳ１３）。
【００９１】
以上が、本発明の第１の実施形態に係る結合処理システム１の動作に関する概略的な説明である。なお、図４のフローチャートは結合処理システム１の概略的な動作を抜粋したものであり、種々の修正・追加を施すことによって実現される。
【００９２】
（空間最適化装置の動作）
次に、本発明の第１の実施形態に係る空間最適化装置１０の動作の詳細について説明する。図５は、第１の実施形態に係る空間最適化装置１０の動作を示すフローチャートである。
【００９３】
図５において、まず、空間最適化装置１０は、入力データ、編集距離閾値τ及び作業スペースの大きさＭの指定を受ける（ステップＳ１１１）。
【００９４】
データ観測部１２は、要約情報（第１の要約情報）として、入力データから分割パラメタｑに関する空間モデルＢ（ｑ）を構成する要素を取得する（ステップＳ１１２）。
【００９５】
次に、空間モデル構築部１４は、要約情報（第１の要約情報）を用いて、分割パラメタｑに関する空間モデルＢ（ｑ）を構築する（ステップＳ１１３）。
【００９６】
空間最適化部１１は、空間モデルＢ（ｑ）と作業スペースのサイズＭとを用いて、結合処理に用いる最大使用メモリ領域が、作業スペースの大きさＭを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを求める。そして、ｑ＿ｒａｎｇｅに含まれる任意の整数を分割パラメタｑとして設定する（ステップＳ１１４）。
【００９７】
最後に、空間最適化部１１は、設定した分割パラメタｑを結合処理装置３０に送る（ステップＳ１１５）。
【００９８】
以上が、本発明の第１の実施形態に係る空間最適化装置１０の動作についての説明である。なお、上述の結合処理システム１及び空間最適化装置１０の動作は一例であって、本発明の課題を解決するために、種々の変更・追加を施したものも本発明の範囲に含まれる。
【００９９】
また、本発明の第１の実施形態に係る結合処理システム１は、空間最適化装置１０と、結合処理装置３０と、データ管理装置４０と、を備える構成とした。第１の実施形態の特徴的な部分は、空間最適化装置１０の構成と動作によって発現する。そのため、空間最適化装置１０を単独で構成した装置・システムについても本発明の範囲に含むものとする。さらに、空間最適化装置１０の動作として示した方法を用いた結合処理方法及び結合処理プログラムについても本発明の範囲に含むものとする。
【０１００】
以上のように、本発明の第１の実施形態に係る空間最適化装置は、ｑバケット分割方式に基づいた結合処理で使用するメモリ領域が、割り当てられた作業スペースを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを適切に設定する。特に、本発明の第１の実施形態では、ｑ＿ｒａｎｇｅの下限値を適切に見積もることができる。そのため、ｑ＿ｒａｎｇｅの範囲内において分割パラメタｑを適切に設定することで、結合処理で使用するメモリ領域が計算機に設定された作業スペースを超えることを防ぎ、メモリ領域が不足することによって結合処理が途中で止まることを回避できる。
【０１０１】
（第２の実施形態）
次に、本発明の第２の実施形態に係る結合処理システム２について説明する。図６は、第２の実施形態に係る結合処理システム２の構成例を概念的に表すブロック図である。なお、第２の実施形態に係る結合処理システム２は、第１の実施形態に係る結合処理システム１に時空間最適化装置２０を追加した構成をとる。
【０１０２】
図６のように、第２の実施形態に係る結合処理システム２は、空間最適化装置１０（空間最適化手段）と、時空間最適化装置２０（時空間最適化手段）と、結合処理装置３０（結合処理手段）と、データ管理装置４０（データ管理手段）と、を備える。
【０１０３】
空間最適化装置１０と、結合処理装置３０と、データ管理装置４０とは、第１の実施形態の結合処理システム１と同じ構成であるために詳細な説明は省略する。ただし、第２の実施形態に係る空間最適化装置１０の空間最適化部１１は、時空間最適化装置２０の時空間最適化部２１と接続されている点が第１の実施形態とは異なる。
【０１０４】
空間最適化装置１０と、時空間最適化装置２０と、結合処理装置３０と、データ管理装置４０とは、それぞれ少なくともＣＰＵ６と、メモリ７と、入出力Ｉ／Ｆ８とを含む。空間最適化装置１０、時空間最適化装置２０、結合処理装置３０及びデータ管理装置４０は、例えば、コンピュータやサーバなどとして実現できる。
【０１０５】
空間最適化装置１０と、時空間最適化装置２０と、結合処理装置３０と、データ管理装置４０とは、互いにネットワーク５を介してデータ授受できるように接続されている。例えば、ネットワーク５としては、インターネットや電話回線などの公衆回線、ＷＡＮ、ＬＡＮ、無線通信ネットワークなどによって実現される。また、空間最適化装置１０、時空間最適化装置２０、結合処理装置３０及びデータ管理装置４０が１台のコンピュータやサーバ内に構成されてもよい。その場合、ネットワーク５の機能の一部は、コンピュータやサーバ内のケーブルや内部バス等に負わせればよい。なお、結合処理システム２の各構成要素間を接続する手段は、ここに挙げたものに限定されない。
【０１０６】
（時空間最適化装置）
次に、本発明の第２の実施形態に係る時空間最適化装置２０について説明する。図７は、第２の実施形態に係る時空間最適化装置２０の構成を示すブロック図である。
【０１０７】
図７のように、第２の実施形態に係る時空間最適化装置２０は、時空間最適化部２１と、データ観測部２２（第２のデータ観測部）と、モデル構成要素格納部２３（第２のモデル構成要素格納部）と、時間モデル構築部２４とを有する。なお、図７においては、各構成要素間の主な接続関係のみを線で示しており、全ての接続を図示しているわけではない。
【０１０８】
時空間最適化部２１と、データ観測部２２と、時間モデル構築部２４とは、例えば、ＣＰＵによりメモリに格納されるプログラムが実行されることで実現される。また、モデル構成要素格納部２３は、例えば、メモリ上に実現される。
【０１０９】
時空間最適化部２１は、空間最適化装置１０の空間最適化部１１及び結合処理装置３０と接続され、パラメタ推定命令及びｑ＿ｒａｎｇｅを取得する。また、時空間最適化部２１は、データ観測部２２及び時間モデル構築部２４に推定実行命令を送る。さらに、時空間最適化部２１は、後述する時間モデル構築部２４が生成する時間モデルＴ（ｑ）を受け取ると、ｑ＿ｒａｎｇｅに属する整数であり、かつ結合処理の処理時間が最小となる値ｑ＊を時間モデルＴ（ｑ）から推定する。そして、時空間最適化部２１は、推定した当該推定値を結合処理装置３０に送信する。
【０１１０】
図８及び図９は、本発明の第２の実施形態における分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）と、時間モデルＴ（ｑ）の関係を示している。
【０１１１】
まず、空間モデル構築部１４によって空間モデルＢ（ｑ）が設定されると、空間最適化部１１は、結合処理で使用するメモリ領域が、割り当てられた作業スペースのサイズＭを越えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）を推定する。
【０１１２】
次に、時間モデル構築部２４によって時間モデルＴ（ｑ）が設定されると、時空間最適化部２１は、作業スペースのサイズＭを越えないようなｑ＿ｒａｎｇｅ（斜線部）で、処理時間が最小となる分割パラメタｑ（ｑ＊）を推定する（図８及び図９）。実際には、処理時間が最小となる分割パラメタｑが整数とは限らない。そのため、図８及び図９のように抽出されるｑ＊には、ｑ＿ｒａｎｇｅに含まれる整数値が設定される。
【０１１３】
図８及び図９の上図には、空間モデルＢ（ｑ）に関する曲線と、作業スペースのサイズＭに関する直線（破線）との交点の横軸座標ｑｍが下限となり、分割パラメタｑの範囲ｑ＿ｒａｎｇｅ（斜線部）が設定される様子を示している。
【０１１４】
図８の下図では、ｑ＿ｒａｎｇｅの下限値となるｑｍが時間モデルＴ（ｑ）を最小とするｑ＊に相当し、分割パラメタｑとして設定されることを示している。
【０１１５】
また、図９の下図は、時間モデルＴ（ｑ）の頂点がｑ＿ｒａｎｇｅに含まれる例であり、頂点の横軸座標ｑ’が時間モデルＴ（ｑ）を最小とするｑ＊に相当し、分割パラメタｑに設定されることを示している。
【０１１６】
データ観測部２２は、時空間最適化部２１から推定実行命令を受け取ると、入出力Ｉ／Ｆ８の通信インタフェースを介して、データ管理装置４０が管理する結合対象データから、モデル化に必要なデータの要約情報（第２の要約情報）を観測し、モデル構成要素格納部２３に格納する。
【０１１７】
本実施形態における要約情報（第２の要約情報）は、例えば、処理対象文字列の総数、文字シーケンスの数、分割パラメタｑを用いた或るバケットにおける類似結合処理の計算量を返す任意の関数などを含む。なお、要約情報（第２の要約情報）は、時間モデルＴ（ｑ）を推定するのに必要な情報であれば詳細は問わない。
【０１１８】
モデル構成要素格納部２３は、データ観測部２２によって観測された要約情報（第２の要約情報）を格納・管理する。
【０１１９】
時間モデル構築部２４は、モデル構成要素格納部２３に必要な要約情報が格納されると、当該要約情報を用いて、分割パラメタｑに対する時間モデルＴ（ｑ）を構築する。なお、時間モデルとは、結合処理装置３０がｑバケット分割方式に基づく文字列類似結合を完了させるまでの全体処理時間をモデル化したものである。具体的な時間モデルＴ（ｑ）の設定方法については、後述の実施例において説明する。
【０１２０】
以上が、本発明の第２の実施形態に係る時空間最適化装置２０の構成についての説明である。
【０１２１】
（システム動作）
次に、本発明の第２の実施形態に係る結合処理システム２の動作について説明する。図１０は、第２の実施形態に係る結合処理システム２の動作を示すフローチャートである。なお、図１０のフローチャートは、本実施形態の結合処理システム２の特徴的な動作を抜き出して示したものである。
【０１２２】
まず、図１０において、結合処理システム２は、入力データ、編集距離閾値τ及び作業スペースのサイズＭの指定を受ける（ステップＳ２１）。このとき、データ管理装置４０は、結合対象データのうち、空間モデルＢ（ｑ）を構築するために必要となるデータの要約情報（第１の要約情報）を空間最適化装置１０に送信する。
【０１２３】
空間最適化装置１０は、要約情報（第１の要約情報）に基づいて空間モデルＢ（ｑ）を構築し、結合処理におけるメモリ上の最大使用領域がＭを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを推定する（ステップＳ２２）。
【０１２４】
次に、時空間最適化装置２０は、時間モデルＴ（ｑ）を構築するために必要となるデータの要約情報（第２の要約情報）に基づいて時間モデルＴ（ｑ）を構築し、ｑ＿ｒａｎｇｅに属する整数であり処理時間が最小となるような値ｑ＊を推定する（ステップＳ２３）。
【０１２５】
最後に、結合処理装置３０は、編集距離閾値τ及びｑ＊を用いて、ｑバケット分割方式に基づく文字列類似結合を行い、結果を出力する（ステップＳ２４）。
【０１２６】
以上が、本発明の第２の実施形態に係る結合処理システム２の動作に関する概略的な説明である。なお、図４のフローチャートは結合処理システム２の概略的な動作を抜粋したものであり、種々の修正・追加を施すことによって実現される。
【０１２７】
（空間最適化装置の動作）
次に、本発明の第２の実施形態に係る空間最適化装置１０の動作の詳細について説明する。図１１は、第２の実施形態に係る空間最適化装置１０の動作を示すフローチャートである。
【０１２８】
図１１において、まず、空間最適化装置１０は、入力データ、編集距離閾値τ及び作業スペースの大きさＭの指定を受ける（ステップＳ２１１）。
【０１２９】
データ観測部１２は、入力データから分割パラメタｑに関する空間モデルＢ（ｑ）を構成する要素を要約情報（第１の要約情報）として取得する（ステップＳ２１２）。
【０１３０】
次に、空間モデル構築部１４は、要約情報（第１の要約情報）を用いて、分割パラメタｑに関する空間モデルＢ（ｑ）を構築する（ステップＳ２１３）。
【０１３１】
空間最適化部１１は、空間モデルＢ（ｑ）及び作業スペースのサイズＭを用いて、結合処理に用いる最大使用メモリが、作業スペースの大きさＭを超えないような分割パラメタｑの範囲ｑ＿ｒａｎｇｅを求める（ステップＳ２１４）。
【０１３２】
最後に、空間最適化部１１は、時空間最適化装置２０にｑ＿ｒａｎｇｅを送る（ステップＳ２１５）。
【０１３３】
以上が、本発明の第２の実施形態に係る空間最適化装置１０の動作についての説明である。なお、上述の結合処理システム２及び空間最適化装置１０の動作は一例であって、本発明の課題を解決するために、種々の変更・追加を施したものも本発明の範囲に含まれる。
【０１３４】
（時空間最適化装置の動作）
次に、本発明の第２の実施形態に係る時空間最適化装置２０の動作について説明する。図１２は、第２の実施形態に係る時空間最適化装置２０の動作を示すフローチャートである。
【０１３５】
まず、図１２において、時空間最適化装置２０は、入力データ、編集距離閾値τ及びｑ＿ｒａｎｇｅの指定を受ける（ステップＳ２２１）。なお、ｑ＿ｒａｎｇｅは、空間最適化装置１０から取得する。
【０１３６】
データ観測部２２は、入力データから分割パラメタｑに関する時間モデルＴ（ｑ）を構成する要素を要約情報（第２の要約情報）として取得する（ステップＳ２２２）。
【０１３７】
次に、時間モデル構築部２４は、要約情報（第２の要約情報）を用いて、分割パラメタｑに関する時間モデルＴ（ｑ）を構築する（ステップＳ２２３）。
【０１３８】
時空間最適化部２１は、構築した時間モデルＴ（ｑ）及びｑ＿ｒａｎｇｅを用いて、範囲ｑ＿ｒａｎｇｅに属する整数で、最小の処理時間を達成する値ｑ＊を求める（ステップＳ２２４）。
【０１３９】
最後に、時空間最適化部２１は、結合処理装置３０にｑ＊を送る（ステップＳ２２５）。
【０１４０】
以上が、本発明の第２の実施形態に係る時空間最適化装置２０の動作についての説明である。なお、上述の結合処理システム、空間最適化装置及び時空間最適化装置の動作は一例であって、本発明の課題を解決するために、種々の変更・追加を施したものも本発明の範囲に含まれる。
【０１４１】
また、本発明の第２の実施形態に係る結合処理システム２においては、空間最適化装置１０と、時空間最適化装置２０と、結合処理装置３０と、データ管理装置４０と、を備える構成とした。第２の実施形態の特徴は、空間最適化装置１０及び時空間最適化装置２０の構成と動作によって発現する。そのため、空間最適化装置１０及び時空間最適化装置２０のみで構成した装置・システムについても本発明の範囲に含むものとする。さらに、空間最適化装置１０及び時空間最適化装置２０の動作として示した方法を用いた結合処理方法及び結合処理プログラムについても本発明の範囲に含むものとする。
【０１４２】
以上のように、本発明の第２の実施形態に係る時空間最適化装置は、空間最適化装置から取得したｑ＿ｒａｎｇｅにおいて、処理時間が最も小さくなるような分割パラメタｑを自動的に求めることができる。そのため、ｑバケット分割方式に基づく結合処理において、結合処理で使用するメモリ領域が計算機の作業スペースを超えないように分割パラメタの範囲を設定し、処理時間が最小となる分割パラメタｑの値ｑ＊を自動的に設定できる。
【０１４３】
ここで、具体的な実施例を用いて、本発明の実施形態に係る結合処理システム１及び２の動作について説明する。
【０１４４】
（実施例１）
本発明の実施形態に係る実施例１では、空間モデル構築部１４が、数理モデルに基づいて空間モデルＢ（ｑ）を構築する例を示す（図１３）。
【０１４５】
図１３の空間モデルＢ（ｑ）は、結合処理装置３０がｑバケット分割方式に基づく文字列類似結合を完了させるまでに使用するメモリ領域容量の最大値を空間モデルＢ（ｑ）としてモデル化したものである。図１３の空間モデルＢ（ｑ）は、式２のように記述される。
2015049561.tif 000003
【０１４６】
なお、式２において、Ｓｂは全バケットサイズの総和、Ｄｉは入力データサイズである。また、式２において、Ｐｍａｘｓｑは、入力データからｑバケット分割方式で生成される文字シーケンスの中で、最も生成頻度の大きな文字シーケンスの発生確率である。さらに、式２において、τ＋ｑＣｑは、τ＋ｑ個の文字の中からｑ個の文字を選ぶ組み合わせの数である。
【０１４７】
Ｐｍａｘｓｑは、文字の生成モデルＰｒ（ｒａｎｋ）から近似する。文字の生成モデルＰｒ（ｒａｎｋ）は、入力データに含まれる文字列の中でｒａｎｋ番目に発生頻度の高い文字の発生確率であり、ｒａｎｋがｋである文字の頻度は、ｚｉｐｆ分布を用いて以下の式３から求められる。
2015049561.tif 000004
【０１４８】
理論上、文字シーケンスに含まれるｑ個の文字が全てｒａｎｋ＝１の文字であった場合、その文字シーケンスは最頻出となる。そのため、ｚｉｐｆ分布を用いると、Ｐｍａｘｓｑは以下の式４のように近似される。なお、式４中のＣ１とＣ２は、回帰などを用いて求める定数である。
2015049561.tif 000005
【０１４９】
以上の式２と式４から、空間モデル構築部１４が構築する空間モデルＢ（ｑ）は、以下の式５のようになる。
2015049561.tif 000006
【０１５０】
式５における定数Ｃ１とＣ２は、具体的には以下のような手順によってデータ観測部１２が求める。
【０１５１】
まず、データ観測部１２は、ランダムに選択した複数の分割パラメタｑの値に対して、入力データからｑバケット分割方式でバケット生成を行い、各分割パラメタｑで最大となるバケットのサイズを取得する。
【０１５２】
そして、空間モデル構築部１４は、図１３が示すように、回帰などの方法を用いて、得られたバケットサイズの各点のなるべく近くを空間モデルＢ（ｑ）の曲線が通るように、Ｃ１とＣ２を調節する。例えば、最小二乗法を用いた回帰を行って調整する場合は、各分割パラメタｑについて、データ観測部１２から得られた実際のバケットサイズの値をＹｑとすると、以下の目的関数（式６）をＣ１とＣ２について最小化することで、Ｃ１とＣ２が求められる。
2015049561.tif 000007
【０１５３】
具体的に式６の目的関数を用いて最小二乗法を用いた回帰を行う場合、求める変数Ｃ１及びＣ２のいずれかで式６の目的関数を偏微分し、Ｃ１及びＣ２のそれぞれに関する偏微分式を立て、それらの偏微分式を０と置けばＣ１及びＣ２を求めることができる。
【０１５４】
空間最適化部１１は、空間モデルＢ（ｑ）の曲線を用いて、結合処理における最大バケットサイズが作業スペースのサイズＭ以下となる分割パラメタｑの範囲ｑ＿ｒａｎｇｅを求める。なお、空間モデルＢ（ｑ）の曲線において、Ｍ＝Ｂ（ｑ）を満たすｑがｑ＿ｒａｎｇｅの下限値となる。空間最適化部１１は、求めたｑ＿ｒａｎｇｅに属する整数を分割パラメタｑとして設定する。
【０１５５】
以上が本発明の実施例１についての説明である。なお、数理モデルに基づく空間最適化は、ここで示した手法に限定するわけではない。
【０１５６】
（実施例２）
本発明の実施形態に係る実施例２では、空間モデル構築部１４が、サンプリングに基づいて空間モデルＢ（ｑ）を構築する例を示す（図１４）。
【０１５７】
モデル構成要素格納部２３には、後述するｓｔａｒｔ＿ｑ、ｅｎｄ＿ｑ、所定の確率Ｐ、仮の空間モデルＢ’（ｑ）等が含まれる。なお、ｓｔａｒｔ＿ｑ、ｅｎｄ＿ｑ、確率Ｐは、ユーザによって設定されるパラメタであってもよいし、所定の方法によって機械的に定まる値であっても構わない。
【０１５８】
空間最適化部１１は、十分広い分割パラメタｑの範囲［ｓｔａｒｔ＿ｑ、ｅｎｄ＿ｑ］を設定する。例えば、空間最適化部１１は、ｓｔａｒｔ＿ｑを１、ｅｎｄ＿ｑをデータ観測部１２によって観測された入力データに含まれる文字列長の平均値又は最大値などに設定する。なお、分割パラメタｑの範囲［ｓｔａｒｔ＿ｑ、ｅｎｄ＿ｑ］は、ここで挙げた方法に限定するわけではない。
【０１５９】
次に、データ観測部１２は、入力データから少なくとも１つの文字列を所定の確率Ｐで選択し、選択した文字列を含む部分データを作成する。データ観測部１２が作成する部分データは、例えば、入力データに含まれる一部のタプルを組み合わせた構造を持ち、元となる入力データと比較すると小さいデータとなる。確率Ｐが１に近いほど、入力データに近い数のデータがサンプリングされ、空間最適化の精度は上がる一方、処理時間を要することになる。ある程度の精度を得るためには、データに依存はするものの、数百から数千個の文字列をサンプリングできるように確率Ｐを設定すればよい。例えば、１０００個程度の文字列をサンプリングしたいときは、サンプリング目安とする１０００を入力データの文字列数で割った値を確率Ｐとすればよい。本実施例においては、サンプリング目安を１０００に設定することによって、１０００個程度の文字列をサンプリングできる。
【０１６０】
そして、データ観測部１２は、作成した部分データに対して、設定された分割パラメタｑの範囲［ｓｔａｒｔ＿ｑ、ｅｎｄ＿ｑ］に属するいずれかの整数を分割パラメタｑとし、ｑバケット分割方式を実行するためのバケットを生成する。
【０１６１】
図１４で示されるように、空間モデル構築部１４は、各分割パラメタｑに対応する最大バケットサイズとなる仮の空間モデルＢ’（ｑ）を構築する。そして、空間モデル構築部１４は、以下の式７を用いて空間モデルＢ（ｑ）を構築する。
Ｂ（ｑ）＝１／Ｐ×Ｂ’（ｑ）・・・（７）
空間最適化部１１は、分割パラメタｑに対する空間モデルＢ（ｑ）のプロットを用いて、結合処理に使用される最大バケットサイズが作業スペースのサイズＭ以下となる分割パラメタｑの範囲ｑ＿ｒａｎｇｅを求める。
【０１６２】
以上が本発明の実施例２についての説明である。なお、サンプリングに基づく空間最適化は、ここで示した手法に限定するわけではない。また、例えば、実施例１及び２を組み合わせて空間モデルＢ（ｑ）を構築してもよい。
【０１６３】
（実施例３）
本発明の実施形態に係る実施例３として、Ｎコア計算機（Ｎは自然数）における並列結合処理の例を示す（図１７）。なお、Ｎコア計算機とは、Ｎ個の中央演算処理装置を持つコンピュータなどの情報処理装置である。
【０１６４】
図１５には、単一の中央演算処理装置を持つ１コア計算機５０によって、文字列類似結合処理を逐次処理するイメージを示した。図１６には、複数の１コア計算機６０−１〜Ｎによって、文字列類似結合処理を分散処理するイメージを示した。図１７には、Ｎ個の中央演算装置を持つＮコア計算機（マルチコア）によって、文字列類似結合処理を並列処理するイメージを示した。なお、図１５〜図１７に示した作業スペースのサイズＭは概念的なイメージであり、本発明の構成を具体的に示したものではない。
【０１６５】
これまで述べてきた空間最適化装置１０（図１５、図１６）では、最大バケットのサイズを推定することによって空間モデルＢ（ｑ）を構築した。
【０１６６】
例えば、図１５のように、単一コア計算機５０による処理では、各バケット５１（５１−１〜Ｎ）に収容された結合キー情報（文字列）について、バケットごとに突き合わせを実行する。その際、コア５６による演算処理では、結合処理で使用するメモリ５７上の領域（斜線の範囲）が、結合処理に割り当てられた作業領域Ｍを超えないように分割パラメタｑを設定する。
【０１６７】
同様に、図１６のように、複数の単一コア計算機６０（６０−１〜Ｎ）による分散処理では、各単一コア計算機６０（６０−１〜Ｎ）のバケット６１（６１−１〜Ｎ）に収容された結合キー情報（文字列）について、バケットごとに突き合わせを実行する。その際、コア６６（６６−１〜Ｎ）による演算処理では、各単一コア計算機６０（６０−１〜Ｎ）の結合処理で使用するメモリ６７（６７−１〜Ｎ）上の領域（斜線の範囲）が、類似結合処理に割り当てられた作業領域Ｍを超えないような分割パラメタｑを設定する。
【０１６８】
このような最大バケットのサイズを推定した空間モデルＢ（ｑ）の構築方法は、１台の計算機でバケットを一つ一つ順番に結合処理して行く逐次処理（図１５）や、複数の分散した計算機でバケットを並列処理して行く分散並列処理（図１６）に適している。
【０１６９】
実施例３では、図１７のように、Ｎコア計算機７０における並列処理が可能な環境に適した空間モデルＢ（ｑ）の構築法を想定する。Ｎコア計算機における並列処理結合の場合、最大で一度にＮ個のバケットを同時に処理できる。その一方で、割り当てられた作業スペースのサイズＭを、Ｎ個のバケット処理で分け合う必要がある。
【０１７０】
図１７のようなマルチコア計算機７０（７０−１〜Ｎ）による分散処理では、マルチコア計算機７０（７０−１〜Ｎ）のバケット７１（７１−１〜Ｎ）に収容された文字列について、バケットごとに突き合わせを実行する。その際、コア７６（７６−１〜Ｎ）による演算処理では、各マルチコア計算機７０（７０−１〜Ｎ）の結合処理で使用するメモリ領域の合計（斜線の範囲）が、結合処理に割り当てられた作業スペースのサイズＭを超えないようなｑを設定する。
【０１７１】
通常、Ｎコア計算機７０における並列処理結合においては、バケットの数がコアの数を上回ることが想定される。その場合、結合処理で使われるメモリ領域の合計が計算機の作業スペースのサイズＭを超えないためには、バケットサイズが大きい順にＮ個のバケットを選択し、選択されたＮ個のバケットのサイズを総和したサイズを空間モデルＢ（ｑ）として推定すればよい。なお、実施例３の空間モデル構築法は、実施例１及び２の構築法と組み合わせて使うことが可能である。
【０１７２】
実施例３によれば、Ｎコア計算機においても、作業スペースのサイズＭを超えないように、結合処理に使用するメモリ領域を設定することができる。
【０１７３】
以上が本発明の実施例３についての説明である。なお、複数コアを有する計算機における空間モデル構築法は、ここで示した手法に限定するわけではない。
【０１７４】
（実施例４）
本発明の実施例４では、時空間最適化装置２０における時間モデルＴ（ｑ）の具体的な構築例を示す。
【０１７５】
時空間最適化装置２０は、空間最適化装置１０（空間最適化部１１）から分割パラメタｑの範囲ｑ＿ｒａｎｇｅを受け取ると、時間モデルＴ（ｑ）を構築するための要約情報（第２の要約情報）を用いて時間モデルＴ（ｑ）を構築する。
【０１７６】
なお、要約情報（第２の要約情報）は、後述する定数ｃ1、ｃ2及びｃ3、処理対象文字列の総数Ｎ、編集距離閾値τ、Ｆｓｅｑ（ｑ）などを含み、モデル構成要素格納部２３に管理・格納されている。
【０１７７】
時間モデルＴ（ｑ）は、結合処理装置３０がｑバケット分割方式に基づく文字列類似結合を完了させるまでの全体処理時間をモデル化したものである。時間モデルＴ（ｑ）は、バケット分割に要する処理時間Ｔｐ（ｑ）と、全バケットの結合に要する処理時間Ｔｊ（ｑ）と、各バケットの結合結果をマージして一つの結果を出力するのに要する処理時間Ｔａ（ｑ）と、の和で構成される（式８）。
Ｔ（ｑ）＝Ｔｐ（ｑ）＋Ｔｊ（ｑ）＋Ｔａ（ｑ）・・・（８）
例えば、各処理時間は、それぞれ計算量の比で表現できる。
【０１７８】
入力データが含む文字列の数をＮとすると、バケット分割に要する処理時間Ｔｐ（ｑ）は、式８によって推定することができる。なお、式９において、ｃ1は回帰などで推定する定数であり、τ+qＣq×Ｎはバケット分割処理の計算量に相当する。
2015049561.tif 000008
【０１７９】
全バケットの結合に要する処理時間Ｔｊ（ｑ）は、入力データから生成されうるあらゆる文字シーケンスの集合Ｓに対して、以下の式１０によって推定することができる。なお、式１０において、Ｆｓｅｑ（ｑ）は文字シーケンスｓｅｑに１対１対応するバケットの結合処理に必要な計算量であり、ｃ2は回帰などから得られる定数である。
2015049561.tif 000009
【０１８０】
Ｆｓｅｑ（ｑ）は、分割パラメタｑを用いた或るバケットにおける類似結合処理の計算量を返す任意の関数を示す。Ｆｓｅｑ（ｑ）は、実施例１及び２で示した空間モデルＢ（ｑ）の構築と同様に、数理モデルを用いて構築を試みてもよいし、入力データから抽出した部分データを用いて処理時間を実測して推定（サンプリング）してもよい。
【０１８１】
各バケットの結合結果をマージして一つの結果を出力するのに要する処理時間Ｔａ（ｑ）については、Ｔｐ（ｑ）と同様の式１０によって推定することができる。なお、式１１において、Ｎは処理対象文字列の総数であり、ｃ3は回帰などから求められる定数である。
2015049561.tif 000010
【０１８２】
なお、各バケットの結合結果をマージするということは、各バケット内で結合された結合キー情報のペアを基に入力データに含まれるタプルのペアを結合してマージすることを意味する。
【０１８３】
以上の式９〜１１によって求めた処理時間を式８に当てはめれば、時間モデルＴ（ｑ）が構築される。
【０１８４】
時空間最適化部２１は、時間モデル構築部２４が構築した時間モデルＴ（ｑ）を用いて、範囲ｑ＿ｒａｎｇｅに含まれる整数の中で、時間モデルＴ（ｑ）を最小にする値ｑ＊を求め、分割パラメタｑを設定する。
【０１８５】
以上が本発明の実施例４についての説明である。なお、各処理時間ついては、式９〜１１以外の方法で求めてもよい。
【０１８６】
以上、実施形態を参照して本発明を説明してきたが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１８７】
本発明によって提供される結合処理システム及び結合処理方法は、同じ意味を表わしていながらも表記が微妙に異なるような文字列を検出する「名寄せ技術」への応用可能である。
【０１８８】
また、本発明の結合処理システム及び結合処理方法は、複数の店舗をまたがる在庫検索システムなどにも応用可能である。例えば、店舗によって商品名が若干異なるような場合であっても、探したい商品を検出することができる。また、同じモデルであっても、色やサイズなどの違いで微妙に異なる品番が付くことがある。このような場合、本発明の結合処理システム及び結合処理方法によれば、色やサイズによって若干違う同じモデルの商品を検出することによって、顧客に推薦することができる。
【０１８９】
また、本発明の結合処理システム及び結合処理方法は、文字列のみならず、例えば移動物体の軌跡や、イベントの時系列データなどといったオブジェクトのシークエンスに対する類似結合処理にも適用可能である。
【符号の説明】
【０１９０】
１    結合処理システム
５    ネットワーク
６    ＣＰＵ
７    メモリ
８    入出力Ｉ／Ｆ
１０    空間最適化装置
１１    空間最適化部
１２    データ観測部
１３    モデル構成要素格納部
１４    空間モデル構築部
２０    時空間最適化装置
２１    時空間最適化部
２２    データ観測部
２３    モデル構成要素格納部
２４    時間モデル構築部
３０    結合処理装置
４０    データ管理装置
【図１】
2015049561.tif 000011
【図２】
2015049561.tif 000012
【図３】
2015049561.tif 000013
【図４】
2015049561.tif 000014
【図５】
2015049561.tif 000015
【図６】
2015049561.tif 000016
【図７】
2015049561.tif 000017
【図８】
2015049561.tif 000018
【図９】
2015049561.tif 000019
【図１０】
2015049561.tif 000020
【図１１】
2015049561.tif 000021
【図１２】
2015049561.tif 000022
【図１３】
2015049561.tif 000023
【図１４】
2015049561.tif 000024
【図１５】
2015049561.tif 000025
【図１６】
2015049561.tif 000026
【図１７】
2015049561.tif 000027
【図１８】
2015049561.tif 000028
【図１９】
2015049561.tif 000029
【図２０】
2015049561.tif 000030