(57)【要約】  複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する結合処理装置が、編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段と、を備える。
2013031117.tif 000002
【特許請求の範囲】
【請求項１】
複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する結合処理装置において、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段と、
を備えることを特徴とする結合処理装置。
【請求項２】
複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるデータ管理装置において、
複数のタプルを格納するデータ格納手段と、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記複数の結合処理装置の中から、前記データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせの中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定するデータ分配手段と、
を備えることを特徴とするデータ管理装置。
【請求項３】
少なくとも１つのデータ管理装置、及び、この少なくとも１つのデータ管理装置で保持される複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置を含む文字列類似結合システムにおいて、
前記少なくとも１つのデータ管理装置は、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目までの端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの末尾文字に相当する該結合キー文字列中の文字の次の文字から該結合キー文字列の末尾文字までの末尾部分文字列と、該組み合わせの先頭文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせ、又は、前記各タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの先頭文字に相当する該結合キー文字列中の文字の前の文字から該結合キー文字列の先頭文字までの先頭部分文字列と、該組み合わせの末尾文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせを含むキー情報タプルをそれぞれ生成するキー情報生成手段と、
前記キー情報生成手段により生成された各キー情報タプルに対応する前記ｑ個の文字の各組み合わせに基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各結合処理装置に各タプルのデータとしてそれぞれ分配するデータ分配手段と、
を備え、
前記複数の結合処理装置はそれぞれ、
前記少なくとも１つのデータ管理装置から分配された複数のキー情報タプルを受信する受信手段と、
前記受信手段により受信された複数のキー情報タプルのうち、各キー情報タプルに対応する前記ｑ個の文字の組み合わせが共通するキー情報タプル集合毎に、前記類似結合処理を実行する結合処理手段と、
を備えることを特徴とする文字列類似結合システム。
【請求項４】
前記複数の結合処理装置はそれぞれ、
前記受信手段により受信された複数のキー情報タプルの各ペアに関し、前記各文字配置情報に含まれる同種の要素のうちの大きいほうの値を合計することにより第１部分推定値を算出し、前記末尾部分文字列間又は前記先頭部分文字列間の編集距離を第２部分推定値として算出し、該第１部分推定値と該第２部分推定値とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段、
を更に備え、
前記各結合処理装置の前記結合処理手段は、前記推定値算出手段により算出された各編集距離推定値と前記編集距離閾値τとの比較結果に基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、
ことを特徴とする請求項３に記載の文字列類似結合システム。
【請求項５】
前記各結合処理装置の前記結合処理手段は、前記推定値算出手段により算出された各第１部分推定値と前記編集距離閾値τとの比較結果、及び、前記推定値算出手段により算出された各第２部分推定値と前記編集距離閾値τとの比較結果の少なくとも一方を更に用いることにより、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする請求項４に記載の文字列類似結合システム。
【請求項６】
前記少なくとも１つのデータ管理装置及び前記複数の結合処理装置と通信可能なシステム制御装置を更に含み、
前記各結合処理装置の前記結合処理手段は、前記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、生成された各結果タプルをそれぞれ前記システム制御装置に送信し、
前記システム制御装置は、
前記複数の結合処理装置から送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が前記編集距離閾値τの条件を満たすタプルのペアを決定する結果生成手段、
を備えることを特徴とする請求項４又は５に記載の文字列類似結合システム。
【請求項７】
前記取得手段は、前記編集距離閾値τ及び前記分割パラメータｑを少なくとも含む通信メッセージを受信することを特徴とする請求項３から６のいずれか１項に記載の文字列類似結合システム。
【請求項８】
前記複数のタプルの結合キー文字列に関し、結合キー文字列の総数、各文字の出現頻度分布、各文字列長の出現頻度分布、最大文字列長及び係数を含む要約情報を生成するデータ分析手段と、
前記分割パラメータｑの値に対応して、前記少なくとも１つのデータ管理装置、前記複数の結合処理装置及び前記システム制御装置の少なくとも１つの処理に掛かる時間を示す処理時間モデルを、前記データ分析手段により生成された前記要約情報に基づいて生成するモデル構築手段と、
前記モデル構築手段により構築された前記処理時間モデルが示す時間を最小とする前記分割パラメータｑの値を決定する最適化手段と、
を備えるパラメータ推定装置を更に含む請求項３から７のいずれか１項に記載の文字列類似結合システム。
【請求項９】
複数のタプルを対象に編集距離閾値τ（正の整数）を用いて実行される文字列類似結合方法において、少なくとも１つのコンピュータが、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得し、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する、
ことを含む文字列類似結合方法。
【請求項１０】
複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理をコンピュータに実行させるプログラムにおいて、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段、
を前記コンピュータに実現させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列類似結合技術に関する。
【背景技術】
【０００２】
結合演算（Join）は、与えられた結合条件に応じて、２つの表の各々の行（タプル）における任意のペアを突き合わせ（Matching）、当該結合条件を満たすペアを繋げることで生成された行を全て出力する処理である。特に、等価条件に応じた結合演算は、等価結合（Equi-Join）と呼ばれ、ＭｙＳＱＬ等のようなＤＢＭＳ（データベースマネジメントシステム）に搭載されるなど、利用範囲の広い技術として知られている。【０００３】
下記非特許文献５では、等価結合のよく知られた実行法として、ネステッドループアプローチ（nested loop join）やハッシュアプローチ（hash join）等が紹介されている。図３５は、ネステッドループアプローチの例を示した図である。図３５に示されるように、或る結合条件に応じて左表と右表とを結合する場合、ネステッドループアプローチでは、左表の任意の行が右表のあらゆる行と突き合わされる。【０００４】
一方で、図３６は、ハッシュアプローチの例を示した図である。図３６において、上部左表及び上部右表の「名前」属性の値が一致するものを結合（等価結合）すると仮定する。ハッシュアプローチでは、前処理として、ハッシュ関数に各タプルの「名前」属性の値を入力することにより得られたハッシュ値に対応するバケットに、各タプルがそれぞれ振り分けられる。その後、各バケット内で、ネステッドループアプローチのように、任意のタプルペアの突き合わせが行われる。【０００５】
このような前処理には２つの利点がある。第１の利点は、トータルの突き合わせ回数を減らせることにある。第２の利点は、バケットごとに独立した結合処理を施すことができるため、容易に並列化できることにある。このような２つの利点から、ハッシュアプローチは高速かつ並列化容易な等価結合の処理法として知られている。【０００６】
文字列類似結合（String Similarity Join）は、類似する文字列を含むタプル同士を結合する処理である。図３７は、図３５の左表と右表に対して編集距離を用いた文字列類似結合を施した結果を示す図である。具体的には、図３７では、「名前」属性の値（文字列）と「名前'」属性の値（文字列）との編集距離が２以下となる各タプルを結合する類似結合が行われている。【０００７】
編集距離とは、文字列間の距離を測る尺度の一つである。図３６と図３７とを比較すれば分かるように、等価結合では、「名前」属性値と「名前'」属性値とを用いて突き合わせを行った結果、結合される行が存在しないのに対し、類似結合では似たような文字列を持つタプル同士を結合することができる。具体的には、編集距離とは、一つの文字列を別の文字列に変換させるのに必要な手順（文字の挿入、削除又は置換）の最小回数を示す。例えば、２つの文字列「ｋｉｔｔｅｎ」と「ｓｉｔｔｉｎｇ」との間の編集距離を算出するためには、「ｋｉｔｔｅｎ」（又は「ｓｉｔｔｉｎｇ」）に対して、文字の挿入、削除又は置換の手順を何回実行すれば、「ｓｉｔｔｉｎｇ」（又は「ｋｉｔｔｅｎ」）に変換できるのかを考えればよい。この場合、「ｋ」を「ｓ」に置換し、かつ、「ｅ」を「ｉ」に置換し、かつ、「ｇ」を挿入すれば、文字列「ｋｉｔｔｅｎ」は文字列「ｓｉｔｔｉｎｇ」に変換される。よって、文字列「ｋｉｔｔｅｎ」と文字列「ｓｉｔｔｉｎｇ」との間の編集距離は、３（２回の置換及び１回の挿入）となる。【０００８】
編集距離は、一般的には、各々の文字列の接頭辞同士の編集距離を用いて計算することができる。文字列ｓ１及びｓ２の各文字列長を｜ｓ１｜及び｜ｓ２｜で示し、（｜ｓ１｜＋１）×（｜ｓ２｜＋１）行列ｍｔｘのｉ行ｊ列目の要素ｍｔｘ［ｉ］［ｊ］を、ｓ１［ｉ］を末尾文字とするｓ１の接頭辞とｓ２［ｊ］を末尾文字とするｓ２の接頭辞との編集距離で示す場合、各要素は次の式を用いて算出され得る。
ｍｔｘ［ｉ］［ｊ］＝ｍｉｎ（ｍｔｘ［ｉ−１］［ｊ］＋１、ｍｔｘ［ｉ］［ｊ−１］＋１、ｍｔｘ［ｉ−１］［ｊ−１］＋θ）
上記式は以下の条件に基づく。
１≦ｉ≦｜ｓ１｜かつ１≦ｊ≦｜ｓ２｜であり、ｓ１［０］及びｓ２［０］は空文字に相当し、ｍｔｘ［０］［０］＝０かつｍｔｘ［０］［ｊ］＝ｊかつｍｔｘ［ｉ］［０］＝ｉである。さらに、θはｓ１［ｉ］＝ｓ２［ｊ］のとき０であり、それ以外のとき１である。【０００９】
文字列ｓ１及びｓ２の編集距離は、上記行列ｍｔｘを全て計算した後、要素ｍｔｘ［｜ｓ１｜］［｜ｓ２｜］の値から取得される。以降、便宜上、このような行列ｍｔｘを編集距離行列と呼ぶ。このような編集距離行列を用いた文字列間の編集距離の算出手法について図３８を用いて説明する。図３８は、文字列「Ｃａｅｓａｒ」と文字列「Ｃｅａｓａｒ」との間の編集距離の計算例を示す図である。図３５の左表には編集距離行列が示され、その編集距離行列の６行６列目の要素である整数値２が２つの文字列間の編集距離の値を示す。【００１０】
このような編集距離の計算は、最短経路探索における経路長の計算と見なすことができる。図３８の右表には、文字列「Ｃａｅｓａｒ」と文字列「Ｃｅａｓａｒ」との間の編集距離の計算を最短経路長の計算と見なした場合に取りうる全経路が示される。編集距離は、この碁盤の目状の経路を右、下、又は、右下方向へ進みながら、左上の地点（０、０）から右下の地点（｜ｓ１｜、｜ｓ２｜）へ辿りつく最短経路の長さを計算することにより取得される。図３８に示されるように、この最短経路探索において、１つ右へ移動するのにかかるコスト及び１つ下へ移動するのにかかるコストはそれぞれ１であり、１つ右下へ移動するのにかかるコストは０又は１である。１つ右へ移動するのにかかるコストとは、地点（ｉ、ｊ−１）から地点（ｉ、ｊ）へ移動する経路長（パス長）を示す。また、１つ下へ移動するのにかかるコストとは、地点（ｉ−１、ｊ）から地点（ｉ、ｊ）へ移動する経路長（パス長）を示す。１つ右下へ移動するのにかかるコストについては、具体的には、ｓ１［ｉ］とｓ２［ｊ］とが同じであれば０であり、そうでなければ１である。図３８の太線で示される経路が、地点（０、０）から地点（｜ｓ１｜、｜ｓ２｜）へ至る最短経路である。各経路上に０と表記されている経路は、コスト（経路長）が０である。【００１１】
図３８に示されるように、取りうる経路が数多く存在するため、数多くの経路の中から最短経路を探し出す、すなわち、編集距離を算出するには、大きな処理コストがかかる。このような編集距離を用いて文字列類似結合を行う手法が、下記非特許文献１から４で提案されている。いずれの提案においても編集距離の計算にかかる処理コストを少なくする工夫が行われている。【００１２】
下記非特許文献１から３で提案される各手法は、文字列から生成されたシグネチャに基づき、類似する可能性のあるタプルのペアを候補として残す（フィルタリングする）。結果、入力タプルの全てのペアの中からフィルタリングされたペアに関してのみ編集距離を算出する（リファインする）ことにより、文字列類似結合処理の高速化が図られている。編集距離の計算は、ネステッドループアプローチに見られるように、あらゆる候補ペアに対して総当たり的に行われる。【００１３】
編集距離の計算が行われる回数（すなわち、突き合わせの回数）を削減しようとするこれらの手法に対して、下記非特許文献４で提案される手法は、編集距離の計算そのものの処理コストを下げることで、処理の高速化を狙う。まず、入力データＳ及びＲで類似結合の対象となる全ての文字列属性値を１つのトライ木（Ｔｒｉｅ）に格納する。トライ木とは、複数の文字列を圧縮して表現することができ、文字列に対するインデックスとしてしばしば使用されるデータ構造である。先頭文字から始まる先頭部分文字列（接頭辞）が一致する文字列同士は、まとめて１つの枝で表現することができるため、このトライ木を探索しながら接頭辞同士の編集距離を計算していくことで、異なる文字列ペアで行われる共通の接頭辞同士の編集距離計算を一回にまとめることができる。【００１４】
なお、文字列間の距離の尺度には、編集距離の他、ジャッカード尺度、コサイン尺度など、性質の異なる複数の種類が存在する。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】A. Arasu， V. Ganti， R. Kaushik, "Efficient Exact Set-Similarity Joins", In VLDB, pages 918-929, 2006．
【非特許文献２】R. J. Bayardo, Y. Ma, R. Srikant, "Scaling up all pairs similarity search", In WWW, pages 131-140, 2007.
【非特許文献３】C. Xiao, W. W. 0011, X. Lin, "Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints", PVLDB, 1(1):933-944, 2008.
【非特許文献４】J. Wang, J. Feng, G. Li, "Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraint", VLDB, 2010.
【非特許文献５】Leonard D. Shapiro, "Join processing in database systems with large main memories", TODS, 1986.
【発明の概要】
【００１６】
しかしながら、上述の非特許文献１から４で提案される各手法は並列化し難いという問題がある。
【００１７】
一方、上述の非特許文献５で提案されるハッシュアプローチを文字列類似結合に適用することにより、突き合わせ回数を減らしつつ並列化を容易にすることが考えられるかもしれない。しかしながら、文字列類似結合のように類似性を考慮した結合処理には、非特許文献５で提案されるハッシュアプローチをそのまま適用することはできない。ハッシュ関数に結合キーを入力することにより得られたハッシュ値に基づき各タプルをバケットに振り分けた場合、類似しているが完全に一致していない結合キー同士の突き合わせ処理が行われないことから、正しい結合結果を得ることができないからである。
【００１８】
また、編集距離の計算コストが大きいために、距離計算を行うための突き合わせが多数発生する文字列類似結合は、全体としてその処理コストが非常に大きくなる傾向にある。そのため、編集距離の計算コストそのものを下げることが望まれる。
【００１９】
本発明は、上述の事情に鑑みてなされたものであり、編集距離を用いた文字列類似結合を低い計算コストで高速に実行する技術を提供する。
【００２０】
本発明の各態様では、上述した課題を解決するために、それぞれ以下の構成を採用する。
【００２１】
第１の態様は、複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する結合処理装置に関する。第１態様に係る結合処理装置は、上記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段とを備える。
【００２２】
第２の態様は、複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるデータ管理装置に関する。第２の態様に係るデータ管理装置は、複数のタプルを格納するデータ格納手段と、上記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、複数の結合処理装置の中から、データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせの中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定するデータ分配手段と、を備える。
【００２３】
第３の態様は、少なくとも１つのデータ管理装置、及び、この少なくとも１つのデータ管理装置で保持される複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置を含む文字列類似結合システムに関する。第３の態様に係る文字列類似結合システムでは、上記少なくとも１つのデータ管理装置が、編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、各タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目までの端部分に含まれるｑ個の文字の各組み合わせに対して、当該組み合わせの末尾文字に相当する当該結合キー文字列中の文字の次の文字から当該結合キー文字列の末尾文字までの末尾部分文字列と、当該組み合わせの先頭文字の当該結合キー文字列中の位置及び当該組み合わせに含まれる文字間に存在する当該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせ、又は、各タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれるｑ個の文字の各組み合わせに対して、当該組み合わせの先頭文字に相当する当該結合キー文字列中の文字の前の文字から当該結合キー文字列の先頭文字までの先頭部分文字列と、当該組み合わせの末尾文字の当該結合キー文字列中の位置及び当該組み合わせに含まれる文字間に存在する当該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせを含むキー情報タプルをそれぞれ生成するキー情報生成手段と、キー情報生成手段により生成された各キー情報タプルに対応するｑ個の文字の各組み合わせに基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各結合処理装置に各タプルのデータとしてそれぞれ分配するデータ分配手段と、を備え、上記複数の結合処理装置はそれぞれ、少なくとも１つのデータ管理装置から分配された複数のキー情報タプルを受信する受信手段と、受信手段により受信された複数のキー情報タプルのうち、各キー情報タプルに対応するｑ個の文字の組み合わせが共通するキー情報タプル集合毎に、類似結合処理を実行する結合処理手段と、を備える。
【００２４】
なお、本発明の別態様としては、上記第１から第３の各態様に含まれる各処理を少なくとも１つのコンピュータが実行する文字列類似結合方法であってもよいし、上記第１から第３の各態様に含まれる各構成を少なくとも１つのコンピュータに実現させるプログラムであってもよいし、このようなプログラムを記録したコンピュータが読み取り可能な記憶媒体であってもよい。
【００２５】
上記各態様によれば、編集距離を用いた文字列類似結合を低い計算コストで高速に実行する技術を提供することができる。
【図面の簡単な説明】
【００２６】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００２７】
【図１】図１は、第３実施形態における文字列類似結合システムの構成例を概念的に示す図である。
【図２】図２は、システム制御装置の構成例を概念的に示すブロック図である。
【図３】図３は、データ管理装置の構成例を概念的に示すブロック図である。
【図４Ａ】図４Ａは、結合キー文字列「Ｃａｅｓａｒ」から生成されるＳＩＰタプルの例を示す図である。
【図４Ｂ】図４Ｂは、結合キー文字列「Ｄａｋ」から生成されるＳＩＰタプルの例を示す図である。
【図５】図５は、ＳＩＰタプルの振り分け手法の例を概念的に示す図である。
【図６】図６は、結合処理装置の構成例を概念的に示すブロック図である。
【図７】図７は、文字列「Ｃａｅｓａｒ」及び「Ｃｅａｓａｒ」に関し生成された各ＳＩＰタプルの局所編集距離の計算を概念的に示す図である。
【図８】図８は、第３実施形態における文字列類似結合システムの全体的な動作の概要を示すフローチャートである。
【図９】図９は、再帰法の動作を示すフローチャートである。
【図１０】図１０は、関数ｐａｒｔｉｔｉｏｎ＿ｒｃの処理を示すフローチャートである。
【図１１】図１１は、再帰法を用いたＳＩＰタプル生成の例を示す図である。
【図１２】図１２は、当てはめ法の動作を示すフローチャートである。
【図１３】図１３は、関数ｍａｋｅ＿ｔｅｍｐｌａｔｅの処理を示すフローチャートである。
【図１４】図１４は、関数ｐａｒｔｉｔｉｏｎ＿ｔｅｍｐの処理を示すフローチャートである。
【図１５】図１５は、当てはめ法を用いたＳＩＰタプル生成の例を示す図である。
【図１６】図１６は、ネステッドループ結合法の動作を示すフローチャートである。
【図１７】図１７は、関数ｎｅｓｔｅｄ＿ｌｏｏｐ＿ｊｏｉｎの処理を示すフローチャートである。
【図１８】図１８は、関数ｉｎｓｅｒｔＭｉｎの処理を示すフローチャートである。
【図１９】図１９は、トライ結合法の動作を示すフローチャートである。
【図２０】図２０は、関数ｆｏｒｅｓｔ＿ｂｕｉｌｄの処理を示すフローチャートである。
【図２１】図２１は、関数ｉｎｓｅｒｔの処理を示すフローチャートである。
【図２２】図２２は、トライ結合法により構築される木構造の例を示す図である。
【図２３】図２３は、関数ｆｏｒｅｓｔ＿ｊｏｉｎの処理を示すフローチャートである。
【図２４】図２４は、関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓの処理を示すフローチャートである。
【図２５】図２５は、関数ａｃｔｉｖｅｌｉｓｔの処理を示すフローチャートである。
【図２６】図２６は、アクティブリストの生成例を示す図である。
【図２７】図２７は、結果生成部の処理の具体例を示すフローチャートである。
【図２８】図２８は、第４実施形態におけるシステムの構成例を概念的に示す図である。
【図２９】図２９は、パラメータ推定装置の構成例を概念的に示すブロック図である。
【図３０】図３０は、第４実施形態におけるシステムの全体的な動作の概要を示すフローチャートである。
【図３１】図３１は、モデル構築部の動作例を示すフローチャートである。
【図３２】図３２は、最適化部の動作例を示すフローチャートである。
【図３３】図３３は、訓練データ及び関数ｚ（ｒ）の例を示す図である。
【図３４Ａ】図３４Ａは、分割パラメータｑ（１≦ｑ≦１４）に関し（式５）から得られる理論的処理時間の例を示す図である。
【図３４Ｂ】図３４Ｂは、分割パラメータｑ（１≦ｑ≦１４）に関し本実施例におけるシステムに実際に結合処理させた場合の実測処理時間を示す図である。
【図３５】図３５は、ネステッドループアプローチの例を示した図である。
【図３６】図３６は、ハッシュアプローチの例を示した図である。
【図３７】図３７は、図３５の左表と右表に対して編集距離を用いた文字列類似結合を施した結果を示す図である。
【図３８】図３８は、文字列「Ｃａｅｓａｒ」と文字列「Ｃｅａｓａｒ」との間の編集距離の計算例を示す図である。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について説明する。なお、以下に挙げる各実施形態はそれぞれ例示であり、本発明は以下の各実施形態の構成に限定されない。
【００２９】
［第１実施形態］
第１実施形態における結合処理装置は、複数のタプルを対象に編集距離閾値τ（正の整数、以降、単に閾値τとも表記する）を用いて類似結合処理を実行する。この結合処理装置は、当該閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得部と、当該各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）（ｑは２以上の整数）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理部を備える。以降、当該端部分に含まれる並び順が維持されたｑ個の文字の各組み合わせをｑコンビネーションと表記する場合もある。
【００３０】
従って、第１実施形態によれば、従来、類似結合処理の対象となるデータの全てのタプルペアを対象に編集距離の計算が行われていたところ、当該端部分から生成されるｑコンビネーションの中に共通するｑコンビネーションが１つも存在しないタプルのペアを除外するため、従来に比べ、処理コストを削減し、システム全体での類似結合処理の時間を削減することができる。また、第１実施形態によれば、検出されるべきタプルのペアの取りこぼしは生じないため、適切な類似結合処理結果を出力することができる。
【００３１】
以下、第１実施形態においてこのような作用効果を奏する理由について説明する。
【００３２】
上述したように、類似結合処理では、処理対象となるデータにおける全てのタプルペアに関して、結合キーの編集距離の算出処理、編集距離と編集距離閾値τとの比較処理等が必要になる。例えば、入力データＳと入力データＲとの間の文字列類似結合は、全タプルペアの数が入力データＳのタプル数と入力データＲのタプル数との乗算値となるため、膨大な処理時間を要する。
【００３３】
そこで、第１実施形態は、編集距離を実際に計算する前に、編集距離が閾値τより大きくなるタプルペアを特定し、この特定されたタプルペアを類似結合処理の対象から除外する。これにより、編集距離計算等の対象とするタプルペアの数を削減することができるため、全体的な類似結合処理時間を軽減することができる。
【００３４】
ここで、文字列ｓ及びｒのｋ文字目から（ｋ＋τ）文字目までの、長さ（τ＋１）の部分文字列を（以降、（τ＋１）部分文字列と表記する）ｓｕｂｓ＿ｋ及びｓｕｂｒ＿ｋで示す。例えば、τが２であり、文字列ｓが「ａｂｃｄｅｆ」であり、文字列ｒが「ｄｃｂａｅｆ」である場合、文字列ｓ及びｒに関しそれぞれ次のような（τ＋１）部分文字列が存在する。
ｓｕｂｓ＿１＝「ａｂｃ」、ｓｕｂｓ＿２＝「ｂｃｄ」、ｓｕｂｓ＿３＝「ｃｄｅ」、ｓｕｂｓ＿４＝「ｄｅｆ」
ｓｕｂｒ＿１＝「ｄｃｂ」、ｓｕｂｒ＿２＝「ｃｂａ」、ｓｕｂｒ＿３＝「ｂａｅ」、ｓｕｂｒ＿４＝「ａｅｆ」
【００３５】
このとき、或るｋに対して、文字列ｓのｓｕｂｓ＿ｋと文字列ｒのｓｕｂｒ＿ｋとの間に共通する文字が一つも存在しない場合、ｓｕｂｓ＿ｋとｓｕｂｒ＿ｋとの間の編集距離は明らかに（τ＋１）である。これにより、編集距離の性質上、全体文字列間の編集距離がその部分文字列間の編集距離を下回ることがないため、文字列ｓと文字列ｒとの間の編集距離は明らかに（τ＋１）以上となる。言い換えれば、文字列ｓと文字列ｒとの間の編集距離がτ以下であるためには、任意のｋに対してｓｕｂｓ＿ｋ及びｓｕｂｒ＿ｋは１つ以上の文字を共有している必要がある。以降、この条件を第１条件と表記する。
【００３６】
加えて、文字列ｓと文字列ｒとの間の編集距離がτ以下であるためには、ｓｕｂｓ＿ｋのｉ番目の文字とｓｕｂｒ＿ｋのｊ番目の文字とが一致した場合、ｓｕｂｓ＿（ｋ＋１）のｉ番目以降の１つ以上の文字とｓｕｂｒ＿（ｋ＋１）のｊ番目以降の文字とが一致している必要がある。以降、この条件を第２条件と表記する。
【００３７】
ｓｕｂｓ＿１（「ａｂｃ」）は２文字目の「ｂ」がｓｕｂｒ＿１（「ｄｃｂ」）の３文字目の「ｂ」と一致するため、上記第１条件を満たすが、ｓｕｂｓ＿２（「ｂｃｄ」）の２番目以降の文字（「ｃ」及び「ｄ」）は、ｓｕｂｒ＿２（「ｃｂａ」）の３番目以降の文字（「ａ」）と一致しないため、上記第２条件を満たさない。よって、文字列ｓと文字列ｒとの間の編集距離は閾値τを上回ると判断される。実際に、文字列ｓと文字列ｒとの編集距離は４である。
【００３８】
ところが、任意のｋについて上記第１条件及び上記第２条件を確認するには処理コストが高いため、第１実施形態は、１≦ｋ≦ｑ（または末端に該当する位置をＬとすると、Ｌ−ｑ＋１≦ｋ≦Ｌ）となるｓｕｂｓ＿ｋ及びｓｕｂｒ＿ｋについて確認を行う。上述の例によれば、１文字目から（ｑ＋τ）文字目までの文字列から取り出される並び順が維持されたｑ個の（τ＋１）部分文字列ｓｕｂｓ＿ｋ及びｓｕｂｒ＿ｋに関し、上記第１条件及び上記第２条件が確認される。これは、当該文字列から取り出される並び順が維持された共通のｑ個の文字の組み合わせの存在を確認することと等価である。
【００３９】
従って、本実施形態では、文字列ｓと文字列ｒとの間の編集距離が閾値τ以下となる十分条件として、先頭文字又は末尾文字から（τ＋ｑ）番目までの各端部分に、並び順が維持された共通のｑ個の文字の組み合わせ（共通のｑコンビネーション）が１組以上存在していることを確認する。ｑは上述の通り分割パラメータであり２以上の整数である。
【００４０】
上述の文字列ｓ及びｒの例において、閾値τが２であり、分割パラメータｑが２である場合、文字列ｓのｑコンビネーションは、「ａｂ」、「ａｃ」、「ａｄ」、「ｂｃ」、「ｂｄ」、「ｃｄ」であり、文字列ｒのｑコンビネーションは、「ｄｃ」、「ｄｂ」、「ｄａ」、「ｃｂ」、「ｃａ」、「ｂａ」である。この場合、文字列ｓ及びｒでは、共通のｑコンビネーションが存在せず、両者の編集距離は閾値τを上回ると判断される。文字列ｓと文字列ｒとの間の実際の編集距離は４であり、閾値τを上回っている。
【００４１】
従って、第１実施形態のように、当該端部分から生成されるｑコンビネーションの中に共通するｑコンビネーションを１つも持たないタプルのペアを編集距離計算対象から除外したとしても、検出されるべきタプルのペアの取りこぼしは生じず、適切な類似結合処理結果を出力することができる。
【００４２】
一方、両者の当該端部分に、共通するｑ個の文字の組み合わせ（ｑコンビネーション）が存在すれば、編集距離が閾値τ以下となる可能性がある。そこで、第１実施形態における結合処理装置は、当該端部分に、少なくとも１つ共通するｑコンビネーションを持つタプルのペアを編集距離計算の対象にすればよい。
【００４３】
［第２実施形態］
第２実施形態におけるデータ管理装置は、複数のタプルを対象に編集距離閾値τを用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続される。このデータ管理装置は、複数のタプルを格納するデータ格納部と、当該閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得部と、複数の結合処理装置の中から、データ格納部に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせ（ｑコンビネーション）の中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせ（ｑコンビネーション）の中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定するデータ分配部と、を備える。
【００４４】
第２実施形態におけるデータ管理装置では、データ格納部に格納され類似結合処理の対象となる各タプルが複数の結合処理装置の少なくとも１つにそれぞれ分配され、複数の結合処理装置で類似結合処理が並列に実行されることにより、文字列類似結合処理が高速化される。ここで、類似結合処理の対象となる複数のタプルは、１つのデータ管理装置のデータ格納部に格納される１つのタプル集合から抽出されてもよいし、１つのデータ管理装置のデータ格納部に格納される複数のタプル集合から抽出されてもよいし、複数のデータ管理装置のデータ格納部に格納される複数のタプル集合から抽出されてもよい。
【００４５】
複数の結合処理装置で実行される類似結合処理には、上述のような周知の手法が利用されてもよい。ここで、各結合処理装置とは、類似結合処理を実行し得る単位を示しており、１つのコンピュータであってもよいし、１つのＣＰＵ（Central Processing Unit）であってもよい。よって、ＣＰＵを搭載する基板を複数備えるコンピュータの場合には、複数の結合処理装置は１台のコンピュータとして実現されてもよい。
【００４６】
上記データ管理装置では、データ格納部に格納される各タプルの分配先は、各タプルの結合キー文字列の中の、先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれるｑコンビネーションの少なくとも１つを、結合キー文字列の中の当該端部分に含む他のタプルと同じ分配先にそれぞれ決定される。ここで、他のタプルとは、データ管理装置自身のデータ格納部に格納されるタプルであってもよいし、他のデータ管理装置により保持されるタプルであってもよい。
【００４７】
結果として、１つの結合処理装置では、結合キー文字列の中の先頭文字から（τ＋ｑ）番目までの端部分に共通する少なくとも１つのｑ個の文字の組み合わせ（ｑコンビネーション）を持つタプルのペア、又は、結合キー文字列の中の末尾文字から（τ＋ｑ）番目までの端部分に共通する少なくとも１つのｑコンビネーションを持つタプルのペアを対象に類似結合処理が行われる。一方、結合キー文字列の中の当該端部分に共通するｑコンビネーションを１つも持たないタプルの組み合わせは、同じ結合処理装置には分配されないため、編集距離計算の対象から除外されることになる。
【００４８】
つまり、第２実施形態では、タプルの組み合わせが同じ結合処理装置に分配されるか否かにより、そのタプルの組み合わせが編集距離計算の対象とされるか否かが決まる。結果、第２実施形態によれば、第１実施形態と同様の効果を得ることができる。
【００４９】
［第３実施形態］
〔システム構成〕
図１は、第３実施形態におけるシステムの構成例を概念的に示す図である。第３実施形態におけるシステム１は、システム制御装置１０、データ管理装置２０（＃１）及び２０（＃２）、結合処理装置３０（＃１）、３０（＃２）、３０（＃３）及び３０（＃４）等を有する。以降、データ管理装置及び結合処理装置については、区別する必要のある場合を除き、データ管理装置２０及び結合処理装置３０と表記する。
【００５０】
システム制御装置１０は、類似結合処理の要求を受け、この要求に応じた類似結合処理を実行するために、データ管理装置２０及び結合処理装置３０を制御する。システム制御装置１０は、各結合処理装置３０からそれぞれ送られる結合結果を受け、最終的な文字列類似結合処理の結果を出力する。
【００５１】
データ管理装置２０は、結合処理対象となる少なくとも１つのデータ（タプル集合）を管理する。第３実施形態では、データ管理装置２０（＃１）及び２０（＃２）はそれぞれデータを管理する。データ管理装置２０は、第１実施形態と同様の考え方により自身で管理するデータを形成する各タプルの分配先をそれぞれ決め、決められた各分配先となる結合処理装置３０に各タプルに関するデータを分配する。なお、具体的には、第３実施形態では、各タプルに関するデータとして、後述するＳＩＰタプルが分配される。
【００５２】
結合処理装置３０は、データ管理装置２０から分配されたデータに基づいて、編集距離が編集距離閾値τの条件を満たすタプルペアを特定し、その特定されたタプルペアに関するデータを結合結果としてシステム制御装置１０に送る。
【００５３】
システム制御装置１０、データ管理装置２０及び結合処理装置３０は、ネットワーク７を介してそれぞれ通信可能に接続される。ネットワーク７は、インターネット等のような公衆網、ＷＡＮ（Wide Area Network）、ＬＡＮ（Local Area Network）、無線通信ネットワーク等である。なお、本実施形態は、各装置間が通信可能に接続されていれば、各装置間の通信プロトコル、ネットワーク形態等を限定しない。
【００５４】
システム制御装置１０、データ管理装置２０及び結合処理装置３０は、図１に示されるように、ハードウェア構成として、ＣＰＵ２、メモリ３、入出力インタフェース（Ｉ／Ｆ）４等をそれぞれ有する。これら各ハードウェア要素は例えばバス５により接続される。メモリ３は、例えば、ＲＡＭ（Random Access Memory）２、ＲＯＭ（Read Only Memory、図示せず）、ハードディスク（ＨＤＤ）等である。入出力Ｉ／Ｆ４は、ネットワーク７を介して他の装置と通信を実現し得るネットワークインタフェースを含む。本実施形態は、各装置のハードウェア構成を限定しない。
【００５５】
また、本実施形態は、データ管理装置及び結合処理装置の台数を限定しない。結合処理対象のデータが１つのデータ管理装置２０に保持される場合には、１つのデータ管理装置２０が存在すればよい。結合処理装置３０は、１台以上、かつ、入力データから生成されるｑコンビネーションの種類数と等しい台数以下分、存在すればよい。この台数の根拠については後述する。
【００５６】
〔装置構成〕
以下、第３実施形態におけるシステム１を構成する各装置の詳細構成についてそれぞれ説明する。
【００５７】
〈システム制御装置〉
図２は、システム制御装置１０の構成例を概念的に示すブロック図である。システム制御装置１０は、図２に示されるように、要求制御部１１、結果生成部１２、結合結果格納部１５等を有する。要求制御部１１及び結果生成部１２は、例えば、ＣＰＵ２によりメモリ３に格納されるプログラムが実行されることで実現される。また、結合結果格納部１５は、例えば、メモリ３上に実現される。
【００５８】
要求制御部１１は、文字列類似結合の処理要求を取得し、この処理要求の内容に基づき実行命令を生成し、入出力Ｉ／Ｆ４の通信インタフェースを介して当該実行命令をデータ管理装置２０及び結合処理装置３０へ送信する。ここで、当該処理要求は、結合処理対象となるデータを特定するためのデータ識別子と、その対象データの結合キー属性の情報と、閾値τと、分割パラメータｑを含む。当該処理要求は、通信を介して外部の装置から取得されてもよいし、システム制御装置１０のユーザインタフェース（図示せず）を介して入力されてもよい。
【００５９】
データ管理装置２０へ送られる上記実行命令は、上記処理要求に含まれていた各データ、閾値τ及び分割パラメータｑと共に、結合処理装置３０のネットワークアドレス情報（例えば、ＩＰ（Internet Protocol）アドレス及びポート）を含む通信メッセージである。一方、結合処理装置３０へ送られる上記実行命令は、データ識別子、閾値τ、分割パラメータｑ、結合処理装置３０のネットワークアドレス情報（例えば、ＩＰアドレス）、システム制御装置１０のネットワークアドレス情報（例えば、ＩＰアドレス）等を含む通信メッセージである。本実施形態は、この通信メッセージのフォーマットを限定しない。
【００６０】
結合結果格納部１５は、各結合処理装置３０から送られる文字列類似結合の局所結合結果を格納する。結合処理装置３０において編集距離が閾値τの条件を満たすと推定されたタプルのペアが存在する場合には、その局所結合結果には、局所結果タプルがそのペアの数分含まれる。局所結果タプルには、タプルのペアを特定するためのタプルポインタのペア及び編集距離推定値が含まれる。
【００６１】
編集距離推定値は、結合処理装置３０により算出される値であり、以降、局所編集距離とも表記される。この局所編集距離の詳細については後述する。タプルポインタは、システム１内で扱われる全タプルの中から１つのタプルを特定するための識別情報であり、タプル特定データと呼ぶこともできる。本実施形態では、タプルポインタは、或るタプル集合（データ）の中で或るタプルを特定するためのタプル識別子と、そのタプル集合（データ）を特定するためのデータ識別子とから形成される。なお、タプル識別子がシステム１内で扱われる全タプルに関しユニークに付される場合には、タプルポインタは、タプル識別子のみで形成されてもよい。
【００６２】
結果生成部１２は、入出力Ｉ／Ｆ４の通信インタフェースを介して各結合処理装置３０から局所結合結果をそれぞれ取得する。結果生成部１２は、取得された局所結合結果を結合結果格納部１５に格納する際に、同じタプルポインタのペアを含む局所結果タプルを検出し、検出された局所結果タプルの中の最小の局所編集距離を持つ局所結果タプルのみを編集距離が前記編集距離閾値τの条件を満たすタプルのペアの情報として結合結果格納部１５に格納する。
【００６３】
〈データ管理装置〉
図３は、データ管理装置２０の構成例を概念的に示すブロック図である。データ管理装置２０は、図３に示されるように、ＳＩＰタプル生成部２１、データ分配部２２、データ格納部２５等を有する。ＳＩＰタプル生成部２１及びデータ分配部２２は、例えば、ＣＰＵによりメモリに格納されるプログラムが実行されることで実現される。また、データ格納部２５は、例えば、メモリ上に実現される。
【００６４】
データ格納部２５は、データ（タプル集合）とそのデータを特定するためのデータ識別子とを格納する。例えば、データ格納部２５は、入力タプル集合Ｓ及び入力タプル集合Ｒの少なくとも１つと、その識別子Ｓ及びＲの少なくとも１つを格納する。このように、データ格納部２５は、データ識別子の異なる複数のデータを格納してもよい。
【００６５】
ＳＩＰタプル生成部２１は、入出力Ｉ／Ｆ４の通信インタフェースを介して、システム制御装置１０から実行命令を受信し、当該実行命令に含まれるデータ識別子に対応するデータをデータ格納部２５から抽出する。例えば、実行命令にデータ識別子Ｒが含まれている場合には、ＳＩＰタプル生成部２１は、入力タプル集合Ｒの全タプルを抽出する。当該実行命令には、閾値τ及び分割パラメータｑが含まれるため、ＳＩＰタプル生成部２１は、それらのデータの取得部と呼ぶこともできる。このように、処理対象となるデータはタプル（行）の集合であり、各タプルは、１つ以上の属性（Ａ０、Ａ１、．．．、Ａｎ）とそれに対応する属性値（ａ０、ａ１、．．．、ａｎ）とのペアの集合であり、属性値の値を用いて＜ａ０、ａ１、．．．、ａｎ＞と表わすこともできる。
【００６６】
ＳＩＰタプル生成部２１は、抽出されたデータに含まれる各タプルに関し、（τ＋ｑ）個の文字からｑ個の文字を選択する全組み合わせの数分のＳＩＰタプルをそれぞれ生成する。ＳＩＰタプルは、タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目の端部分に含まれる各ｑコンビネーションに対して、末尾部分文字列と文字配置情報とタプルポインタとの組み合わせ、又は、タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれる各ｑコンビネーションに対して、先頭部分文字列と文字配置情報とタプルポインタとの組み合わせを含む。各タプルの結合キーは、システム制御装置１０から送られる実行命令に含まれる結合キー属性の情報により特定される。なお、前者の文字配置情報と後者の文字配置情報とを区別する必要がある場合には、前者を第１の文字配置情報と表記し、後者を第２の文字配置情報と表記する。
【００６７】
ｑコンビネーションに対応する末尾部分文字列とは、結合キー文字列中における当該ｑコンビネーションの末尾文字の次の文字から末尾文字までの文字列を示す。ｑコンビネーションに対応する第１文字配置情報は、当該ｑコンビネーションの先頭文字の当該結合キー文字列中の位置及び当該ｑコンビネーションに含まれる文字間に存在する当該結合キー文字列中の他の文字の数を要素として含む。ここで、ｑコンビネーションに含まれる各文字をＱ［ｋ］（１≦ｋ≦ｑ）で示し、当該結合キー文字列中におけるその文字Ｑ［ｋ］の位置をＩｎｄｅｘ（Ｑ［ｋ］）で示した場合、ｑコンビネーションに対応する末尾部分文字列とは、当該結合キー文字列中の（Ｉｎｄｅｘ（Ｑ［ｑ］）＋１）番目から末尾までの端部分文字列を示す。また、ｑコンビネーションに対応する第１文字配置情報は、（Ｉｎｄｅｘ（Ｑ［１］）−１）及び（Ｉｎｄｅｘ（Ｑ［ｋ］）−Ｉｎｄｅｘ（Ｑ［ｋ−１］）−１）（２≦ｋ≦ｑ）を要素として含む。
【００６８】
ｑコンビネーションに対応する先頭部分文字列とは、結合キー文字列中における当該ｑコンビネーションの先頭文字より前の文字列を示す。ｑコンビネーションに対応する第２文字配置情報は、当該ｑコンビネーションに含まれる文字間に存在する当該結合キー文字列中の他の文字の数及び当該ｑコンビネーションの末尾文字の当該結合キー文字列中の位置を要素として含む。ここで、ｑコンビネーションに含まれる各文字をＱ［ｋ］（１≦ｋ≦ｑ）で示し、当該結合キー文字列中におけるその文字Ｑ［ｋ］の位置をＩｎｄｅｘ（Ｑ［ｋ］）で示した場合、ｑコンビネーションに対応する先頭部分文字列とは、当該結合キー文字列における先頭から（Ｉｎｄｅｘ（Ｑ［１］）−１）番目までの端部分文字列を示す。また、ｑコンビネーションに対応する第２文字配置情報は、（Ｉｎｄｅｘ（Ｑ［ｋ＋１］）−Ｉｎｄｅｘ（Ｑ［ｋ］）−１）（１≦ｋ≦ｑ−１）及び（結合キー文字列長−Ｉｎｄｅｘ（Ｑ［ｑ］）−１）を要素として含む。
【００６９】
上述のように文字配置情報は、複数の要素を含む配列として実現されてもよいため、以降、文字配置情報を文字配置配列と表記する場合もある。
【００７０】
図４Ａは、結合キー文字列「Ｃａｅｓａｒ」から生成されるＳＩＰタプルの例を示す図である。図４Ｂは、結合キー文字列「Ｄａｋ」から生成されるＳＩＰタプルの例を示す図である。図４Ａ及び図４Ｂの例では、閾値τが２であり、分割パラメータｑが２である。図４Ｂに示されるように、「Ｄａｋ」のように結合キー文字列の長さが（τ＋ｑ）より小さいとき、足りない文字数分、特殊文字「＊」を埋めることで、ｑコンビネーションが生成される。特殊文字「＊」は、同じ特殊文字以外のどの文字とも一致しない文字であればどのようなものであってもよい。また、このような場合には、図４Ｂに示されるように、末尾部分文字列には空文字（図４Ｂに示す−）が入れられる。
【００７１】
また、図４Ａで示されるＳＩＰタプルは、ｑシーケンスを結合キー文字列の末尾文字からの端部分から生成する場合には、次のように生成される。この場合、ｑシーケンスは、「ｅｓ」、「ｅａ」、「ｅｒ」、「ｓａ」、「ｓｒ」、「ａｒ」である。なお、ＳＩＰタプルは、＜（末尾部分文字列）、（文字配置情報）、タプルポインタ＞として表記される。
「ｅｓ」：  ＜Ｃａ、（０、２）、ｐｔｒ＞
「ｅａ」：  ＜Ｃａ、（１、１）、ｐｔｒ＞
「ｅｒ」：  ＜Ｃａ、（２、０）、ｐｔｒ＞
「ｓａ」：  ＜Ｃａｅ、（０、１）、ｐｔｒ＞
「ｓｒ」：  ＜Ｃａｅ、（１、０）、ｐｔｒ＞
「ａｒ」：  ＜Ｃａｅｓ、（０、０）、ｐｔｒ＞
【００７２】
上述のいずれのＳＩＰタプル生成手法においても、上記例では、４個の文字から２個の文字を選択する組み合わせの数として、６個のＳＩＰタプルが生成される。
【００７３】
ＳＩＰタプル生成部２１は、ＳＩＰタプルの生成が完了すると、対応するｑコンビネーション毎にＳＩＰタプルを振り分ける。以降、ＳＩＰタプルが振り分けられる単位をバケットと表記する。各バケットには、対応するｑコンビネーションがラベルとして付される。
【００７４】
図５は、ＳＩＰタプルの振り分け手法の例を概念的に示す図である。図５の上部の２つの表が結合すべき入力データであり、結合キー属性は「名前」及び「名前'」である。ＳＩＰタプル生成部２１は、閾値τ（＝２）及び分割パラメータｑ（＝２）を受けて、各タプルに対して各ＳＩＰタプルをそれぞれ生成し、対応するｑコンビネーションのラベルが付されたバケットに各ＳＩＰタプルを振り分ける。図５には、一部のバケット及び一部のＳＩＰタプルのみが示されており、ラベルＣｅ、Ｃｓ、ｅｓ及びＧｎの各バケットが示されている。
【００７５】
なお、ＳＩＰタプルの態様は上記２つのうちのいずれの方法が利用されてもよい。このようにＳＩＰタプルは、結合キーに関する情報を含むタプルであるため、キー情報タプルと呼ぶこともできる。これにより、ＳＩＰタプル生成部２１は、キー情報生成部と呼ぶこともできる。
【００７６】
データ分配部２２は、ＳＩＰタプル生成部２１により生成されたバケットの集合を受け、各バケット（ＳＩＰタプルの集合）の分配先を決定し、当該各バケットを、分配先として決定された各結合処理装置３０に、各タプルのデータとして、それぞれ分配（送信）する。データ分配部２２は、各バケットに対応するｑコンビネーションに基づいて、各バケットの分配先を決定する。結果、当該ｑコンビネーションが１つでも共通するＳＩＰタプルのペアは、同じ結合処理装置３０に分配される。
【００７７】
例えば、データ分配部２２は、ｑコンビネーションを入力して、結合処理装置３０（＃１）、３０（＃２）、３０（＃３）及び３０（＃４）のいずれか１つを特定し得る１つの数値を出力する関数（ハッシュ関数等）を用いて、各バケット（ＳＩＰタプルの集合）の分配先を決定する。データ分配部２２は、決定された分配先の結合処理装置３０のネットワークアドレスをシステム制御装置１０から送られる実行命令に含まれるネットワークアドレス情報から特定し、対応する各バケットをその結合処理装置３０に送信する。なお、或るｑコンビネーション（ｑ個の文字）から分配先を決定するための手法は、ハッシュ関数等のような関数を利用する形態に限定されない。
【００７８】
ここで、各タプルから生成されるｑコンビネーションは、結合キー文字列の中の先頭文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたいずれかｑ個の文字、或いは、結合キー文字列の中の末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたいずれかｑ個の文字となる。よって、ｑコンビネーションが１つでも共通するタプルｓ及びタプルｒについては、タプルｓに関して（τ＋ｑ）個の中からｑ個選択される組み合わせの数分生成されるＳＩＰタプルと、タプルｒに関して同数だけ生成されるＳＩＰタプルとの全組み合わせ（ペア）のうちの１つ以上のペアが、同じ結合処理装置３０に分配され、類似結合処理の対象とされる。なお、本実施形態では、当該端部分に共通するｑコンビネーションが１つも存在しないタプルｓ及びタプルｒについては、同じ結合処理装置３０に分配されてもよいし、異なる結合処理装置３０に分配されてもよい。いずれの場合であっても、当該端部分に共通するｑコンビネーションが１つも存在しないタプルｓ及びタプルｒについては、結合処理装置３０において類似結合処理対象から除外される。
【００７９】
〈結合処理装置〉
図６は、結合処理装置３０の構成例を概念的に示すブロック図である。結合処理装置３０は、図６に示されるように、ＳＩＰタプル受信部３１、結合処理部３２、推定値算出部３３、ＳＩＰタプル格納部３５等を有する。ＳＩＰタプル受信部３１、結合処理部３２及び推定値算出部３３は、例えば、ＣＰＵによりメモリに格納されるプログラムが実行されることで実現される。また、ＳＩＰタプル格納部３５は、例えば、メモリ上に実現される。
【００８０】
ＳＩＰタプル受信部３１は、データ管理装置２０から送られるバケットを受信し、ＳＩＰタプル格納部３５に格納する。ＳＩＰタプル格納部３５は、ＳＩＰタプル受信部３１により受信されたバケットを格納する。ＳＩＰタプル格納部３５は、ラベル（ｑコンビネーション）が一致するバケット（ＳＩＰタプルの集合）の和集合を生成し、この和集合を１つの集合として格納する。
【００８１】
結合処理部３２は、システム制御装置１０から送られる実行命令を受信し、この実行命令に含まれる各種データを保持する。上述のように、この各種データには、データ識別子、閾値τ、分割パラメータｑ、データ管理装置２０のネットワークアドレス情報（例えば、ＩＰアドレス）、システム制御装置１０のネットワークアドレス情報（例えば、ＩＰアドレス）等が含まれる。
【００８２】
結合処理部３２は、上述のように保持されるデータを用いて、ＳＩＰタプル格納部３５に格納されるＳＩＰタプルを対象に類似結合処理を実行する。具体的には、結合処理部３２は、ＳＩＰタプルの集合をバケット（対応するｑコンビネーション）毎にＳＩＰタプル格納部３５から抽出し、抽出されたｑコンビネーションが共通する複数のＳＩＰタプルの中の２つの全組み合わせ（全ペア）に関し、推定値算出部３３に所定の処理を実行させる。ここで、類似結合処理が異なるタプル集合（データ）間の結合を対象とする場合には、結合処理部３２は、ｑコンビネーションが共通する複数のＳＩＰタプルの中のデータ識別子が異なる２つの全組み合わせ（全ペア）に関し、推定値算出部３３に所定の処理を実行させる。当該データ識別子は、ＳＩＰタプルに含まれるタプルポインタから抽出される。これにより、結合キー文字列におけるｑコンビネーションに共通するものが存在しないタプルｓ及びタプルｒについては、同じ結合処理装置３０に分配されたとしても、類似結合処理対象から除外される。
【００８３】
結合処理部３２は、推定値算出部３３から処理結果を取得し、取得された処理結果に基づいて、編集距離が閾値τの条件を満たすと推定されるＳＩＰタプルのペアを特定する。推定値算出部３３の処理結果としては、ＳＩＰタプルの各ペアに関する局所編集距離と、その編集距離が閾値τの条件を満たすか否かを示す情報が取得される。結合処理部３２は、特定された各ペアに関し、タプルポインタのペア及び局所編集距離を含む局所結果タプルをそれぞれ生成し、生成された局所結果タプルを含む局所結合結果をそれぞれシステム制御装置１０に送信する。
【００８４】
推定値算出部３３は、結合処理部３２からＳＩＰタプルのペア（２つのＳＩＰタプル）を受けると、そのペアの編集距離が閾値τの条件を満たすか否かの判定、及び、そのペアの局所編集距離の算出を行う。なお、局所編集距離の算出は、当該編集距離が閾値τの条件を満たす場合のみ行われるようにしてもよい。
【００８５】
ＳＩＰタプルのペアの編集距離の条件判定は次のような３つの手法により行われる。
【００８６】
第１条件判定は、各ＳＩＰタプルに含まれる文字配置配列を用いて行われる。具体的には、推定値算出部３３は、ＳＩＰタプルの各ペアに関し、各文字配置配列に含まれる同種の要素のうちの大きいほうの値を各要素についてそれぞれ抽出し、それらの合計値を算出する。ＳＩＰタプルのペアをｔ１及びｔ２で示し、各ＳＩＰタプルの文字配置配列をＡ１及びＡ２で示した場合、推定値算出部３３は、以下の式を計算する。以下の式のｍａｘ（）は、括弧内の値のうちの大きい方の値を抽出することを意味する。
ｓｕｍ＝ｍａｘ（Ａ１［０］、Ａ２［０］）＋．．．＋ｍａｘ（Ａ１［ｑ−１］、Ａ２［ｑ−１］）
【００８７】
推定値算出部３３は、算出された合計値（ｓｕｍ）が閾値τより大きい場合には、そのＳＩＰタプルのペアの編集距離が閾値τの条件を満たさないことを示す処理結果を結合処理部３２に返す。
【００８８】
第２条件判定は、各ＳＩＰタプルに含まれる末尾部分文字列又は先頭部分文字列を用いて行われる。具体的には、推定値算出部３３は、ＳＩＰタプルの各ペアに関し、末尾部分文字列間の編集距離、又は、先頭部分文字列間の編集距離を算出する。以降、ここで算出される編集距離は、部分文字列編集距離ｓｅｄと表記される場合もある。推定値算出部３３は、算出された部分文字列編集距離ｓｅｄが閾値τより大きい場合には、そのＳＩＰタプルのペアの編集距離が閾値τの条件を満たさないことを示す処理結果を結合処理部３２に返す。
【００８９】
第３条件判定は、上記第１条件判定で算出された合計値ｓｕｍと上記第２条件判定算出された部分文字列編集距離ｓｅｄを用いて行われる。具体的には、推定値算出部３３は、上記第１条件判定で算出された合計値ｓｕｍと上記第２条件判定で算出された部分文字列編集距離ｓｅｄとを足し合わせた局所編集距離ｌｅｄを算出し、この局所編集距離ｌｅｄと閾値τとを比較する。推定値算出部３３は、局所編集距離ｌｅｄが閾値τより大きい場合に、そのＳＩＰタプルのペアの編集距離が閾値τの条件を満たさないことを示す処理結果を結合処理部３２に返す。
【００９０】
推定値算出部３３は、局所編集距離ｌｅｄが閾値τ以下である場合に、その局所編集距離ｌｅｄと、そのＳＩＰタプルのペアの編集距離が閾値τの条件を満たすことを示す情報とを処理結果として結合処理部３２に返す。
【００９１】
上記各条件判定は、第１条件判定、第２条件判定、第３条件判定の順に、そのＳＩＰタプルのペアの編集距離が閾値τの条件を満たさないと判定されるまで実行されてもよい。また、第２条件判定が第１条件判定より先に実行されてもよい。また、各条件判定は、合計値ｓｕｍ、部分文字列編集距離ｓｅｄ及び局所編集距離ｌｅｄを算出した後に、それぞれ行われるようにしてもよい。
【００９２】
ここで、上述のように部分文字列編集距離ｓｅｄを用いて算出される局所編集距離ｌｅｄと、結合キー文字列全体を用いて算出される通常の編集距離（以降、真の編集距離と表記する）との関係について説明する。
【００９３】
図７は、文字列「Ｃａｅｓａｒ」及び「Ｃｅａｓａｒ」に関し生成された各ＳＩＰタプルの局所編集距離の計算を概念的に示す図である。図７の例では、閾値τが２であり分割パラメータｑが２であり、ラベル（ｑコンビネーション）が「Ｃａ」、「Ｃｅ」、「Ｃｓ」、「ａｓ」及び「ｅｓ」である各バケットを受信した結合処理装置３０が、文字列「Ｃａｅｓａｒ」及び「Ｃｅａｓａｒ」に関する各局所編集距離ｌｅｄをそれぞれ算出する。図７の右下には、各バケットに関し行われる局所編集距離の計算式が示されている。なお、各文字列の０番目の要素は空文字であると仮定する。
【００９４】
距離計算を経路探索問題で捉えた場合、局所編集距離の計算は、スタート地点から或る地点まで又は或る地点からゴール地点までの経路をあらかじめ与えることで、真の編集距離を計算するよりも少ない経路候補の中から最短のものを探索している。例えば、ラベル「Ｃａ」のバケットで行われる計算は、地点（０、０）から地点（１、１）へのパスＰ１と、地点（１、２）から地点（２、３）へのパスＰ２とを必ず通ると見なし、地点（２、３）からゴールである地点（６、６）へ至るあらゆる経路候補の中から最短のものを探索する処理と等価である。
【００９５】
以降、上記パスＰ１及びＰ２のように、ラベル（ｑコンビネーション）に含まれる各文字の地点は必ず通過すると仮定することができるため、このようなパスを見なしパスと呼ぶこともできる。このような見なしパスの組み合わせは、明らかに、文字列「Ｃａｅｓａｒ」及び「Ｃｅａｓａｒ」において先頭又は末尾から（τ＋ｑ）までの範囲で文字が一致している地点の組み合わせである。
【００９６】
閾値τ以下の編集距離を持つ文字列同士は、先頭又は末尾から（τ＋ｑ）までの範囲の文字のいずれかｑ個が一致しているはずである。このとき、真の編集距離を得る最短経路は必ず見なしパスの組み合わせを通過する。従って、本実施形態では、あらゆる見なしパスの組み合わせに対していずれかの結合処理装置が局所編集距離を計算する。
【００９７】
このとき、ＳＩＰタプルに含まれる情報では、スタート地点（０、０）からラベル（ｑコンビネーション）の末尾文字に相当する地点への経路の中で見なしパス以外のパスを結合処理装置３０は知ることはできない。本実施形態は、当該知ることができないパスの経路長を各文字配置配列に含まれる同種の要素のうちの大きいほうの値を各要素について合計された値ｓｕｍで推定する。例えば、ラベル「Ｃａ」のバケットの場合には、パスＰ１及びＰ２以外のパスの経路長はｓｕｍ（＝ｍａｘ（０、０）＋ｍａｘ（１、０））で推定される。
【００９８】
以上より、ラベル「Ｃａ」のバケットに関する局所編集距離の計算は次式で示すことができる。ここで、二つの文字列ｘ、ｙの編集距離はＥＤ（ｘ、ｙ）と表記される。次式のＥＤ（「Ｃ」、「Ｃ」）及びＥＤ（「ａ」、「ａ」）が、ラベル「Ｃａ」のバケットにおける見なしパスの経路長を示す。
ｌｅｄ＝ｍａｘ（｜「」｜、｜「」｜）＋ＥＤ（「Ｃ」、「Ｃ」）＋ｍａｘ（｜「ｅ」｜、｜「」｜）＋ＥＤ（「ａ」、「ａ」）＋ＥＤ（「ｓａｒ」、「ｅｓａｒ」）
【００９９】
このような計算式で得られる局所編集距離ｌｅｄと真の編集距離との関係を以下に示す。文字列ｘの先頭からｉ−１番目の文字までの先頭部分文字列をｘｈ＿ｉ、文字列ｘのｉ番目の文字から末尾までの末尾部分文字列をｘｔ＿ｉで示す場合、文字列ｘ及び文字列ｙに関し、次式が成り立つ。
ＥＤ（ｘ、ｙ）≦ＥＤ（ｘｈ＿ｉ、ｙｈ＿ｊ）＋ＥＤ（ｘｔ＿ｉ、ｙｔ＿ｊ）
ＥＤ（ｘ、ｙ）≦ｍａｘ（｜ｘ｜、｜ｙ｜）
【０１００】
更に、ｘｈ＿ｉ、ｙｈ＿ｊをそれぞれｖ番目とｕ番目の文字を境に二つに分割し、ｘｈ＿ｉから（ｘｈ＿ｉ）ｈ＿ｖ及び（ｘｈ＿ｉ）ｔ＿ｖが取得され、ｙｈ＿ｊから（ｙｈ＿ｊ）ｈ＿ｕ及び（ｙｈ＿ｊ）ｔ＿ｕが取得されるとすると、次式が得られる。
ＥＤ（ｘ、ｙ）≦ＥＤ（ｘｈ＿ｉ、ｙｈ＿ｊ）＋ＥＤ（ｘｔ＿ｉ、ｙｔ＿ｊ）
ＥＤ（ｘ、ｙ）≦ＥＤ（（ｘｈ＿ｉ）ｈ＿ｖ、（ｙｈ＿ｊ）ｈ＿ｕ）＋ＥＤ（（ｘｈ＿ｉ）ｔ＿ｖ、（ｙｈ＿ｉ）ｔ＿ｕ）＋ＥＤ（ｘｔ＿ｉ、ｙｔ＿ｊ）
【０１０１】
このことから、文字列ｘ及びｙを重なりのない長さが０以上の任意の（２ｑ＋１）個の部分文字列に分割したとき、ｋ番目の部分文字列をｘ＿ｋ及びｙ＿ｋで示すと、次式が得られる。
ＥＤ（ｘ、ｙ）≦ＥＤ（ｘ＿０、ｙ＿０）＋．．．＋ＥＤ（ｘ＿２ｑ、ｙ＿２ｑ）
【０１０２】
上記式の右辺のうち、ＥＤ（ｘ＿２ｑ、ｙ＿２ｑ）を除く或るｑ個のＥＤ（ｘ＿ｋ、ｙ＿ｋ）をｍａｘ（｜ｘ＿ｋ｜、｜ｙ＿ｋ｜）に置き換え、残りのｑ個をＥＤ（ｘ＿ｋ、ｙ＿ｋ）＝０かつ｜ｘ＿ｋ｜＝｜ｙ＿ｋ｜＝１と仮定すると、このように修正された右辺は上述の局所編集距離ｌｅｄの算出式と等しくなる。即ち、次式を導くことができる。
ＥＤ（ｘ、ｙ）≦ｌｅｄ
【０１０３】
このように、推定値算出部３３で算出される局所編集距離ｌｅｄは、真の編集距離の上限値を示す。つまり、各結合処理装置３０は、編集距離が閾値τ以下である各タプルのペアにおける、最短経路上に存在する可能性のあるあらゆる見なしパスの組み合わせに関して、局所上限値を計算している。従って、計算された局所編集距離ｌｅｄのうちで最小の局所編集距離ｌｅｄは真の編集距離と等しくなると言える。
【０１０４】
このような内容は、以下の定理として示すことができる。即ち、与えられた文字列ｘ及びｙ間の編集距離ＥＤ（ｘ、ｙ）が編集距離閾値τ以下であるならば、次の条件を満たす正の整数のペア＜ｉ、ｊ＞が少なくとも１つ必ず存在する。
（１≦ｉ≦τ＋１）ＡＮＤ（１≦ｊ≦τ＋１）ＡＮＤ（ｘ［ｉ］＝ｙ［ｊ］）ＡＮＤ｛ｍａｘ（｜ｘｈ＿ｉ、ｙｈ＿ｊ｜）＋ＥＤ（ｘｔ＿ｉ、ｙｔ＿ｊ）＝ＥＤ（ｘ、ｙ）｝
、又は、
（０≦｜ｘｓ｜−ｉ＋１≦τ＋１）ＡＮＤ（０≦｜ｙｓ｜−ｊ＋１≦τ＋１）ＡＮＤ（ｘ［ｉ］＝ｙ［ｊ］）ＡＮＤ｛ｍａｘ（｜ｘｔ＿ｉ、ｙｔ＿ｊ｜）＋ＥＤ（ｘｈ＿ｉ、ｙｈ＿ｊ）＝ＥＤ（ｘ、ｙ）｝
【０１０５】
ここで、ｘｔ＿ｉは、文字列ｘの先頭文字からｉ番目の文字から末尾文字までの末尾部分文字列を示し、｜ｘｈ＿ｉ｜は、残りの先頭部分文字列の文字列長を示し、ｙｔ＿ｊは、文字列ｙの先頭文字からｊ番目の文字から末尾文字までの末尾部分文字列を示し、｜ｙｈ＿ｊ｜は、残りの先頭部分文字列の文字列長を示す。また、ｘ［ｉ］は、文字列ｘの先頭文字からｉ番目の文字を示し、ｙ［ｊ］は、文字列ｙの先頭文字からｊ番目の文字を示し、｜ｘｓ｜は、文字列ｘの文字列長を示し、｜ｙｓ｜は、文字列ｙの文字列長を示す。
【０１０６】
上記定理は、ＥＤ（ｘｔ＿ｉ、ｙｔ＿ｊ）に対しても再帰的に成立するため、上記定理は、帰納法により、任意の分割パラメータｑに対して成立する。
【０１０７】
上記の定理から、真の編集距離が閾値τ以下であるとき、ＳＩＰタプルから生成されるタプルｘ及びタプルｙに関する複数の局所編集距離のうち最も小さい局所編集距離が、必ず真の編集距離と等しくなることが保証される。タプルｘ及びタプルｙに関する局所編集距離は複数生成される可能性があるため、閾値τ以下となる局所編集距離も複数存在する可能性があるが、上述のように、システム制御装置１０の結果生成部１２において、局所編集距離を用いた局所結果タプルのフィルタリングが行われることで、真の編集距離を局所編集距離から容易に知ることが出来る。よって、本実施形態のように、真の編集距離の代わりに局所編集距離を用いて類似結合結果を得たとしても、正確な類似結合結果を得ることができる。
【０１０８】
〔動作例〕
次に、第３実施形態におけるシステム１の動作例について説明する。図８は、第３実施形態におけるシステム１の全体的な動作の概要を示すフローチャートである。
【０１０９】
まず、システム制御装置１０において、要求制御部１１が文字列類似結合の処理要求を取得する（Ｓ８１）。この処理要求には、結合処理対象となるデータを特定するためのデータ識別子（例えば、Ｄ１及びＤ２）と、その対象データの結合キー属性の情報（例えば、「名前」及び「名前'」）と、編集距離閾値τと、分割パラメータｑとが含まれる。要求制御部１１は、取得された処理要求の内容に基づいて実行命令を生成し、生成された各実行命令をデータ管理装置２０及び結合処理装置３０に送る。
【０１１０】
当該実行命令を受信した各データ管理装置２０は次のように動作する。ＳＩＰタプル生成部２１が、当該実行命令に含まれるデータ識別子に対応するデータをデータ格納部２５から抽出し、抽出されたデータに含まれる各タプルに関し、各ｑコンビネーションに対応するＳＩＰタプルをそれぞれ生成する（Ｓ８２）。ＳＩＰタプルは、各タプルに関し、（τ＋ｑ）個の文字からｑ個の文字を選択する全ての組み合わせの数分、生成される。
【０１１１】
続いて、ＳＩＰタプル生成部２１は、各ＳＩＰタプルを、対応するｑコンビネーションのラベルが付されたバケットにそれぞれ振り分ける（Ｓ８３）。
【０１１２】
データ分配部２２は、ＳＩＰタプル生成部２１により生成されたバケット（ＳＩＰタプル集合）を受け、各バケットの分配先となる結合処理装置３０を特定し、特定された各結合処理装置３０に各バケットをそれぞれ分配する（Ｓ８５）。
【０１１３】
各バケット（ＳＩＰタプル集合）を受信した各結合処理装置３０は次のように動作する。ＳＩＰタプル受信部３１が、データ管理装置２０から送られるバケットを受信し、ＳＩＰタプル格納部３５が、受信されたバケットに関し、ラベル（ｑコンビネーション）が一致するバケットの和集合を生成し、この和集合を１つのバケット（１つのＳＩＰタプル集合）としてＳＩＰタプル格納部３５に格納する。
【０１１４】
結合処理部３２は、ＳＩＰタプルの集合をバケット毎にＳＩＰタプル格納部３５から抽出し、抽出されたバケット毎のＳＩＰタプル集合を対象に類似結合処理を実行する（Ｓ８６）。この類似結合処理では、推定値算出部３３が、各ＳＩＰタプルのペアの編集距離が閾値τを超えるか否かの判定を行い、編集距離が閾値τ以下となる各ＳＩＰタプルのペアに関しその局所編集距離ｌｅｄを算出する。
【０１１５】
結合処理部３２は、推定値算出部３３の処理結果に応じて、編集距離が閾値τの条件を満たすと推定されるＳＩＰタプルのペアを特定し、特定された各ペアに関し、タプルポインタのペア及び局所編集距離ｌｅｄを含む局所結果タプルをそれぞれ生成し、生成された局所結果タプルを含む局所結合結果をそれぞれシステム制御装置１０に送信する（Ｓ８７）。
【０１１６】
各結合処理装置３０から局所結合結果を受信したシステム制御装置１０では、結果生成部１２が、同じタプルポインタのペアを含む局所結果タプルのうち最小の局所編集距離を持つもの以外を排除した後、当該局所結果タプルを結合結果格納部１５に格納する（Ｓ８８）。結果、ユーザは、システム制御装置１０の結合結果格納部１５に格納される局所結果タプルにより、編集距離閾値τの条件を満たすタプルのペアの情報を得ることができる。
【０１１７】
〔第３実施形態における作用及び効果〕
上述したように、第３実施形態では、編集距離閾値τ及び分割パラメータｑを用いて、保持されるデータの各タプルに関し、各ｑコンビネーションに対応するＳＩＰタプルがそれぞれ生成される。そして、対応するｑコンビネーションで特定される各バケットに、ＳＩＰタプルが振り分けられ、ｑコンビネーションに応じて特定された結合処理装置３０に、各バケット（ＳＩＰタプルの集合）がそれぞれ分配され、バケット毎、即ち、ｑコンビネーション毎に、ＳＩＰタプルの情報に基づいて、類似結合処理が実行される。
【０１１８】
このように、第３実施形態では、結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせ（ｑコンビネーション）の中に、共通するものを持たないタプルのペアは類似結合処理（編集距離計算）対象から除外される。
【０１１９】
従って、第３実施形態によれば、全てのタプルのペアに関し類似結合処理を行う手法に比べ、類似結合処理の処理コストを削減し、システム全体での類似結合処理の時間を削減することができる。更に、ＳＩＰタプルという最小限の部分情報を類似結合処理対象として各結合処理装置３０に送ることで、使用する通信リソースを最小限に抑えることができると共に、類似結合処理の並列化を実現することができる。
【０１２０】
また、第３実施形態では、類似結合処理として、文字配置配列を用いた足し算で算出される経路長（ｓｕｍ）、及び、末尾部分文字列間又は先頭部分文字列間の編集距離（部分文字列編集距離ｓｅｄ）、並びに、それらを用いて、ＳＩＰタプルの各ペアに関する編集距離の上限値となり得る局所編集距離ｌｅｄが算出される。そして、これら各情報により、編集距離推定値が閾値τ以下となるＳＩＰタプルのペアが特定される。
【０１２１】
従って、第３実施形態によれば、部分文字列に関する編集距離の計算が行われるに過ぎないため、完全な結合キー文字列の編集距離を算出する手法に比べて、類似結合処理自体の処理コストを抑えることができ、トータルの処理時間を短縮することができる。
【０１２２】
更に、第３実施形態のように、部分文字列を用いた類似結合処理がなされたとしても、タプルのペア＜ｘ、ｙ＞に対して、必ず１つ以上の結合処理装置３０で真の編集距離ＥＤ（ｘ、ｙ）と値が等しくなる局所編集距離ｌｅｄが算出されるため、取りこぼしなく結合処理が行われ、適切な文字列類似結合の結合結果を得ることができる。
【実施例１】
【０１２３】
以下、上述の第３実施形態におけるシステム１のより具体的な例を説明する。特に、ＳＩＰタプル生成部２１の処理、結合処理部３２及び推定値算出部３３の処理、及び、結果生成部１２の処理に関する具体例をそれぞれ説明する。もちろん、各処理は以下の実施例に限定されない。【０１２４】
ＳＩＰタプル生成部２１の処理は、図８の処理（Ｓ８２及びＳ８３）に相当する。この処理について、ここでは、再帰法及び当てはめ法と呼ぶことができる２種類の実施例を説明する。処理対象のデータの規模、閾値τ、分割パラメータｑ等により、これら２種類の実施例には適否がある。【０１２５】
図９及び図１０は、再帰法の動作を示すフローチャートである。図９に示されるように、ＳＩＰタプル生成部２１は、まずデータ格納部２５からデータＤを取得し（Ｓ９１）、更に、データＤから未処理の文字列（タプル）ｓｔｒ及び文字列ｓｔｒのポインタｐを取得する（Ｓ９２、Ｓ９３）。【０１２６】
続いて、ＳＩＰタプル生成部２１は、空文字列ｓｅｑ及びｑ個の要素が全て−１に設定された整数配列Ａを生成する（Ｓ９４、Ｓ９５）。その後、ＳＩＰタプル生成部２１は、空文字列ｓｅｑ、未処理の文字列ｓｔｒ、文字列ｓｔｒのポインタｐ、整数配列Ａ、分割パラメータｑ、分割パラメータｑと閾値τとの合計値を引数として、関数ｐａｒｔｉｔｉｏｎ＿ｒｃを呼び出す（Ｓ９６）。ＳＩＰタプル生成部２１は、このような処理をデータＤ内の未処理の文字列ｓｔｒがなくなるまで繰り返す（Ｓ９７）。【０１２７】
図１０には、関数ｐａｒｔｉｔｉｏｎ＿ｒｃの処理フローが示されている。関数ｐａｒｔｉｔｉｏｎ＿ｒｃは、空文字列ｓｅｑ、未処理の文字列ｓｕｆｆｉｘ、文字列ｓｕｆｆｉｘのポインタｐ、整数配列Ａ、分割パラメータｑ、分割パラメータｑと閾値τとの合計値ｌｉｍｉｔを引数として受け取り、整数変数ｉを１で初期化した後（Ｓ１０１）、整数変数ｉがｌｉｍｉｔ以下である限り、以下の処理を繰り返す。以下の説明では、関数ｐａｒｔｉｔｉｏｎ＿ｒｃを省略して単に関数と表記する。【０１２８】
関数は、要素数ｑの配列Ａ２に整数配列Ａの全要素をコピーする（Ｓ１０３）。次に、関数は、整数変数ｓｉｚｅに文字列ｓｅｑの文字列長を代入する（Ｓ１０４）。更に、関数は、ｓｅｑ２にｓｅｑをコピーする（Ｓ１０５）。【０１２９】
関数は、整数変数ｉがｓｉｚｅを上回る場合（Ｓ１０６；ＹＥＳ）、例外処理を施すために、特殊文字「＊」をｓｅｑ２の末尾に追加する（Ｓ１０７）。一方、関数は、整数変数ｉがｓｉｚｅ以下である場合（Ｓ１０６；ＮＯ）、ｓｕｆｆｉｘのｉ番目の文字ｓｕｆｆｉｘ［ｉ］をｓｅｑ２の末尾に追加する（Ｓ１０８）。【０１３０】
続いて、関数は、配列Ａのｓｉｚｅ番目の要素Ａ［ｓｉｚｅ］にｉ−１を格納する（Ｓ１０９）。更に、関数は、ｓｕｆｆｉｘのｉ＋１番目の文字から末尾までの末尾部分文字列（接尾辞）ｓｕｆｆｉｘ２を取得する（Ｓ１１０）。関数は、ｓｅｑ２の文字列長が分割パラメータｑと等しければ（Ｓ１１１；ＹＥＳ）、ＳＩＰタプル＜ｓｕｆｆｉｘ２、Ａ２、ｐ＞をラベルｓｅｑ２のバケットに挿入する（Ｓ１１２）。【０１３１】
ｓｅｑ２の文字列長が分割パラメータｑと等しくなければ（ｑ未満ならば）（Ｓ１１１；ＮＯ）、関数は、ｓｅｑ２、ｓｕｆｆｉｘ２、Ａ２、ｐ、ｑ、（ｌｉｍｉｔ−ｉ）を引数として再帰的に自身（関数ｐａｒｔｉｔｉｏｎ＿ｒｃ）を呼び出す（Ｓ１１３）。【０１３２】
再帰呼び出しが終了すると、関数は、整数変数ｉに１を加算し（Ｓ１１４）、再度、整数変数ｉがｌｉｍｉｔ以下かどうかを評価する（Ｓ１０２）。整数変数ｉがｌｉｍｉｔを超えると（Ｓ１０２；ＮＯ）、関数は処理を終了する。【０１３３】
図１１は、上述のような再帰法を用いたＳＩＰタプル生成の例を示す図である。図１１には、分割パラメータｑが２であり、閾値τが２であり、処理対象の文字列（タプル）が「ＤＡＬＩ」である場合のＳＩＰタプル生成例が示される。図１１における整数配列Ａが文字配置情報（文字配置配列）に相当し、接尾辞が末尾部分文字列に相当する。図１１には、再帰的に、ｑコンビネーション、文字配置配列（整数配列）及び末尾部分文字列（接尾辞）が生成されていく状況が示されている。【０１３４】
図１２、図１３及び図１４は、当てはめ法の動作を示すフローチャートである。当てはめ法では、図１２に示されるように、ＳＩＰタプル生成部２１は、テンプレート配列Ｓを初期化した後（Ｓ１２１）、関数ｍａｋｅ＿ｔｅｍｐｌａｔｅを呼び出すことによりその配列Ｓを生成する（Ｓ１２２）。【０１３５】
続いて、ＳＩＰタプル生成部２１は、データ格納部２５からデータＤを取得し（Ｓ１２３）、データＤから未処理の文字列（タプル）ｓｔｒを取得する（Ｓ１２４）。ＳＩＰタプル生成部２１は、未処理の文字列ｓｔｒのポインタｐを取得し（Ｓ１２５）、文字列ｓｔｒにおける位置ｑ＋１から末尾までの末尾部分文字列（接尾辞）ｓｕｆｆｉｘを取得する（Ｓ１２６）。なお、位置ｑ＋１以降に文字が存在しない場合には、ｓｕｆｆｉｘには空文字列が設定される。【０１３６】
ＳＩＰタプル生成部２１は、文字列ｓｔｒ、接尾辞ｓｕｆｆｉｘ、分割パラメータｑ、閾値τ及びテンプレート配列Ｓを引数として、関数ｐａｒｔｉｔｉｏｎ＿ｔｅｍｐを呼び出す（Ｓ１２７）。ＳＩＰタプル生成部２１は、データＤに未処理の文字列ｓｔｒが存在しなくなるまで、上述の処理を繰り返す（Ｓ１２８）。【０１３７】
図１３には、関数ｍａｋｅ＿ｔｅｍｐｌａｔｅの処理フローが示されている。関数ｍａｋｅ＿ｔｅｍｐｌａｔｅは、初期化されたテンプレート配列Ｓ、分割パラメータｒ、分割パラメータｒと閾値τとの合計値ｎを引数として受け取ると、まず、１以上ｎ以下のｎ個の整数値からｒ個を選択する全組み合わせ＜ｋ０、．．．、ｋｒ−１＞を生成し、生成された組み合わせを集合Ｃに格納する（Ｓ１３１）。ここで、（ｋ０＜．．．＜ｋｒ−１）とする。以下の説明では、関数ｍａｋｅ＿ｔｅｍｐｌａｔｅを省略して単に関数と表記する。【０１３８】
次に、関数は、集合Ｃから未処理の組＜ｋ０、．．．、ｋｒ−１＞を取得し（Ｓ１３２）、整数変数ｉを０で初期化する（Ｓ１３３）。更に、関数は、整数配列Ａのｉ番目の要素Ａ［ｉ］に（ｋｉ−ｋｉ−１−１）を格納する（Ｓ１３４）。このとき、例外的にｋ−１は１とする。関数は、整数変数ｉが分割パラメータｒ以上となるまで、整数変数ｉに１を加算しながら、処理（Ｓ１３４）を繰り返す（Ｓ１３４、Ｓ１３５；ＹＥＳ、Ｓ１３６）。【０１３９】
関数は、整数変数ｉがｒ以上となると（Ｓ１３５；ＮＯ）、テンプレート配列Ｓのｋｒ−１番目の要素であるリスト構造Ｓ［ｋｒ−１］に整数配列Ａを追加する（Ｓ１３７）。関数は、集合Ｃに未処理の組がなくなるまで、上述のような処理を繰り返す（Ｓ１３８）。【０１４０】
図１４には、関数ｐａｒｔｉｔｉｏｎ＿ｔｅｍｐの処理フローが示されている。関数ｐａｒｔｉｔｉｏｎ＿ｔｅｍｐは、文字列ｓｔｒ、接尾辞ｓｕｆｆｉｘ、分割パラメータｑ、閾値τ及びテンプレート配列Ｓを引数として受け取ると、整数変数ｉをｑ＋１で初期化した後（Ｓ１４１）、テンプレート配列Ｓのｉ番目の要素であるリストＳ［ｉ］から、未処理の整数配列Ａを取得する（Ｓ１４２）。以下の説明では、関数ｐａｒｔｉｔｉｏｎ＿ｔｅｍｐを省略して単に関数と表記する。【０１４１】
続いて、関数は、ｓｅｑを空文字列で、ｒを（ｑ−１）で、ｈを（ｉ−１）でそれぞれ初期化する（Ｓ１４３）。関数は、更に文字列変数ｔｍｐに特殊文字「＊」を代入する（Ｓ１４４）。【０１４２】
関数は、ｓｔｒの文字列長がｈ以上の場合（Ｓ１４５；ＮＯ）、例外処理を行う必要がないため、文字列変数ｔｍｐにｓｔｒのｈ番目の要素文字ｓｔｒ［ｈ］を代入した上で（Ｓ１４６）、ｓｅｑにｔｍｐとｓｅｑを連結した文字列を代入する（Ｓ１４７）。一方、ｓｔｒの文字列長がｈ未満の場合（Ｓ１４５；ＹＥＳ）、関数は、例外処理として、そのままｓｅｑにｔｍｐとｓｅｑを連結した文字列を代入する（Ｓ１４７）。【０１４３】
ｒが０より大きい場合（Ｓ１４８；ＹＥＳ）、関数は、ｈに（ｈ−（Ａ［ｒ］＋１））を代入し（Ｓ１４９）、ｒから１を減算した後（Ｓ１５０）、処理（Ｓ１４４）に戻る。一方で、ｒが０以下の場合（Ｓ１４８；ＮＯ）、関数は、ＳＩＰタプル＜ｓｕｆｆｉｘ、Ａ、ｐ＞をラベルｓｅｑのバケットに挿入する（Ｓ１５１）。【０１４４】
関数は、このような処理をテンプレート配列Ｓのｉ番目の要素であるリストＳ［ｉ］に未処理の整数配列Ａが存在しなくなるまで繰り返す（Ｓ１５２；ＹＥＳ）。【０１４５】
未処理の整数配列Ａが存在しなくなると（Ｓ１５２；ＮＯ）、関数は、ｉが（ｑ＋τ）以下であるか否かを判定する（Ｓ１５３）。関数は、ｉが（ｑ＋τ）以下である場合（Ｓ１５３；ＹＥＳ）、ｓｔｒの位置２から末尾までの接尾辞を新たに取得し、その接尾辞をｓｕｆｆｉｘに代入し、整数変数ｉに１を加算した後（Ｓ１５４）、処理（Ｓ１４２）に戻る。一方、関数は、ｉが（ｑ＋τ）より大きい場合（Ｓ１５３；ＮＯ）、処理を終了する。【０１４６】
図１５は、上述のような当てはめ法を用いたＳＩＰタプル生成の例を示す図である。図１５には、分割パラメータｑが２であり、閾値τが２である場合のＳＩＰタプル生成例が示される。当てはめ法は、始めにテンプレート配列Ｓを生成することにより、可能なあらゆる整数配列（文字配置配列）Ａを生成する。図１５の例では、テンプレート配列Ｓの生成後、タプル「ＤＡＬＩ」及び「ＭＡＮＥＴ」に対して、そのテンプレート配列Ｓを適用することにより、各ＳＩＰタプルが生成される。【０１４７】
結合処理部３２及び推定値算出部３３の処理は、図８の処理（Ｓ８６及びＳ８７）に相当する。この処理について、ここでは、ネステッドループ結合法及びトライ結合法と呼ぶことができる２種類の実施例を説明する。処理対象のデータの規模、閾値τ、分割パラメータｑ等により、これら２種類の実施例には適否がある。【０１４８】
図１６、図１７及び図１８はネステッドループ結合法の動作を示すフローチャートである。図１６に示されるように、結合処理部３２は、局所結果集合Ｒを初期化した後（Ｓ１６１）、ＳＩＰタプル格納部３５から未処理のバケットＢを取得する（Ｓ１６２）。続いて、結合処理部３２は、未処理のバケットＢ、分割パラメタｑ、閾値τ、局所結果集合Ｒを引数とし、関数ｎｅｓｔｅｄ＿ｌｏｏｐ＿ｊｏｉｎを呼び出す（Ｓ１６３）。結合処理部３２は、このような処理を、未処理のバケットＢが存在しなくなるまで繰り返す（Ｓ１６４）。【０１４９】
図１７には、関数ｎｅｓｔｅｄ＿ｌｏｏｐ＿ｊｏｉｎの処理フローが示されている。関数ｎｅｓｔｅｄ＿ｌｏｏｐ＿ｊｏｉｎは、未処理のバケット（ＳＩＰタプル集合）Ｂ、分割パラメータｑ、閾値τ、局所結果集合Ｒを引数として受け取ると、まず、バケットＢから未処理のＳＩＰタプルｔ１（＝＜ｓｕｆｆｉｘ１、Ａ１、ｐ１＞）を取得する（Ｓ１７１）。ｐ１は、元のタプルが属する入力データを特定するためのデータ識別子（ｄｂ１）と、その入力データの中で元のタプルを特定するためのタプル識別子（ｉｄ１）とを含むタプルポインタであり、ここでは、「ｄｂ１：ｉｄ１」と表記される。また、以下の説明では、関数ｎｅｓｔｅｄ＿ｌｏｏｐ＿ｊｏｉｎを省略して単に関数と表記する。【０１５０】
関数は、バケットＢから上記ＳＩＰタプルｔ１に対して未処理のＳＩＰタプルｔ２（＝＜ｓｕｆｆｉｘ２、Ａ２、ｐ２＞）を取得する（Ｓ１７２）。ここで、ｐ２は「ｄｂ２：ｉｄ２」である。関数は、更に、整数変数ｉ及びｍを０でそれぞれ初期化した後（Ｓ１７３）、整数変数ｍに（ｍ＋ｍａｘ（Ａ１［ｉ］、Ａ２［ｉ］））の値を代入する（Ｓ１７４）。ここで、ｍａｘ関数は与えられた２つの整数変数のうち、大きなほうの値を返す関数である。【０１５１】
ｍがτ以下である場合（Ｓ１７５；ＹＥＳ）、関数は、ｉに１を加算しながら（Ｓ１７６）、ｉがｑ以上となるまで、処理（Ｓ１７４）を繰り返す（Ｓ１７４、Ｓ１７５；ＹＥＳ、Ｓ１７６、Ｓ１７７；ＹＥＳ）。【０１５２】
ｍがτ以下であり、かつ、ｉがｑ以上となると（Ｓ１７７；ＮＯ）、関数は、ｓｕｆｆｉｘ１とｓｕｆｆｉｘ２との間の編集距離ｓｅｄを、関数ｅｄを用いて算出する（Ｓ１７８）。関数ｅｄ内の処理には周知な手法が利用されればよいため、ここでは説明を省略する。【０１５３】
続いて、関数は、ｍとｓｅｄとを加算することにより局所編集距離を算出し、その局所編集距離（ｍ＋ｓｅｄ）が閾値τ以下であるか否かを評価する（Ｓ１７９）。関数は、局所編集距離が閾値τ以下であれば（Ｓ１７９；ＹＥＳ）、関数ｉｎｓｅｒｔＭｉｎを呼び出す（Ｓ１８０）。これにより、局所結果タプル＜＜ｐ１、ｐ２＞、ｍ＋ｓｅｄ＞が局所結果集合Ｒに追加される。一方、局所編集距離（ｍ＋ｓｅｄ）が閾値τより大きい場合（Ｓ１７９；ＮＯ）、その局所結果タプルが集合Ｒに追加されない。【０１５４】
関数は、バケットＢに、データ識別子ｄｂ２を持つ他の未処理ＳＩＰタプルの存在を確認し（Ｓ１８１）、他の未処理ＳＩＰタプルが存在する場合（Ｓ１８１；ＹＥＳ）、処理（Ｓ１７２）以降を繰り返す。他の未処理ＳＩＰタプルが存在しない場合（Ｓ１８１；ＮＯ）、関数は、バケットＢに、データ識別子ｄｂ１を持つ未処理のＳＩＰタプルの存在を確認する（Ｓ１８２）。関数は、他の未処理ＳＩＰタプルが存在する場合（Ｓ１８２；ＹＥＳ）、処理（Ｓ１７１）以降を繰り返す。関数は、他の未処理ＳＩＰタプルが存在しなくなると（Ｓ１８２；ＮＯ）、処理を終了する。【０１５５】
図１８には、関数ｉｎｓｅｒｔＭｉｎの処理フローが示されている。関数ｉｎｓｅｒｔＭｉｎは、ペア＜ｘ、ｉ＞とリスト構造ｌｉｓｔとを引数として受け取る。ここで、ｘは任意の変数、ｉは整数変数とする。本関数は、まず、ｌｉｓｔの中に、ｘを含む要素＜ｘ、ｊ＞が存在するかどうかを確認する（Ｓ１８６）。関数は、要素＜ｘ、ｊ＞が存在する場合（Ｓ１８６；ＹＥＳ）、ｉがｊより小さいかどうかを評価する（Ｓ１８７）。ｉがｊより小さい場合、関数は、既存の要素＜ｘ、ｊ＞をｌｉｓｔから削除し（Ｓ１８８）、ｌｉｓｔに＜ｘ、ｉ＞を挿入する（Ｓ１８９）。ｉがｊ以上である場合（Ｓ１８７；ＹＥＳ）、関数は、特に処理をしない。また、ｌｉｓｔにｘを含む要素＜ｘ、ｊ＞が存在しない場合（Ｓ１８６；ＮＯ）、関数は、要素＜ｘ、ｉ＞をｌｉｓｔに挿入し（Ｓ１８９）、処理を終える。【０１５６】
図１９、図２０、図２１、図２３、図２４及び図２５は、トライ結合法の動作を示すフローチャートである。図１９に示されるように、トライ結合法では、結合処理部３２は、局所結果集合Ｒの初期化（Ｓ１９１）及び未処理バケットＢの取得（Ｓ１９２）の後、取得された未処理バケットＢに対して木構造Ｔを初期化する（Ｓ１９３）。続いて、結合処理部３２は、バケットＢに含まれているＳＩＰタプルを木構造Ｔに挿入する関数ｆｏｒｅｓｔ＿ｂｕｉｌｄを呼び出すことにより、木構造Ｔを生成する（Ｓ１９４）。【０１５７】
結合処理部３２は、生成された木構造Ｔ、分割パラメータｑ、閾値τ及び局所結果集合Ｒを引数として、関数ｆｏｒｅｓｔ＿ｊｏｉｎを呼び出すことにより、バケットＢに含まれるＳＩＰタプルのペアの編集距離を算出する（Ｓ１９５）。結合処理部３２は、このような処理を、未処理のバケットＢが存在しなくなるまで繰り返す（Ｓ１９６）。【０１５８】
図２０には、関数ｆｏｒｅｓｔ＿ｂｕｉｌｄの処理フローが示されている。関数ｆｏｒｅｓｔ＿ｂｕｉｌｄは、バケットＢ及び初期化された木構造Ｔを引数として受け取ると、Ｔの根（ルート）ノードｎｄを取得する（Ｓ２００）。以下の説明では、関数ｆｏｒｅｓｔ＿ｂｕｉｌｄを省略して単に関数と表記する。【０１５９】
続いて、関数は、バケットＢから未処理のＳＩＰタプル＜ｓｕｆ、Ａ、ｄｂ：ｉｄ＞を取得した後（Ｓ２０１）、配列Ａ、ノードｎｄ及びデータ識別子ｄｂを引数として関数ｉｎｓｅｒｔを呼び出す（Ｓ２０２）。この関数ｉｎｓｅｒｔにより、ノードｎｄ以下の部分木に配列Ａが挿入される。関数は、関数ｉｎｓｅｒｔの返り値であるノードをｎｄに代入する（Ｓ２０２）。関数ｉｎｓｅｒｔの返り値となるノードは、配列Ａの末尾の値をラベルに持つノードである。【０１６０】
更に、関数は、文字列配列ｓｕｆと配列Ａの末尾の値をラベルに持つノードｎｄとデータ識別子ｄｂとを引数として関数ｉｎｓｅｒｔを呼び出し、関数ｉｎｓｅｒｔの返り値をｎｄに代入する（Ｓ２０３）。この場合、関数ｉｎｓｅｒｔは、ｎｄ以下の部分木に配列ｓｕｆを挿入する。このときの返り値は、ｓｕｆの末尾文字をラベルに持つノードである。【０１６１】
関数は、このように取得されたノードｎｄに、ＳＩＰタプルのポインタ属性値ｄｂ：ｉｄを登録する（Ｓ２０４）。関数は、このような処理を、バケットＢに未処理のＳＩＰタプルが存在しなくなるまで繰り返す（Ｓ２０５）。【０１６２】
図２１には、関数ｉｎｓｅｒｔの処理フローが示されている。関数ｉｎｓｅｒｔは、配列変数ａｒｒａｙとノードｎｄとデータ識別子ｄｂとを引数として受け取ると、配列変数ａｒｒａｙのサイズｓｉｚｅを取得し（Ｓ２１０）、整数変数ｉを０で初期化する（Ｓ２１１）。以降、関数ｉｎｓｅｒｔを省略して単に関数と表記する。【０１６３】
関数は、ａｒｒａｙのｉ番目の要素であるａｒｒａｙ［ｉ］をラベルに持つノードｃがｎｄの子として存在するか否かを評価する（Ｓ２１２）。存在しない場合（Ｓ２１２；ＮＯ）、関数は、要素ａｒｒａｙ［ｉ］をラベルに持つノードｃを生成し、そのノードｃをｎｄの子として設定する（Ｓ２１３）。ノードｃがｎｄの子として存在する場合には（Ｓ２１２；ＹＥＳ）、関数は、処理（Ｓ２１３）を行うことなく、ｎｄにｃを代入する（Ｓ２１４）。その後、関数は、ｉに１を加算し、ｉがｓｉｚｅ以上となるまで、上述の処理を繰り返す（Ｓ２１７；ＹＥＳ）。【０１６４】
ｉがｓｉｚｅ以上となる（Ｓ２１７；ＮＯ）、即ち、処理すべきａｒｒａｙ［ｉ］が存在しなくなると、関数は、ｎｄを返り値として返す（Ｓ２１８）。このとき、ｎｄはａｒｒａｙの末尾の要素をラベルとして持つ、深さｉのノードとなる。なお、根ノードの深さは０とされる。【０１６５】
図２２は、上述のようなトライ結合法により構築される木構造の例を示す図である。図２２の例では、ラベルＣｅが付されたバケットＢに関し構築される木構造が示されている。木構造の上部において矩形のノードにより構成される木は、整数配列（文字配置配列）Ａの情報を格納するトライであり、木構造の下部の丸型のノードにより構成される木は、末尾部分文字列（接尾辞）を表すトライである。実線で示されるノードは、ポインタにデータ識別子Ａがついているタプルに対応するノードを示し、破線で示されるノードは、Ｂがついているタプルに対応するノードを示し、２重線で示されるノードは、両方のタプルに対応するノードを示す。また、丸型ノードの右上に付与された番号は、説明の便宜上のノード番号である。丸型ノードのラベル文字の下線は、タプルのポインタが登録されたノードであることを示している。【０１６６】
図２３には、関数ｆｏｒｅｓｔ＿ｊｏｉｎの処理フローが示されている。関数ｆｏｒｅｓｔ＿ｊｏｉｎは、木構造Ｔ、分割パラメータｑ、閾値τ及び局所結果集合Ｒを引数として受け取ると、以下に示す処理により、Ｔに登録されたＳＩＰタプルの任意のペアの中から局所編集距離がτ以下となるＳＩＰタプルのペアをＲに登録する。以下の説明では、関数ｆｏｒｅｓｔ＿ｊｏｉｎを省略して単に関数と表記する。【０１６７】
関数は、まず、木構造Ｔの根（ルート）ノードｎｄを取得し（Ｓ２３０）、ｎｄの子ノードｃと値０とから形成される全てのペア＜ｃ、０＞を生成して、集合（リスト構造）ａｌに挿入する（Ｓ２３１）。【０１６８】
続いて、関数は、未処理のｎｄの子ノードｃを取得し（Ｓ２３２）、関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓを呼び出す（Ｓ２３３）。これにより、子ノードｃの子孫となる接尾辞根ノードのアクティブリストが生成される。接尾辞根ノードとは、木構造Ｔにおいて、深さｑ＋１に位置し、初めてラベルが整数値でなく空白文字となっているノードを意味する。また、ノードｘのアクティブリストとは、或る文字列の接頭辞（先頭部分文字列）に対応するｘとの間の局所編集距離の値がτ以下の関係にある、別の文字列の接頭辞に対応するノードの集合である。関数は、このような処理を、未処理のｎｄの子ノードが存在しなくなるまで繰り返す（Ｓ２３４）。【０１６９】
その後、関数は、木構造Ｔから未処理の接尾辞根ノードｒｎｄを取得し（Ｓ２３５）、処理（Ｓ２３３）で生成されたｒｎｄのアクティブリストを取得し、このアクティブリストをａｌに代入する（Ｓ２３６）。更に、関数は、未処理のｒｎｄの子ノードｎｄを取得し（Ｓ２３７）、関数ａｃｔｉｖｅｌｉｓｔを呼び出す（Ｓ２３８）。これにより、ｎｄのアクティブリストが再帰的に生成される。関数は、処理（Ｓ２３７及びＳ２３８）を、ｒｎｄの未処理の子ノードが存在しなくなるまで繰り返す（Ｓ２３９）。そして、関数は、処理（Ｓ２３５）から処理（Ｓ２３８）を、未処理の接尾辞根ノードが存在しなくなるまで繰り返す（Ｓ２４０）。【０１７０】
図２４には、関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓの処理フローが示されている。関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓは、アクティブリストａｌ、ノードｃ、分割パラメータｑ、閾値τ、及び局所結果集合Ｒを引数として受け取り、以下の処理により、ノードｃのアクティブリストを生成する。以下、関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓを省略して関数と表記する。【０１７１】
関数は、まず、ノードｃのラベル数値ｉを取得し（Ｓ２４１）、ノードｃのアクティブリストａｌｃを初期化する（Ｓ２４２）。続いて、関数は、アクティブリストａｌから未処理の要素＜ｎｄ、ｌｅｄ＞を取得し（Ｓ２４３）、ｎｄのラベル数値ｊを取得する（Ｓ２４４）。関数は、ｌｅｄに（ｌｅｄ＋ｍａｘ（ｉ、ｊ））の値を代入し、それがτ以下なら、ａｌｃに＜ｎｄ、ｌｅｄ＞を追加する（Ｓ２４５）。関数は、アクティブリストａｌに未処理の要素が存在しなくなるまで処理（Ｓ２４３、Ｓ２４４及びＳ２４５）を繰り返す（Ｓ２４６）。【０１７２】
その後、関数は、ｑ−１が０より大きい場合（Ｓ２４７；ＹＥＳ）、ノードｃの子ノードｃｃは接尾辞根ノードではないため、ノードｃの未処理の子ノードｃｃを取得する（Ｓ２４８）。そして、関数は、自身（関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓ）を再帰的に呼び出す（Ｓ２４９）。関数は、このような処理（Ｓ２４８及びＳ２４９）を未処理のノードｃの子ノードが存在しなくなるまで繰り返す（Ｓ２５０）。【０１７３】
ｑ−１が０以下の場合（Ｓ２４７；ＮＯ）、ノードｃの子ノードｃｃは接尾辞根ノードであるため、関数は、ａｌｃを子ノードｃｃのアクティブリストとして保持する（Ｓ２５１）。更に、関数は、ｃｃにポインタｐ１が登録されている場合、ａｌｃの要素＜ａｎ、ｅｄ＞の中で、ａｎにポインタｐ２が登録されているものを探し、関数ｉｎｓｅｒｔＭｉｎを呼び出して、局所結果タプル＜＜ｐ１、ｐ２＞、ｅｄ＞をＲに登録する（Ｓ２５２）。【０１７４】
図２５には、関数ａｃｔｉｖｅｌｉｓｔの処理フローが示されている。関数ａｃｔｉｖｅｌｉｓｔは、アクティブリストａｌ、ノードｎｄ、閾値τ及び局所結果集合Ｒを引数として受け取り、以下の処理により、ノードｎｄ以下の部分木を構成する各ノードのアクティブリストを再帰的に計算していく。以下、関数ａｃｔｉｖｅｌｉｓｔを省略して関数と表記する。【０１７５】
関数は、ｎｄのアクティブリストａｌｎｄを初期化した後（Ｓ２６０）、アクティブリストａｌから未処理の要素＜ａｎ、ｌｅｄ＞を取得する（Ｓ２６１）。続いて、関数は、ｌｅｄ＋１がτ以下ならば関数ｉｎｓｅｒｔＭｉｎを呼び出す（Ｓ２６２）。これにより、要素＜ａｎ、（ｌｅｄ＋１）＞がアクティブリストａｌｎｄに登録される。【０１７６】
次に、関数は、ａｎの未処理の子ノードｃａｎを取得し（Ｓ２６３）、更に、ｎｄのラベル文字とｃａｎのラベル文字とが一致していれば、θに０を代入、一致していなければθに１を代入する（Ｓ２６４）。更に、関数は、（ｌｅｄ２＋１）及び（ｌｅｄ＋θ）の小さいほうの値をｌｅｄ３に代入する（Ｓ２６５）。続いて、関数は、ｌｅｄ３がτ以下であるなら、＜ａｎ、ｌｅｄ３＞をａｌｎｄに登録するために、関数ｉｎｓｅｒｔＭｉｎを呼び出す（Ｓ２６６）。【０１７７】
関数は、上記処理（Ｓ２６３）から処理（Ｓ２６６）を、ａｎに未処理の子ノードが存在しなくなるまで繰り返す（Ｓ２６７）。更に、関数は、上記処理（Ｓ２６１）から処理（Ｓ２６６）を、ａｌに未処理の要素が存在しなくなるまで繰り返す（Ｓ２６８）。【０１７８】
その後、関数は、ｎｄにポインタｐ１が登録されていれば、ａｌｎｄの要素＜ａｎ、ｅｄ＞の中でａｎにポインタｐ２が登録されているものを探して、関数ｉｎｓｅｒｔＭｉｎを呼び出す（Ｓ２６９）。これにより、局所結果タプル＜＜ｐ１、ｐ２＞、ｅｄ＞が局所結果集合Ｒに挿入される。【０１７９】
続いて、関数は、ｎｄの未処理の子ノードｃを取得した後（Ｓ２７０）、ｃのアクティブリストをｎｄのアクティブリストａｌｎｄを用いて算出するために、関数ａｃｔｉｖｅｌｉｓｔを再帰的に呼び出す（Ｓ２７１）。関数は、処理（Ｓ２７０）及び処理（Ｓ２７１）をｎｄの子ノードが存在しなくなるまで繰り返す（Ｓ２７２）。【０１８０】
図２６は、アクティブリストの生成例を示す図である。ノード番号は、図２２に示される木構造における接頭辞トライの各ノードの右上に付与された便宜上の番号に対応している。ノード番号＃０及び＃４のアクティブリストは、関数ａｃｔｉｖｅｌｉｓｔ＿ｒｏｏｔｓが呼び出されることにより生成される。更にその後、関数ａｃｔｉｖｅｌｉｓｔが、ノード番号＃０及び＃４の下の部分木を構成するノードのアクティブリストを順次計算する。この例では、ノード番号＃５及び＃６のアクティブリストが生成される。【０１８１】
結果生成部１２の処理は、図８の処理（Ｓ８８）に相当する。図２７は、結果生成部１２の処理の具体例を示すフローチャートである。【０１８２】
結果生成部１２は、結合結果集合Ｒを初期化した後（Ｓ２８１）、局所結果集合Ｌを取得する（Ｓ２８２）。局所結果集合Ｌは、例えば、各結合処理装置３０から送られる局所結合結果の集合である。結果生成部１２は、取得された局所結果集合Ｌから未処理の要素（局所結果タプル）を取得し（Ｓ２８３）、その要素及び結合結果集合Ｒを引数にして、関数ｉｎｓｅｒｔＭｉｎを呼び出す（Ｓ２８４）。これにより、結合結果集合Ｒに局所結果タプルが格納される。結果生成部１２は、未処理の要素がなくなるまで、処理（Ｓ２８３）及び処理（Ｓ２８４）を繰り返す（Ｓ２８５）。【０１８３】
［第４実施形態］
上述の各実施形態では、分割パラメータｑの値の決め方については特に言及されていなかった。分割パラメータｑの値は、バケットの数、及び、文字列類似結合処理全体の処理時間に影響を与える。よって、分割パラメータｑは、バケット数や処理時間を考慮して適切な値に設定されることが望ましい。しかしながら、分割パラメータｑの最適値は、類似結合処理の対象となるデータによっても変わるため、それを人的に決定するには多大な労力を要する。【０１８４】
そこで、第４実施形態におけるシステム１は、文字列類似結合処理全体の処理時間を最小にする適切な分割パラメータｑを自動で決定する。以下、第４実施形態におけるシステム１について、上述の第３実施形態と異なる内容を中心に説明し、同様の内容については適宜省略する。【０１８５】
図２８は、第４実施形態におけるシステムの構成例を概念的に示す図である。第４実施形態におけるシステム１は、第３実施形態の構成に加えて、パラメータ推定装置４０を更に有する。なお、第４実施形態で新たに組み込まれる構成は、第３実施形態のみでなく、第１実施形態や第２実施形態に組み込まれてもよい。【０１８６】
システム制御装置１０は、類似結合処理の要求を受け、この要求に応じた類似結合処理を実行するために、データ管理装置２０及び結合処理装置３０に加え、パラメータ推定装置４０を更に制御する。【０１８７】
パラメータ推定装置４０は、データ管理装置２０で管理されている類似結合処理対象となるデータ（タプルの集合）と編集距離閾値τに対して、システム１における類似結合処理全体の処理時間を最小とし得る分割パラメータｑを推定する。パラメータ推定装置４０は、分割パラメータｑに対して類似結合処理全体の処理時間モデル（以降、単に処理時間モデルと表記する）を構築し、この処理時間モデルを最適化することにより分割パラメータｑの最適値を推定する。【０１８８】
〔装置構成〕
システム制御装置１０の構成は、第３実施形態と同じであるが、要求制御部１１がパラメータ推定装置４０と通信する点において第３実施形態と異なる。具体的には、要求制御部１１は、取得された文字列類似結合の処理要求の内容に基づきパラメータ推定命令を生成し、そのパラメータ推定命令を入出力Ｉ／Ｆ４の通信インタフェースを介してパラメータ推定装置４０へ送信する。第４実施形態では、要求制御部１１により取得される処理要求には、分割パラメータｑが含まれていなくともよい。【０１８９】
上記パラメータ推定命令に応じて、要求制御部１１は、パラメータ推定装置４０から分割パラメータｑを受信する。以降、要求制御部１１は、第３実施形態と同様に、実行命令をデータ管理装置２０及び結合処理装置３０へ送信する。当該実行命令には、処理対象となるデータを特定するためのデータ識別子と、その対象データの結合キー属性の情報と、編集距離閾値τと、パラメータ推定装置４０から受信された分割パラメータｑが含まれる。【０１９０】
図２９は、パラメータ推定装置４０の構成例を概念的に示すブロック図である。パラメータ推定装置４０は、図２９に示されるように、データ分析部４１、最適化部４２、モデル構築部４３、モデル構成要素格納部４４等を有する。データ分析部４１、最適化部４２及びモデル構築部４３は、例えば、ＣＰＵ２によりメモリ３に格納されるプログラムが実行されることで実現される。また、モデル構成要素格納部４４は、例えば、メモリ３上に実現される。【０１９１】
最適化部４２は、システム制御装置１０からパラメータ推定命令を取得すると、データ分析部４１及びモデル構築部４３に推定実行命令を送る。最適化部４２は、後述するモデル構築部４３により生成された処理時間モデルを受け取ると、処理時間モデルから分割パラメータｑを決定し、決定された分割パラメータｑをシステム制御装置１０へ送信する。なお、最適化部４２の具体的処理については動作例の項において述べる。【０１９２】
データ分析部４１は、最適化部４２から推定実行命令を受け取ると、その命令に含まれるデータ識別子に基づいてデータ管理装置２０により管理される類似結合処理対象のデータ（タプル集合）を特定し、その特定されたタプル集合の結合キー文字列から、処理時間モデルの構築のために利用される要約情報を生成し、この要約情報をモデル構成要素格納部４４に格納する。以降、当該類似結合処理対象のデータ（タプル集合）を処理対象データと表記し、その処理対象データの結合キー文字列を処理対象文字列と表記する場合もある。【０１９３】
モデル構成要素格納部４４は、データ分析部４１により生成された要約情報を格納する。この要約情報には、具体的には、当該処理対象文字列の総数、当該処理対象文字列に出現するユニークな各文字（空文字を除く）の出現頻度分布、当該処理対象文字列が所持する各文字列長の出現頻度分布、及び、当該処理対象文字列の中の最長の文字列長、処理時間モデルの構築のための係数等が含まれる。【０１９４】
モデル構築部４３は、モデル構成要素格納部４４に格納されている要約情報を用いて、分割パラメータｑに対する処理時間モデルを構築する。なお、モデル構築部４３による具体的な処理時間モデルの構築処理については動作例の項において述べる。【０１９５】
〔動作例〕
図３０は、第４実施形態におけるシステム１の全体的な動作の概要を示すフローチャートである。なお、図３０では、図８に示される第３実施形態と同一の処理ステップについては図８と同じ符号が付されている。【０１９６】
まず、システム制御装置１０において、要求制御部１１が文字列類似結合の処理要求を取得する（Ｓ３０１）。この処理要求には、第３実施形態と異なり、分割パラメータｑは含まれなくてもよい。要求制御部１１は、取得された処理要求の内容に基づいてパラメータ推定命令を生成し、そのパラメータ推定命令をパラメータ推定装置４０に送る。【０１９７】
パラメータ推定装置４０は、そのパラメータ推定命令を受信すると、データ分析部４１が、データ管理装置２０における、データ識別子で特定される処理対象データの処理対象文字列を分析し、分析結果として要約情報を生成する（Ｓ３０２）。【０１９８】
続いて、モデル構築部４３が、生成された要約情報を用いて分割パラメータｑに対する処理時間モデルＴ（ｑ）を構築する（Ｓ３０３）。【０１９９】
次に、最適化部４２が、構築された処理時間モデルＴ（ｑ）を用いて、文字列類似結合全体の処理時間を最小にする分割パラメータｑを推定する（Ｓ３０４）。以降、処理（Ｓ３０１）で取得されたデータ識別子、結合キー属性情報及び編集距離閾値τ、並びに、処理（Ｓ３０４）で推定された分割パラメータｑが用いられることにより、第３実施形態と同様の処理が実行される（Ｓ８２からＳ８８）。【０２００】
図３１は、モデル構築部４３の動作例を示すフローチャートである。以降、データ分析部４１により生成された要約情報に含まれる各情報を次のように示すものとする。処理対象文字列の総数がＮで示され、当該処理対象文字列に出現するユニークな各文字の出現頻度分布がｚで示され、当該処理対象文字列が所持する各文字列長の出現頻度分布がｂｉｎで示され、当該処理対象文字列の中の最長の文字列長がｌｍａｘで示され、処理時間モデルの構築のための係数がｃ１、ｃ２及びｃ３で示される。【０２０１】
モデル構築部４３は、まず、バケット分割に掛かる処理時間Ｔｐ（ｑ）を推定する（Ｓ３１１）。バケット分割とは、各ＳＩＰタプルを各バケットにそれぞれ振り分ける処理を意味する。処理時間Ｔｐ（ｑ）は、具体的には、以下の（式１）で示される関数により算出される。
【数１】
2013031117.tif 000003
Ｎｑ≡τ＋ｑＣｑ×Ｎ【０２０２】
上記（式１）において、Ｎｑはバケット分割処理の計算量に相当する。上述するように、バケット分割は、各処理対象データに含まれる各処理対象文字列からτ＋ｑＣｑ個のｑコンビネーションを生成し、それらを対応するバケットに振り分ける処理である。よって、バケット分割処理の計算量はＮｑ≡τ＋ｑＣｑ×Ｎに比例する。【０２０３】
続いて、モデル構築部４３は、類似結合に掛かる処理時間Ｔｊ（ｑ）を推定する（Ｓ３１２）。処理時間Ｔｊ（ｑ）は、具体的には、以下の（式２）で示される関数により算出される。ここで、Ｆｓ（ｑ）は、分割パラメータｑを用いた或るバケットにおける類似結合処理の計算量を返す任意の関数を示し、Ｓｌは、処理対象文字列から生成される長さが｜ｓ｜＝ｌのあらゆるｑコンビネーションｓの集合を示す。なお、特殊文字「＊」は長さ｜ｓ｜にカウントされないものとする。
【数２】
2013031117.tif 000004
【０２０４】
上記（式２）における係数以外の部分によれば、全てのバケットで発生する類似結合処理の計算量の和が算出される。類似結合処理の計算量は、適用する類似結合処理のアルゴリズムによって異なるため、上記（式２）では任意のアルゴリズムの計算量を表せるよう関数Ｆｓ（ｑ）で示される。なお、類似結合処理の計算量の具体的算出手法については、後述の実施例の項において述べる。【０２０５】
次に、モデル構築部４３は、各結合処理装置３０により生成された局所結合結果を整理するのに掛かる処理時間Ｔａ（ｑ）を推定する（Ｓ３１３）。局所結合結果の整理とは、具体的には、同じタプルポインタのペアを含む局所結果タプルのうち最小の局所編集距離を持つもの以外を排除する処理を意味する。処理時間Ｔａ（ｑ）は、具体的には、以下の（式３）で示される関数により算出される。
【数３】
2013031117.tif 000005
【０２０６】
局所結合結果の中には、各タプルペアに対して最悪でτ＋ｑＣｑ個の重複が発生しているため、上記（式３）に示されるように、局所結合結果を整理するのに掛かる時間は、Ｎｑ≡τ＋ｑＣｑ×Ｎに比例すると考えられる。【０２０７】
最後に、モデル構築部４３は、上述のように推定された各処理時間を合計することにより、処理時間モデルＴ（ｑ）を構築する（Ｓ３１４）。処理時間モデルＴ（ｑ）は、以下の（式４）で示される。
【数４】
2013031117.tif 000006
【０２０８】
図３２は、最適化部４２の動作例を示すフローチャートである。
最適化部４２は、まず、変数ｑに初期値として１を代入する（Ｓ３２１）。その上で、最適化部４２は、上述のようにモデル構築部４３により構築された処理時間モデルＴ（ｑ）を用いて、Ｔ（ｑ＋１）とＴ（ｑ）との差が０以下であるか否かを判定する（Ｓ３２２）。このとき、Ｔ（２）からＴ（１）を減算した値が０以下であるか否かが判定される。【０２０９】
最適化部４２は、当該差分が０以下である場合（Ｓ３２２；ＹＥＳ）、変数ｑの値が最小の処理時間を実現する値ではないため、変数ｑに１を加算する（Ｓ３２３）。そして、最適化部４２は、再度、Ｔ（ｑ＋１）とＴ（ｑ）の差が０以下であるか否かを判定する（Ｓ３２２）。最適化部４２は、当該差分が０より大きくなる（Ｓ３２２；ＮＯ）、又は、変数ｑの値が当該結合対象文字列における最長の文字列の長さｌｍａｘを超える（Ｓ３２４；ＹＥＳ）まで、上述の処理を繰り返す。【０２１０】
最適化部４２は、当該差分が０より大きい場合（Ｓ３２２；ＮＯ）、又は、変数ｑの値が当該結合対象文字列における最長の文字列長ｌｍａｘを超える場合（Ｓ３２４；ＹＥＳ）、そのときの変数ｑの値が最小の処理時間を実現する値と判断し、その値を分割パラメータｑの値として決定する（Ｓ３２５）。【０２１１】
モデル構築部４３により構築される処理時間モデル式は、二次関数によく似た形をしているため、一般的には１以上ｌｍａｘ以内の範囲に最適値が存在する。なお、パラメータ推定装置４０により決定された分割パラメータｑの値が１となった場合、分割パラメータｑが１である場合の類似結合処理を実施する代替システムにその類似結合処理を実行させてもよい。【０２１２】
〔第４実施形態における作用及び効果〕
上述のように、第４実施形態では、類似結合処理対象となるタプル集合の結合キー文字列（処理対象文字列）についての要約情報が生成され、この要約情報に基づいて、本システム１で実行される文字列類似結合処理の全体の処理時間モデルが構築される。具体的には、データ管理装置２０で実行されるバケット分割処理に掛かる時間Ｔｐ（ｑ）、結合処理装置３０で実行される類似結合処理に掛かる時間Ｔｊ（ｑ）、及び、システム制御装置１０で実行される局所結合結果の整合処理に掛かる時間Ｔａ（ｑ）が、当該要約情報や利用されるアルゴリズム等からそれぞれ推定され、それらの時間の合計から処理時間モデルＴ（ｑ）が構築される。そして、その処理時間モデルＴ（ｑ）を最小とする分割パラメータｑが最適値として決定され、このように最適化された分割パラメータｑを用いて、実際に、本システム１における文字列類似結合処理が実行される。【０２１３】
従って、第４実施形態によれば、全体の処理時間を最小とする分割パラメータｑが自動で決定されるため、理論的に最速に近い実行時間で文字列類似結合処理を実行することができる。これに伴い、分割パラメータｑを決める労力をなくすことができる。
【実施例２】
【０２１４】
以下、上述の第４実施形態におけるシステム１に関し、特に、パラメータ推定装置４０のより具体的な例を説明する。もちろん、パラメータ推定装置４０は以下の実施例に限定されない。本実施例では、結合処理アルゴリズムとしてネステッドループが利用される例を挙げ、更に、説明の便宜のために、結合処理装置３０が１台であり、この結合処理装置３０が全てのバケットの結合処理を逐次実行する例を挙げる。【０２１５】
上述したように、データ分析部４１により生成された要約情報には、処理対象文字列の総数Ｎ、各文字の出現頻度分布ｚ、各文字列長の出現頻度分布ｂｉｎ、最長の文字列長ｌｍａｘ、係数ｃ１、ｃ２及びｃ３が含まれる。データ分析部４１は、処理対象文字列の数をカウントすることにより総数Ｎを得る。更に、データ分析部４１は、当該処理対象文字列から最長の文字列を見つけ出すことにより長さｌｍａｘを得る。【０２１６】
データ分析部４１は、各文字の出現頻度分布ｚを関数ｚ（ｒ）として得る。ｒは、各文字の出現頻度を高い順に並べた場合の高い方からの順位を示す変数である。即ち、関数ｚ（ｒ）は、出現頻度の順位ｒに対してその出現頻度を出力する。データ分析部４１は、各処理対象文字列（各結合キー文字列）に出現する各文字をそれぞれカウントし、そのカウント数をその総和が１になるように正規化し、正規化されたカウント数（すなわち出現頻度）の高い順に並べたものを訓練データとして生成する。データ分析部４１は、このように得られた訓練データから、回帰分析等を用いて学習を行い、関数ｚ（ｒ）を得る。【０２１７】
図３３は、訓練データ及び関数ｚ（ｒ）の例を示す図である。図３３において、各点（ひし形）が結ばれた細線が訓練データを示し、太線がその訓練データから得られた関数ｚ（ｒ）を示す。縦軸は出現頻度を示し、横軸は各文字の出現頻度の順位を示す。図３３の例では、処理対象文字列には２７個のユニーク文字が存在しており、横軸ｒは１以上２７以下の値を取る。この訓練データから回帰分析により以下の近似式が得られる。
ｚ（ｒ）＝−０．０３８ｌｎ（ｒ）＋０．１２６９【０２１８】
データ分析部４１は、各文字列長の出現頻度分布ｂｉｎを関数ｂｉｎ（ｌ）として得る。ｌは、文字列長を示す変数である。即ち、関数ｂｉｎ（ｌ）は、文字列長ｌに対してその出現頻度を出力する。データ分析部４１は、処理対象文字列における各文字列長の出現数をカウントし、そのカウント数から関数ｚ（ｒ）と同様の方法で訓練データを生成する。データ分析部４１は、このように得られた訓練データから、回帰分析等を用いて学習を行い、関数ｂｉｎ（ｌ）を得る。【０２１９】
データ分析部４１は、本システム１に試験的に結合処理を実行させることにより訓練データを生成し、この訓練データから回帰分析等を用いて学習を行うことにより、係数ｃ１、ｃ２及びｃ３を得る。例えば、データ分析部４１は、処理対象データからサンプリングされ得られたサンプリングデータ（サンプリングタプル）に対して、様々な分割パラメータｑの値を用いて試験的にシステム１に結合処理を実行させ、実際に計測された処理時間から訓練データを生成する。なお、係数ｃ１、ｃ２及びｃ３の取得は、分割パラメータｑの決定処理の前処理として逐次行われてもよいし、予めシミュレーションとして行われてもよい。後者の場合には、そのように得られた係数ｃ１、ｃ２及びｃ３が予めメモリ等に格納されていればよい。【０２２０】
以上に述べた要約情報の取得方法はあくまでも一例であり、特に、ｚ、ｂｉｎ、及び３つの係数は、よりよい精度のモデル（式４）が構築できるのであれば、どのような取得方法であっても構わない。【０２２１】
モデル構築部４３は、上述したように（式１）、（式２）、（式３）及び（式４）を用いて、処理時間モデルＴ（ｑ）を構築する。（式１）及び（式３）は、上述のように得られた要約情報を用いることにより算出することができる。以下、結合処理アルゴリズムとしてネステッドループが利用される場合において、上記（式２）の定義例について説明する。【０２２２】
或るｑコンビネーションｓに対応するバケットが所持する文字列の個数をｍｓで表すと、当該バケットで実行されるネステッドループアルゴリズムの計算量Ｆｓ（ｑ）は、次の式で表すことができる。
Ｆｓ（ｑ）＝ｍｓ２【０２２３】
分割パラメータｑに関する処理時間モデルを得るために、上記式におけるｍｓが次のようにｑを用いて書き直される。結合キー文字列ｘがｑコンビネーションｓに対応したバケットに振り分けられる確率をμｓとすると、全てのバケットに含まれる文字列の総和はＮｑであることから、ｍｓは次の式で表わすことができる。μｓは、処理対象文字列におけるｑコンビネーションｓの出現確率に等しい。
ｍｓ＝μｓＮｑ【０２２４】
ここで、文字列長が｜ｔ｜である文字列ｔの出現確率ｐ｜ｔ｜（ｔ）は、各文字の出現頻度分布ｚ（ｒ）を用いて、次の式で表すことができる。以下の式における関数ｒａｎｋ（ｃ）は、文字ｃの出現頻度の高い方からの順位を出力する関数を示す。なお、Σｓ∈Ｓｌｐｌ（ｓ）＝１が成立する。
【数５】
2013031117.tif 000007
【０２２５】
特殊文字「＊」は、処理対象文字列中の或る文字列ｘの長さｌが十分でないとき、ｑコンビネーション中に現れるため、タプルｘから長さ｜ｓ｜のｑコンビネーションｓが検出される確率は、各文字列の長さの出現頻度分布ｂｉｎ（ｌ）に依存する。よって、μｓは次式で表すことができる。
【数６】
2013031117.tif 000008
【０２２６】
以上から、或る値ｌに対して、次の式が成立する。
【数７】
2013031117.tif 000009
【０２２７】
Ｓｌは、処理対象文字列内の長さが（｜ｓ｜＝ｌ）の全ｑコンビネーションｓの集合であった。そこで、処理対象文字列に出現する全文字の数を｜Σ｜と表すと、次の式が得られる。なお、ｚ（ｒ）２の和は定数であるため、以下の式においてそれをαとした。
【数８】
2013031117.tif 000010
【０２２８】
結果、ネステッドループアルゴリズムに対応する上記（式２）は、変数ｑを用いて次の式として定義することができる。ｑ２で除算されているのは正規化のためである。
【数９】
2013031117.tif 000011
【０２２９】
従って、本実施例では、モデル構築部４３は、次の式に示す処理時間モデルＴ（ｑ）を構築する。
【数１０】
2013031117.tif 000012
【０２３０】
図３４Ａは、分割パラメータｑ（１≦ｑ≦１４）に関し上記（式５）から得られる理論的処理時間の例を示す図である。図３４Ｂは、分割パラメータｑ（１≦ｑ≦１４）に関し本実施例におけるシステム１に実際に結合処理させた場合の実測処理時間を示す図である。図３４Ａ及び図３４Ｂによれば、（式５）で示される処理時間モデルＴ（ｑ）の精度が示される。ここでは、各ユニーク文字の出現頻度分布ｚ、及び、各文字列の長さの出現頻度分布ｂｉｎが同じで、対象となるタプルの数（データサイズ）の異なる６種類の実験データが用いられた。【０２３１】
図３４Ａ及び図３４Ｂにおいて丸で囲まれた点が、各実験データにおける分割パラメータｑの最適値を示す。図３４Ａ及び図３４Ｂでは、上述の（式５）で得られた理論的な値と、実測により得られる値とが等しいことが示されている。従って、図３４Ａ及び図３４Ｂによれば、上述の（式５）において、文字列類似結合処理全体の処理時間を最小化する適切な分割パラメータｑを得ることができることが立証される。【０２３２】
〔第４実施形態の変形例〕
モデル構築部４３は、（式１）、（式２）及び（式３）により得られる、データ管理装置２０で実行されるバケット分割処理に掛かる時間Ｔｐ（ｑ）、結合処理装置３０で実行される類似結合処理に掛かる時間Ｔｊ（ｑ）、及び、システム制御装置１０で実行される局所結合結果の整合処理に掛かる時間Ｔａ（ｑ）の少なくとも１つを用いて処理時間モデルＴ（ｑ）を構築するようにしてもよい。例えば、類似結合処理に掛かる時間Ｔｊ（ｑ）をそのまま処理時間モデルＴ（ｑ）としてもよいし、バケット分割処理に掛かる時間Ｔｐ（ｑ）と類似結合処理に掛かる時間Ｔｊ（ｑ）とのみを用いて処理時間モデルＴ（ｑ）としてもよい。この場合には、図３１に示されるフローチャートにおいて、（Ｓ３１１）、（Ｓ３１２）及び（Ｓ３１３）の少なくとも１つが実行されればよい。【０２３３】
また、第４実施形態では、パラメータ推定装置４０を他の装置とは別に設ける例を示したが、パラメータ推定装置４０の各処理部は、システム制御装置１０、データ管理装置２０又は結合処理装置３０で実現されてもよい。【０２３４】
［補足］
上述の各実施形態及び変形例において実行される類似結合処理は、少なくとも１つのデータ管理装置２０に格納されている少なくとも１つのデータ（ＳＩＰタプル集合）であって処理要求で指定されたデータの中から、当該処理要求で指定された結合キー属性の文字列間の編集距離が閾値τの条件を満たすタプルのペアを検出していた。しかしながら、本発明に係る類似結合処理は、このような態様に限定されず、文字列類似検索処理の意をも包含する概念である。【０２３５】
つまり、本発明に係る類似結合処理は、処理要求等で得られるクエリ文字列を１つのタプルとし、このクエリ文字列との間の編集距離が閾値τの条件を満たすタプルを、少なくとも１つのデータ管理装置２０に格納されている少なくとも１つのデータの中から検索する処理であってもよい。【０２３６】
この態様では、処理要求で指定されたデータを保持するデータ管理装置２０は、上述の各実施形態と同様に、ＳＩＰタプルを生成しかつ分配する。一方、クエリ文字列をシステム制御装置１０から取得したデータ管理装置２０は、このクエリ文字列に関するＳＩＰタプルを生成しかつ分配する。クエリ文字列に関するＳＩＰタプルを受信した結合処理装置３０は、クエリ文字列に関するＳＩＰタプルと、他のＳＩＰタプルとのペアを対象に、上述の各実施形態及び変形例と同様の結合処理を実行すればよい。【０２３７】
また、本発明に係る類似結合処理は、同じ意味を示すが表記が微妙に異なる文字列を検出するといった名寄せ技術をも含む概念である。【０２３８】
また、上述の各実施形態及び変形例で示した文字列類似結合システム１は、複数の店舗をまたがる在庫検索システム等に適用することができる。このような態様によれば、商品名が店舗によって若干異なる場合にも、探したい商品を検出することができる。また、同じモデルの商品であっても色やサイズなどが違うことにより各商品に異なる品番が付く場合がある。このような場合でも、当該態様によれば、色やサイズが違う同じモデルの商品を検出することができる。【０２３９】
また、本願が提供する技術は、文字列のみならず、オブジェクトのシークエンスに対する類似結合にも適用可能である。ここでオブジェクトのシークエンスとは、例えば移動物体の軌跡や、イベントの時系列データなどが挙げられる。【０２４０】
ここで、上述の説明で用いた数学的記法について説明する。表記ａ［ｋ］は、配列ａのｋ（≧０）番目の要素を意味する。また、文字列ｘもまた配列と捉えることができる。配列ｘの大きさ（配列長、要素数）は、｜ｘ｜として表記される。但し、ｘが文字列を示す場合、ｘ［０］は、空文字に対応しかつ配列長（文字列長）にカウントされない。例えば、文字列ｘが「ａｂｃｄｅ」の場合、ｘ［０］は「」（空文字）であり、ｘ［１］は「ａ」であり、｜ｘ｜は５である。一方、配列Ａが（０、１、２、３）である場合、Ａ［０］は０であり、｜Ａ｜は４である。【０２４１】
なお、上述の説明で用いた複数のフローチャートでは、複数のステップ（処理）が順番に記載されているが、本実施形態で実行される処理ステップの実行順序は、その記載の順番に制限されない。本実施形態では、図示される処理ステップの順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態及び各変形例は、内容が相反しない範囲で組み合わせることができる。【０２４２】
上記の各実施形態及び各変形例の一部又は全部は、以下の付記のようにも特定され得る。但し、各実施形態及び各変形例が以下の記載に限定されるものではない。【０２４３】
（付記１）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する結合処理装置において、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段と、
を備えることを特徴とする結合処理装置。【０２４４】
（付記２）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるデータ管理装置において、
複数のタプルを格納するデータ格納手段と、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記複数の結合処理装置の中から、前記データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせの中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定するデータ分配手段と、
を備えることを特徴とするデータ管理装置。【０２４５】
（付記３）少なくとも１つのデータ管理装置、及び、この少なくとも１つのデータ管理装置で保持される複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置を含む文字列類似結合システムにおいて、
前記少なくとも１つのデータ管理装置は、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目までの端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの末尾文字に相当する該結合キー文字列中の文字の次の文字から該結合キー文字列の末尾文字までの末尾部分文字列と、該組み合わせの先頭文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせ、又は、前記各タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの先頭文字に相当する該結合キー文字列中の文字の前の文字から該結合キー文字列の先頭文字までの先頭部分文字列と、該組み合わせの末尾文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせを含むキー情報タプルをそれぞれ生成するキー情報生成手段と、
前記キー情報生成手段により生成された各キー情報タプルに対応する前記ｑ個の文字の各組み合わせに基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各結合処理装置に各タプルのデータとしてそれぞれ分配するデータ分配手段と、
を備え、
前記複数の結合処理装置はそれぞれ、
前記少なくとも１つのデータ管理装置から分配された複数のキー情報タプルを受信する受信手段と、
前記受信手段により受信された複数のキー情報タプルのうち、各キー情報タプルに対応する前記ｑ個の文字の組み合わせが共通するキー情報タプル集合毎に、前記類似結合処理を実行する結合処理手段と、
を備えることを特徴とする文字列類似結合システム。【０２４６】
（付記４）前記複数の結合処理装置はそれぞれ、
前記受信手段により受信された複数のキー情報タプルの各ペアに関し、前記各文字配置情報に含まれる同種の要素のうちの大きいほうの値を合計することにより第１部分推定値を算出し、前記末尾部分文字列間又は前記先頭部分文字列間の編集距離を第２部分推定値として算出し、該第１部分推定値と該第２部分推定値とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段、
を更に備え、
前記各結合処理装置の前記結合処理手段は、前記推定値算出手段により算出された各編集距離推定値と前記編集距離閾値τとの比較結果に基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、
ことを特徴とする付記３に記載の文字列類似結合システム。【０２４７】
（付記５）前記各結合処理装置の前記結合処理手段は、前記推定値算出手段により算出された各第１部分推定値と前記編集距離閾値τとの比較結果、及び、前記推定値算出手段により算出された各第２部分推定値と前記編集距離閾値τとの比較結果の少なくとも一方を更に用いることにより、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする付記４に記載の文字列類似結合システム。【０２４８】
（付記６）前記少なくとも１つのデータ管理装置及び前記複数の結合処理装置と通信可能なシステム制御装置を更に含み、
前記各結合処理装置の前記結合処理手段は、前記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、生成された各結果タプルをそれぞれ前記システム制御装置に送信し、
前記システム制御装置は、
前記複数の結合処理装置から送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が前記編集距離閾値τの条件を満たすタプルのペアを決定する結果生成手段、
を備えることを特徴とする付記４又は５に記載の文字列類似結合システム。【０２４９】
（付記７）前記取得手段は、前記編集距離閾値τ及び前記分割パラメータｑを少なくとも含む通信メッセージを受信することを特徴とする付記３から６のいずれか１つに記載の文字列類似結合システム。【０２５０】
（付記８）前記複数のタプルの結合キー文字列に関し、結合キー文字列の総数、各文字の出現頻度分布、各文字列長の出現頻度分布、最大文字列長及び係数を含む要約情報を生成するデータ分析手段と、
前記分割パラメータｑの値に対応して、前記少なくとも１つのデータ管理装置、前記複数の結合処理装置及び前記システム制御装置の少なくとも１つの処理に掛かる時間を示す処理時間モデルを、前記データ分析手段により生成された前記要約情報に基づいて生成するモデル構築手段と、
前記モデル構築手段により構築された前記処理時間モデルが示す時間を最小とする前記分割パラメータｑの値を決定する最適化手段と、
を備えるパラメータ推定装置を更に含む付記３から７のいずれか１つに記載の文字列類似結合システム。【０２５１】
（付記９）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて実行される文字列類似結合方法において、少なくとも１つのコンピュータが、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得し、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する、
ことを含む文字列類似結合方法。【０２５２】
（付記１０）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて実行される文字列類似結合方法において、少なくとも１つのコンピュータが、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得し、
前記各タプルの分配先として少なくとも１つのコンピュータを決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせの中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定する、
ことを含む文字列類似結合方法。【０２５３】
（付記１１）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて実行される文字列類似結合方法において、
少なくとも１つのコンピュータが、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得し、
前記各タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目までの端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの末尾文字に相当する該結合キー文字列中の文字の次の文字から該結合キー文字列の末尾文字までの末尾部分文字列と、該組み合わせの先頭文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせ、又は、前記各タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの先頭文字に相当する該結合キー文字列中の文字の前の文字から該結合キー文字列の先頭文字までの先頭部分文字列と、該組み合わせの末尾文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせを含むキー情報タプルをそれぞれ生成し、
前記生成された各キー情報タプルに対応する前記ｑ個の文字の各組み合わせに基づいて、当該各キー情報タプルの分配先を決定し、
前記各キー情報タプルを、分配先として決定された各コンピュータに各タプルのデータとしてそれぞれ分配し、
複数のコンピュータがそれぞれ、
前記少なくとも１つのコンピュータから分配された複数のキー情報タプルを受信し、
前記受信された複数のキー情報タプルのうち、各キー情報タプルに対応する前記ｑ個の文字の組み合わせが共通するキー情報タプル集合毎に、文字列類似結合処理を実行する、
ことを含む文字列類似結合方法。【０２５４】
（付記１２）前記複数のコンピュータがそれぞれ、
前記受信された複数のキー情報タプルの各ペアに関し、前記各文字配置情報に含まれる同種の要素のうちの大きいほうの値を合計することにより第１部分推定値を算出し、
前記末尾部分文字列間又は前記先頭部分文字列間の編集距離を第２部分推定値として算出し、
前記第１部分推定値と前記第２部分推定値とを加算することにより、編集距離推定値をそれぞれ算出し、
前記算出された各編集距離推定値と前記編集距離閾値τとの比較結果に基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、
ことを更に含む付記１１に記載の文字列類似結合方法。【０２５５】
（付記１３）前記複数のコンピュータがそれぞれ、前記算出された各第１部分推定値と前記編集距離閾値τとの比較結果、及び、前記算出された各第２部分推定値と前記編集距離閾値τとの比較結果の少なくとも一方を更に用いることにより、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを更に含む付記１２に記載の文字列類似結合システム。【０２５６】
（付記１４）前記複数のコンピュータがそれぞれ、
前記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、
前記生成された各結果タプルをそれぞれ他のコンピュータに送信し、
前記他のコンピュータが、
前記複数のコンピュータから送られた複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、
前記検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が前記編集距離閾値τの条件を満たすタプルのペアを決定する、
ことを更に含む付記１２又は１３に記載の文字列類似結合方法。【０２５７】
（付記１５）コンピュータが、
前記複数のタプルの結合キー文字列に関し、結合キー文字列の総数、各文字の出現頻度分布、各文字列長の出現頻度分布、最大文字列長及び係数を含む要約情報を生成し、
前記分割パラメータｑの値に対応して、前記少なくとも１つのコンピュータ、前記複数のコンピュータ及び前記他のコンピュータの少なくとも１つの処理に掛かる時間を示す処理時間モデルを、前記要約情報に基づいて生成し、
前記処理時間モデルが示す時間を最小とする前記分割パラメータｑの値を決定する、
ことを更に含む付記１１から１４のいずれか１つに記載の文字列類似結合方法。【０２５８】
（付記１６）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理をコンピュータに実行させるプログラムにおいて、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中に、共通する組み合わせを持たないタプルのペアを編集距離計算対象から除外する結合処理手段、
を前記コンピュータに実現させるプログラム。【０２５９】
（付記１７）複数のタプルを対象に編集距離閾値τ（正の整数）を用いて類似結合処理を実行する複数の結合処理装置と通信可能に接続されるコンピュータに、
複数のタプルを格納するデータ格納手段と、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記複数の結合処理装置の中から、前記データ格納手段に格納される各タプルを処理させる結合処理装置を各タプルの分配先として決定する際に、各タプルの結合キー文字列の中の先頭文字又は末尾文字から（τ＋ｑ）番目までの端部分に含まれる、並び順が維持されたｑ個の文字の組み合わせの中の少なくとも１つが共通する他のタプルと同じ分配先にそれぞれ決定し、かつ、当該ｑ個の文字の組み合わせの中に共通する組み合わせを持たない他のタプルとは同じ分配先にならないように、各タプルの分配先をそれぞれ決定するデータ分配手段と、
を実現させるプログラム。【０２６０】
（付記１８）複数のタプルを保持する少なくとも１つのコンピュータに、
前記編集距離閾値τ及び分割パラメータｑ（２以上の整数）を取得する取得手段と、
前記各タプルの結合キー文字列の先頭文字から（τ＋ｑ）番目までの端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの末尾文字に相当する該結合キー文字列中の文字の次の文字から該結合キー文字列の末尾文字までの末尾部分文字列と、該組み合わせの先頭文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせ、又は、前記各タプルの結合キー文字列の末尾文字から（τ＋ｑ）番目の端部分に含まれるｑ個の文字の各組み合わせに対して、該組み合わせの先頭文字に相当する該結合キー文字列中の文字の前の文字から該結合キー文字列の先頭文字までの先頭部分文字列と、該組み合わせの末尾文字の該結合キー文字列中の位置及び該組み合わせに含まれる文字間に存在する該結合キー文字列中の他の文字の数を要素として含む文字配置情報と、タプル特定データとの組み合わせを含むキー情報タプルをそれぞれ生成するキー情報生成手段と、
前記キー情報生成手段により生成された各キー情報タプルに対応する前記ｑ個の文字の各組み合わせに基づいて、当該各キー情報タプルの分配先を決定し、当該各キー情報タプルを、分配先として決定された各コンピュータに各タプルのデータとしてそれぞれ分配するデータ分配手段と、
を実現させ、
複数のコンピュータの各々に、
前記少なくとも１つのコンピュータから分配された複数のキー情報タプルを受信する受信手段と、
前記受信手段により受信された複数のキー情報タプルのうち、各キー情報タプルに対応する前記ｑ個の文字の組み合わせが共通するキー情報タプル集合毎に、前記類似結合処理を実行する結合処理手段と、
を実現させるプログラム。【０２６１】
（付記１９）前記複数のコンピュータの各々に、
前記受信手段により受信された複数のキー情報タプルの各ペアに関し、前記各文字配置情報に含まれる同種の要素のうちの大きいほうの値を合計することにより第１部分推定値を算出し、前記末尾部分文字列間又は前記先頭部分文字列間の編集距離を第２部分推定値として算出し、該第１部分推定値と該第２部分推定値とを加算することにより、編集距離推定値をそれぞれ算出する推定値算出手段、
を更に実現させ、
前記結合処理手段は、前記推定値算出手段により算出された各編集距離推定値と前記編集距離閾値τとの比較結果に基づいて、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、
ことを特徴とする付記１８に記載のプログラム。【０２６２】
（付記２０）前記結合処理手段は、前記推定値算出手段により算出された各第１部分推定値と前記編集距離閾値τとの比較結果、及び、前記推定値算出手段により算出された各第２部分推定値と前記編集距離閾値τとの比較結果の少なくとも一方を更に用いることにより、編集距離が前記編集距離閾値τの条件を満たすと推定されるタプルのペアを特定する、ことを特徴とする付記１９に記載のプログラム。【０２６３】
（付記２１）前記結合処理手段は、前記特定された各ペアに関し、タプル特定データのペア及び編集距離推定値を含む結果タプルをそれぞれ生成し、生成された各結果タプルをそれぞれ他のコンピュータに送信し、
前記他のコンピュータに、
前記送信された複数の結果タプルの中から同じタプル特定データのペアを含む重複結果タプルを検出し、検出された重複結果タプルの中から最小の編集距離推定値を持つ結果タプル以外の結果タプルを削除することにより、編集距離が前記編集距離閾値τの条件を満たすタプルのペアを決定する結果生成手段、
を実現させる付記１９又は２０に記載のプログラム。【０２６４】
（付記２２）前記複数のタプルの結合キー文字列に関し、結合キー文字列の総数、各文字の出現頻度分布、各文字列長の出現頻度分布、最大文字列長及び係数を含む要約情報を生成するデータ分析手段と、
前記分割パラメータｑの値に対応して、前記少なくとも１つのデータ管理装置、前記複数の結合処理装置及び前記システム制御装置の少なくとも１つの処理に掛かる時間を示す処理時間モデルを、前記データ分析手段により生成された前記要約情報に基づいて生成するモデル構築手段と、
前記モデル構築手段により構築された前記処理時間モデルが示す時間を最小とする前記分割パラメータｑの値を決定する最適化手段と、
をコンピュータに更に実現させる付記１９から２１のいずれか１つに記載のプログラム。【０２６５】
（付記２３）付記１６から２２のいずれか１つに記載のプログラムを記録したコンピュータが読み取り可能な記録媒体。【０２６６】
この出願は、２０１１年８月２６日に出願された日本出願特願２０１１−１８４７７７号、及び、２０１１年１１月３０日に出願された日本出願特願２０１１−２６２６２５号を基礎とする優先権を主張し、それら開示の全てをここに取り込む。
【図１】
2013031117.tif 000013
【図２】
2013031117.tif 000014
【図３】
2013031117.tif 000015
【図４Ａ】
2013031117.tif 000016
【図４Ｂ】
2013031117.tif 000017
【図５】
2013031117.tif 000018
【図６】
2013031117.tif 000019
【図７】
2013031117.tif 000020
【図８】
2013031117.tif 000021
【図９】
2013031117.tif 000022
【図１０】
2013031117.tif 000023
【図１１】
2013031117.tif 000024
【図１２】
2013031117.tif 000025
【図１３】
2013031117.tif 000026
【図１４】
2013031117.tif 000027
【図１５】
2013031117.tif 000028
【図１６】
2013031117.tif 000029
【図１７】
2013031117.tif 000030
【図１８】
2013031117.tif 000031
【図１９】
2013031117.tif 000032
【図２０】
2013031117.tif 000033
【図２１】
2013031117.tif 000034
【図２２】
2013031117.tif 000035
【図２３】
2013031117.tif 000036
【図２４】
2013031117.tif 000037
【図２５】
2013031117.tif 000038
【図２６】
2013031117.tif 000039
【図２７】
2013031117.tif 000040
【図２８】
2013031117.tif 000041
【図２９】
2013031117.tif 000042
【図３０】
2013031117.tif 000043
【図３１】
2013031117.tif 000044
【図３２】
2013031117.tif 000045
【図３３】
2013031117.tif 000046
【図３４Ａ】
2013031117.tif 000047
【図３４Ｂ】
2013031117.tif 000048
【図３５】
2013031117.tif 000049
【図３６】
2013031117.tif 000050
【図３７】
2013031117.tif 000051
【図３８】
2013031117.tif 000052
【国際調査報告】
2013031117.tif 000053
2013031117.tif 000054
2013031117.tif 000055
2013031117.tif 000056