(57)【特許請求の範囲】
【請求項１】
二分木生成装置と、複数の情報処理装置とを用いてデータの分散生成処理を行う分散生成処理システムにおいて、
前記二分木生成装置は、
二分木のデータ構造を用いて、複数のデータをレベルごとにある指標に従ってグループ分けし、キー情報を前記二分木における各ノードに対して割り当てるとともに、各ノードのノード値を取得するノード生成手段と、
前記複数の情報処理装置から出力されたノードごとの処理結果を示す処理結果情報を収集する収集手段と、
前記ノード生成手段により生成された前記各ノードのキー情報と当該各ノードに対応付けられたノード値とからなる初期情報又は前記収集手段により収集された処理結果情報を、キー情報に応じて、前記情報処理装置に分けて出力する出力手段と、
前記複数の情報処理装置において処理された処理結果情報に基づいて所定条件を満たした二分木を生成する二分木生成手段と、を備え、
前記出力手段は、前記初期情報を、キー情報に応じて、前記複数の情報処理装置に分けて出力し、
前記複数の情報処理装置のそれぞれは、
前記初期情報のキー情報ごとに分けて当該初期情報を入力し、入力した初期情報におけるノード値が所定条件を満たさないノードに基づいて、前記初期情報におけるノード値が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を示す処理結果レコードを出力し、
前記二分木生成装置における収集手段は、前記処理結果レコードを収集し、前記出力手段は、前記収集された処理結果レコードを特定ノード決定情報として、キー情報に応じて、前記複数の情報処理装置に分けて出力し、
前記複数の情報処理装置は、
前記特定ノード決定情報に基づいて、当該特定ノードの上位ノードの二分木における反対側の子ノードである兄弟ノードおよびその下位の全ノードである統合先ノードのそれぞれを示す統合先キー情報と、前記特定ノードおよびその下位の全ノードのそれぞれのキー情報との対応付けを行い、キー情報と統合先キー情報とからなる統合先情報を出力し、
前記二分木生成装置における収集手段は、前記統合先情報を収集し、前記出力手段は、前記統合先情報及び前記初期情報を、キー情報ごとに分けて、前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記統合先情報に基づいて、前記初期情報におけるキー情報ごとのノード値を、当該キー情報に対応する統合先キー情報のノード値に集計して、統合先キー情報ごとのノード値を算出し、
前記二分木生成手段は、算出されたノード値に基づいて所定条件を満たした二分木を生成することを特徴とする分散生成処理システム。
【請求項２】
前記出力手段は、前記初期情報をキー情報ごとのレコード単位に分割した初期レコードのそれぞれを、キー情報に応じて、前記複数の情報処理装置に分けて出力し、
前記複数の情報処理装置のそれぞれは、
入力した初期情報のキー情報ごとに分けて当該初期レコードを入力し、入力した前記初期レコードにおけるノード値が所定条件を満たさない場合には、当該初期レコードに記述されているキー情報、およびその旨を示す識別子情報からなる第零処理結果レコードを生成し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第零処理結果レコードを収集して合成することで第零処理結果情報を生成し、前記出力手段は、前記第零処理結果情報をキー情報ごとのレコード単位に分けた第零入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
当該複数の情報処理装置のそれぞれは、
前記第零入力レコードを入力し、当該第零入力レコードのキー情報に基づいて、それぞれのノードに対する兄弟ノード及び下位にある子ノードのキー情報を、第一処理結果レコードとして出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第一処理結果レコードを収集して合成することで第一処理結果情報を生成し、前記出力手段は、前記第一処理結果情報をキー情報ごとのレコード単位に分けた第一入力レコードのそれぞれを、当該第一入力レコードと同じキー情報を有する前記第零入力レコードとともに、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
当該複数の情報処理装置のそれぞれは、
当該第一入力レコードを入力した場合には、第二処理結果レコードを出力せず、前記第零入力レコードのみを入力した場合には、当該第零入力レコードに記述されているキー情報を第二処理結果レコードとして出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第二処理結果レコードを収集して合成することで、第二処理結果情報を生成し、前記出力手段は、当該第二処理結果情報をキー情報ごとのレコード単位に分けた第二入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記第二入力レコードを入力し、当該第二入力レコードに記述されているキー情報である自キー情報および前記キー情報で示されるノードの上位にある上位ノードの兄弟ノードを示す対キー情報を、それぞれ前記キー情報と対応付けた第三処理結果レコードを生成して出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第三処理結果レコードを収集して合成することで、第三処理結果情報を生成し、前記出力手段は、当該第三処理結果情報をキー情報ごとのレコード単位に分けた第三入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記第三入力レコードを入力し、当該第三入力レコードにおけるキー情報と、そのバリュー値との一致・不一致を示す一致情報を、キー情報と対応付けた第四処理結果レコードを生成して出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第四処理結果レコードを収集して合成することで、第四処理結果情報を生成し、前記出力手段は、当該第四処理結果情報をキー情報ごとのレコード単位に分けた第四入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記一致情報が一致を示す第四入力レコードのみを入力した場合には、当該第四入力レコードに含まれるキー情報を第五処理結果レコードとして出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第五処理結果レコードを収集して合成することで第五処理結果情報を生成し、これを特定ノード決定情報とすることを特徴とする請求項１に記載の分散生成処理システム。
【請求項３】
前記出力手段は、前記特定ノード決定情報をキー情報ごとのレコード単位に分けた第五入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記第五入力レコードを入力し、当該第五入力レコードのキー情報で示される特定ノードの下位にある全下位ノードの下位キー情報のすべてと、当該下位キー情報のそれぞれを二進数で構成されるビット列のうち前記特定ノードを示すビットを反転した反転キー情報とを対応付けた第六処理結果レコードを生成して出力し、
前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第六処理結果レコードを収集して合成することで第六処理結果情報を生成し、これを統合先情報とすることを特徴とする請求項１または２に記載の分散生成処理システム。
【請求項４】
前記二分木生成装置における収集手段は、前記統合先情報を収集し、前記出力手段は、前記初期情報に記述されているキー情報ごとのレコード単位に分けた初期レコードのそれぞれ、および当該統合先情報をキー情報ごとのレコード単位に分けた第六入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記初期レコード、および当該初期レコードと同じキー情報を有する前記第六入力レコードを入力し、
前記初期レコードおよび前記第六入力レコードが入力された場合には、当該第六入力レコードにおける反転キー情報をキー情報として、前記初期レコードのノード値をバリュー値として対応付けた第七処理結果レコードを生成し、前記初期レコードのみが入力された場合には、当該初期レコードを第七処理結果レコードとして、それぞれ出力し、
前記二分木生成装置における収集手段は、前記第七処理結果レコードを収集して合成することで第七処理結果情報を生成し、前記出力手段は、当該第七処理結果情報を、キー情報ごとのレコード単位に分けた第七入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記第七入力レコードを入力し、当該第七入力レコードに含まれているノード値を集計して、最終処理結果レコードとして出力し、
前記二分木生成装置における収集手段は、前記最終処理結果レコードを収集して合成することで最終処理結果情報を生成し、前記二分木生成手段は、当該最終処理結果情報に基づいて前記所定条件を満たした二分木を生成する、ことを特徴とする請求項１から３のいずれか一項に記載の分散生成処理システム。
【請求項５】
二分木生成手段により生成された二分木が所定条件を満たすまで、前記特定ノード決定情報の出力処理、前記統合先情報の出力処理、およびノード値の集計処理を繰り返し行うことを特徴とする請求項１から４のいずれか一項に記載の分散生成処理システム。
【請求項６】
二分木生成装置と、複数の情報処理装置とを用いてデータの分散生成処理を行う分散生成処理システムの分散生成処理方法において、
前記二分木生成装置は、二分木のデータ構造を用いて、複数のデータをレベルごとにある指標に従ってグループ分けし、キー情報を前記二分木における各ノードに対して割り当てるとともに、各ノードのノード値を取得するノード生成ステップと、
前記複数の情報処理装置から出力されたノードごとの処理結果を示す処理結果情報を収集する収集ステップと、
前記ノード生成ステップにより生成された前記各ノードのキー情報と当該各ノードに対応付けられたノード値とからなる初期情報又は前記収集ステップにより収集された処理結果情報を、キー情報に応じて、前記情報処理装置に分けて出力する出力ステップと、
前記複数の情報処理装置において処理された処理結果情報に基づいて所定条件を満たした二分木を生成する二分木生成ステップと、を備え、
前記出力ステップは、前記初期情報を、キー情報に応じて、前記複数の情報処理装置に分けて出力し、
前記複数の情報処理装置のそれぞれは、
前記初期情報のキー情報ごとに分けて当該初期情報を入力し、入力した初期情報におけるノード値が所定条件を満たさないノードに基づいて、前記初期情報におけるノード値が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を示す処理結果レコードを出力し、
前記二分木生成装置における収集ステップは、前記処理結果レコードを収集し、前記出力ステップは、前記収集された処理結果レコードを特定ノード決定情報として、キー情報に応じて、前記複数の情報処理装置に分けて出力し、
前記複数の情報処理装置は、
前記特定ノード決定情報に基づいて、当該特定ノードの上位ノードの二分木における反対側の子ノードである兄弟ノードおよびその下位の全ノードである統合先ノードのそれぞれを示す統合先キー情報と、前記特定ノードおよびその下位の全ノードのそれぞれのキー情報との対応付けを行い、キー情報と統合先キー情報とからなる統合先情報を出力し、
前記二分木生成装置における収集ステップは、前記統合先情報を収集し、前記出力ステップは、前記統合先情報及び前記初期情報を、キー情報ごとに分けて、前記複数の情報処理装置のそれぞれに出力し、
前記複数の情報処理装置のそれぞれは、
前記統合先情報に基づいて、前記初期情報におけるキー情報ごとのノード値を、当該キー情報に対応する統合先キー情報のノード値に集計して、統合先キー情報ごとのノード値を算出し、
前記二分木生成ステップは、算出されたノード値に基づいて所定条件を満たした二分木を生成することを特徴とする分散生成処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二分木を用いたノードに対する分散生成処理システムおよび分散生成処理方法に関する。
【背景技術】
【０００２】
ビッグデータを対象とする製品やサービスの提供が広がっている。ビッグデータを分析する際にはユーザおよびコンテンツ等をグループ化して計算量を削減する手法が一般的である。ここで、ユーザおよびコンテンツ等をグループ化する際に二分木を利用することが可能である。二分木を用いてグループ化するものとして、特許文献１に記載のものが挙げられる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−０７７１３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、全ノードが所定条件を満たす二分木はシーケンシャルでしか生成できないため、分散処理にて上記の全ノードが所定条件（例えばある値以上のデータ数を持つノード）を満たす二分木を生成することは困難である。
【０００５】
そこで、本発明においては、分散処理により全ノードが所定条件を満たす二分木を生成することできる分散生成処理システムおよび分散生成処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述の課題を解決するために、本発明の分散生成処理システムは、二分木生成装置と、複数の情報処理装置とを用いてデータの分散生成処理を行う分散生成処理システムにおいて、前記二分木生成装置は、二分木のデータ構造を用いて、複数のデータをレベルごとにある指標に従ってグループ分けし、キー情報を前記二分木における各ノードに対して割り当てるとともに、各ノードのノード値を取得するノード生成手段と、前記複数の情報処理装置から出力されたノードごとの処理結果を示す処理結果情報を収集する収集手段と、前記ノード生成手段により生成された前記各ノードのキー情報と当該各ノードに対応付けられたノード値とからなる初期情報又は前記収集手段により収集された処理結果情報を、キー情報に応じて、前記情報処理装置に分けて出力する出力手段と、前記複数の情報処理装置において処理された処理結果情報に基づいて所定条件を満たした二分木を生成する二分木生成手段と、を備え、前記出力手段は、前記初期情報を、キー情報に応じて、前記複数の情報処理装置に分けて出力し、前記複数の情報処理装置のそれぞれは、前記初期情報のキー情報ごとに分けて当該初期情報を入力し、入力した初期情報におけるノード値が所定条件を満たさないノードに基づいて、前記初期情報におけるノード値が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を示す処理結果レコードを出力し、前記二分木生成装置における収集手段は、前記処理結果レコードを収集し、前記出力手段は、前記収集された処理結果レコードを特定ノード決定情報として、キー情報に応じて、前記複数の情報処理装置に分けて出力し、前記複数の情報処理装置は、前記特定ノード決定情報に基づいて、当該特定ノードの上位ノードの二分木における反対側の子ノードである兄弟ノードおよびその下位の全ノードである統合先ノードのそれぞれを示す統合先キー情報と、前記特定ノードおよびその下位の全ノードのそれぞれのキー情報との対応付けを行い、キー情報と統合先キー情報とからなる統合先情報を出力し、前記二分木生成装置における収集手段は、前記統合先情報を収集し、前記出力手段は、前記統合先情報及び前記初期情報を、キー情報ごとに分けて、前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記統合先情報に基づいて、前記初期情報におけるキー情報ごとのノード値を、当該キー情報に対応する統合先キー情報のノード値に集計して、統合先キー情報ごとのノード値を算出し、前記二分木生成手段は、算出されたノード値に基づいて所定条件を満たした二分木を生成することを特徴とする。
【０００７】
本発明の分散生成処理方法は、二分木生成装置と、複数の情報処理装置とを用いてデータの分散生成処理を行う分散生成処理システムの分散生成処理方法において、前記二分木生成装置は、二分木のデータ構造を用いて、複数のデータをレベルごとにある指標に従ってグループ分けし、キー情報を前記二分木生成装置における各ノードに対して割り当てるとともに、各ノードのノード値を取得するノード生成ステップと、前記複数の情報処理装置から出力されたノードごとの処理結果を示す処理結果情報を収集する収集ステップと、前記ノード生成ステップにより生成された前記各ノードのキー情報と当該各ノードに対応付けられたノード値とからなる初期情報又は前記収集ステップにより収集された処理結果情報を、キー情報に応じて、前記情報処理装置に分けて出力する出力ステップと、前記複数の情報処理装置において処理された処理結果情報に基づいて所定条件を満たした二分木を生成する二分木生成ステップと、を備え、前記出力ステップは、前記初期情報を、キー情報に応じて、前記複数の情報処理装置に分けて出力し、前記複数の情報処理装置のそれぞれは、前記初期情報のキー情報ごとに分けて当該初期情報を入力し、入力した初期情報におけるノード値が所定条件を満たさないノードに基づいて、前記初期情報におけるノード値が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を示す処理結果レコードを出力し、前記二分木生成装置における収集ステップは、前記処理結果レコードを収集し、前記出力ステップは、前記収集された処理結果レコードを特定ノード決定情報として、キー情報に応じて、前記複数の情報処理装置に分けて出力し、前記複数の情報処理装置は、前記特定ノード決定情報に基づいて、当該特定ノードの上位ノードの二分木における反対側の子ノードである兄弟ノードおよびその下位の全ノードである統合先ノードのそれぞれを示す統合先キー情報と、前記特定ノードおよびその下位の全ノードのそれぞれのキー情報との対応付けを行い、キー情報と統合先キー情報とからなる統合先情報を出力し、前記二分木生成装置における収集ステップは、前記統合先情報を収集し、前記出力ステップは、前記統合先情報及び前記初期情報を、キー情報ごとに分けて、前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記統合先情報に基づいて、前記初期情報におけるキー情報ごとのノード値を、当該キー情報に対応する統合先キー情報のノード値に集計して、統合先キー情報ごとのノード値を算出し、前記二分木生成ステップは、算出されたノード値に基づいて所定条件を満たした二分木を生成することを特徴とする。
【０００８】
この発明によれば、初期情報のキー情報ごとに分けて当該初期情報を複数の情報処理装置に出力し、それぞれの情報処理装置では、入力した初期情報におけるノード値が所定条件を満たさないノードに基づいて、初期情報におけるノード値が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を特定ノード決定情報として出力し、特定ノード決定情報に基づいて、キー情報と統合先キー情報とからなる統合先情報を出力し、統合先情報に基づいて、初期情報におけるキー情報ごとのノード値を、当該キー情報に対応する統合先キー情報のノード値に集計して、統合先キー情報ごとのノード値を算出し、算出されたノード値に基づいて所定条件を満たした二分木を生成する。これにより、各情報処理装置において、分散処理をすることにより特定ノードの決定、統合先の決定をおこなって、これらに基づいて二分木を生成することができる。
【０００９】
また、本発明の分散生成処理ステムにおいて、前記出力手段は、前記初期情報をキー情報ごとのレコード単位に分割した初期レコードのそれぞれを、キー情報に応じて、前記複数の情報処理装置に分けて出力し、前記複数の情報処理装置のそれぞれは、入力した初期情報のキー情報ごとに分けて当該初期レコードを入力し、入力した前記初期レコードにおけるノード値が所定条件を満たさない場合には、当該初期レコードに記述されているキー情報、およびその旨を示す識別子情報からなる第零処理結果レコードを生成し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第零処理結果レコードを収集して合成することで第零処理結果情報を生成し、前記出力手段は、前記第零処理結果情報をキー情報ごとのレコード単位に分けた第零入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、当該複数の情報処理装置のそれぞれは、前記第零入力レコードを入力し、当該第零入力レコードのキー情報に基づいて、それぞれのノードに対する兄弟ノード及び下位にある子ノードのキー情報を、第一処理結果レコードとして出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第一処理結果レコードを収集して合成することで第一処理結果情報を生成し、前記出力手段は、前記第一処理結果情報をキー情報ごとのレコード単位に分けた第一入力レコードのそれぞれを、当該第一入力レコードと同じキー情報を有する前記第零入力レコードとともに、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、当該複数の情報処理装置のそれぞれは、当該第一入力レコードを入力した場合には、第二処理結果レコードを出力せず、前記第零入力レコードのみを入力した場合には、当該第零入力レコードに記述されているキー情報を第二処理結果レコードとして出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第二処理結果レコードを収集して合成することで、第二処理結果情報を生成し、前記出力手段は、当該第二処理結果情報をキー情報ごとのレコード単位に分けた第二入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記第二入力レコードを入力し、当該第二入力レコードに記述されているキー情報である自キー情報および前記キー情報で示されるノードの上位にある上位ノードの兄弟ノードを示す対キー情報を、それぞれ前記キー情報と対応付けた第三処理結果レコードを生成して出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第三処理結果レコードを収集して合成することで、前記第三処理結果情報を生成し、前記出力手段は、当該第三処理結果情報をキー情報ごとのレコード単位に分けた第三入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記第三入力レコードを入力し、当該第三入力レコードにおけるキー情報と、そのバリュー値との一致・不一致を示す一致情報を、キー情報と対応付けた第四処理結果レコードを生成して出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第四処理結果レコードを収集して合成することで、第四処理結果情報を生成し、前記出力手段は、当該第四処理結果情報をキー情報ごとのレコード単位に分けた第四入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記一致情報が一致を示す第四入力レコードのみを入力した場合には、当該第四入力レコードに含まれるキー情報を第五処理結果レコードとして出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第五処理結果レコードを収集して合成することで第五処理結果情報を生成し、これを特定ノード決定情報とすることを特徴とする。
【００１０】
また、本発明の分散生成処理ステムにおいて、前記出力手段は、前記特定ノード決定情報をキー情報ごとのレコード単位に分けた第五入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記第五入力レコードを入力し、当該第五入力レコードのキー情報で示される特定ノードの下位にある全下位ノードの下位キー情報のすべてと、当該下位キー情報のそれぞれを二進数で構成されるビット列のうち前記特定ノードを示すビットを反転した反転キー情報とを対応付けた第六処理結果レコードを生成して出力し、前記二分木生成装置における収集手段は、前記複数の情報処理装置から前記第六処理結果レコードを収集して合成することで前記第六処理結果情報を生成し、これを統合先情報とすることを特徴とする。
【００１１】
また、本発明の分散生成処理ステムにおいて、前記二分木生成装置における収集手段は、前記第統合先情報を収集し、前記出力手段は、前記初期情報に記述されているキー情報ごとのレコード単位に分けた初期レコードのそれぞれ、および当該統合先情報をキー情報ごとのレコード単位に分けた第六入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記初期レコード、および当該初期レコードと同じキー情報を有する前記第六入力レコードを入力し、前記初期レコードおよび前記第六入力レコードが入力された場合には、当該第六入力レコードにおける反転キー情報をキー情報として、前記初期レコードのノード値をバリュー値として対応付けた第七処理結果レコードを生成し、前記初期レコードのみが入力された場合には、当該第初期レコードを第七処理結果レコードとして、それぞれ出力し、前記二分木生成装置における収集手段は、前記第七処理結果レコードを収集して合成することで第七処理結果情報を生成し、前記出力手段は、当該第七処理結果情報を、キー情報ごとのレコード単位に分けた第七入力レコードのそれぞれを、キー情報ごとに分けて前記複数の情報処理装置のそれぞれに出力し、前記複数の情報処理装置のそれぞれは、前記第七入力レコードを入力し、当該第七入力レコードに含まれているノード値を集計して、最終処理結果レコードとして出力し、前記二分木生成装置における収集手段は、前記最終処理結果レコードを収集し手合成することで最終処理結果情報を生成し、前記二分木生成手段は、当該最終処理結果情報に基づいて前記所定条件を満たした二分木を生成する、ことを特徴とする。
【００１２】
また、本発明の分散生成処理システムは、二分木生成手段により生成された二分木が所定条件を満たすまで、前記特定ノード決定情報の出力処理、前記統合先情報の出力処理、およびノード値の集計処理を繰り返し行うことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、各情報処理装置において、分散処理をすることにより特定ノードの決定、統合先の決定をおこなって、これらに基づいて所定条件を満たす二分木を生成することができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態の分散生成処理システム１０のシステム構成を示すシステム図である。
【図２】二分木生成装置１００の機能構成を示すブロック図である。
【図３】サーバ２００の機能を示すブロック図である。
【図４】二分木生成から分散処理をして、最終的な二分木を生成する処理を示すフローチャートである。
【図５】仮二分木生成の処理を示す模式図である。
【図６】二分木生成装置１００において生成された初期情報３０１（キー情報とデータ数）に基づいた処理を示す模式図である。
【図７】入力３０３−１に対する処理を示す模式図である。
【図８】入力３０３Ａおよび３０３−１に対する処理を示す模式図である。
【図９】入力３０５に対する処理を示す模式図である。
【図１０】入力３０７に対する処理を示す模式図である。
【図１１】入力３０９に対する処理を示す模式図である。
【図１２】入力３１１に対する処理を示す模式図である。
【図１３】入力３１３に対する処理を示す模式図である。
【図１４】入力３１５に対する処理を示す模式図である。
【発明を実施するための形態】
【００１５】
添付図面を参照しながら本発明の実施形態を説明する。可能な場合には、同一の部分には同一の符号を付して、重複する説明を省略する。
【００１６】
図１は、本実施形態の分散生成処理システム１０のシステム構成を示すシステム図である。図１に示される通り、二分木生成装置１００と、複数のサーバ２００とから構成されている。図１においては、サーバ２００ａ〜２００ｘと便宜上記載しているが、この数に限定されるものではない。
【００１７】
本実施形態においては、二分木生成装置１００が、仮二分木を生成し、これに基づいて、仮二分木における各ノードのデータをサーバ２００ａ〜２００ｘに振り分け、分散処理させる。二分木生成装置１００は、サーバ２００ａ〜２００ｘにおいて処理された処理結果を収集し、再度ノードごとにサーバ２００ａ〜２００ｘに処理結果を振り分け、分散処理を行わせる。この分散処理を行うことにより、最上位ノードの決定、統合先ノードの抽出、およびノードの統合といった処理を実行する。統合先のノードの処理結果を集計することにより、各ノードにおいて所定条件を満たした二分木を生成することができる。
【００１８】
つぎに、この分散処理システム１０についてより詳細に説明する。図２は、二分木生成装置１００の機能構成を示すブロック図である。この二分木生成装置１００は、仮二分木生成部１０１（ノード生成手段）、処理結果収集部１０２（収集手段）、出力部１０３（出力手段）、二分木生成部１０４（二分木生成手段）、および二分木生成元情報記憶部１０５を含んで構成されている。
【００１９】
仮二分木生成部１０１は、あるデータ群に基づいて、仮二分木を生成する部分であり、二分木のデータ構造を用いて、データをレベルごとにある指標によってグループ分けするし、二分木におけるノードの位置を示すキー情報を各ノードに対して割り当るとともに、各ノードのノード値を取得する。ここで、ノード値とは、典型的には各ノードに割り当てられたデータ数であるが、これに限定されない。例えば、各ノードの重みや重要度を表す値であってもよい。本実施形態においては、ノード値は各ノードに割り当てられたデータ数を表すこととする。また、仮二分木とは、最終的に二分木が満たすべき所定の条件を満たしていない二分木を意味する。例えば、この仮二分木生成部１０１は、二分木生成元情報記憶部１０５に記憶されている複数のデータ（閲覧履歴データ）に対して、ある指標を満たすもの、および満たさないものに分割して、それぞれのデータ数を出力し、さらに上記指標を満たすものの複数のデータから、さらに別の指標を満たすもの、満たさないものに分割して、それぞれのデータ数を出力する。これを繰り返すことにより、ノードごとにデータ数を生成することができる。例えば、仮二分木生成部１０１は、グループ分けに用いる指標を、ウェブサイトの閲覧有無とし、ウェブサイトを閲覧したユーザ数をデータ数として仮二分木を生成する。この場合、まず、サイトＡを閲覧したユーザ数、閲覧しなかったユーザ数をそれぞれデータ数として出力する。同様に、サイトＡを閲覧したユーザのうちサイトＢを閲覧したユーザ数、閲覧しなかったユーザ数をデータ数として出力する。
【００２０】
このような繰り返し処理したことにより、仮二分木生成部１０１は、二分木におけるノードの位置を示すキー情報とそのデータ数とを対応付けた初期情報を生成する。このキー情報は、２進数のビット列からなるものであり、二分木の右側から、そのレベルに応じたビット列をもって割り振られる。
【００２１】
処理結果収集部１０２は、仮二分木生成部１０１により生成された仮二分木に基づいた、キー情報（ノード）ごとのデータ数若しくはサーバ２００において処理されたキー情報（ノード）ごとの処理結果３を、収集する部分である。この処理結果収集部１０２は、処理結果をサーバ２００に振り分ける際に、さらにキー情報ごとに振り分けるサーバ２００を分けて、サーバ２００ａ〜２００ｘに振り分ける。
【００２２】
出力部１０３は、処理結果収集部１０２により振り分けられたサーバ２００に対してキー情報のみ、若しくはキー情報と処理結果とからなる入力レコード、または仮二分木生成部１０１で生成された初期情報の初期レコードを各サーバ２００に出力する。
【００２３】
二分木生成部１０４は、最終処理結果に基づいて、統合先のノードのデータ数と、統合元のデータ数とを集計して、二分木を生成する部分である。なお、ここで生成した二分木が所定条件を満たさない場合には、これを仮二分木として、再度上述の処理を繰り返す。
【００２４】
二分木生成元情報記憶部１０５は、二分木生成の対象となるデータを記憶する部分であり、たとえばウェブコンテンツに対する閲覧履歴データを記憶する。この閲覧履歴データは、一般的なものでよく、ユーザＩＤとコンテンツＩＤとを対応付けたもので構成される。
【００２５】
このような二分木生成装置１００により生成されたキー情報およびデータ数からなるデータを初期情報として、キー情報ごとに分けて各サーバ２００に処理させることで、分散処理を行うことができる。また、各サーバ２００において処理された処理結果を再度各サーバにキー情報ごとに分けて処理させることで、分散処理を行うことができる。
【００２６】
図３は、サーバ２００の機能を示すブロック図である。図３に示されるように、サーバ２００は、入力部２０１、情報処理部２０２、および出力部２０３から構成されている。
【００２７】
入力部２０１は、二分木生成装置１００から出力されたキー情報のみ、またはキー情報に対応付けられたデータ数若しくは処理結果から構成される入力レコード若しくは初期レコードを入力する。
【００２８】
情報処理部２０２は、入力部２０１から入力したキー情報または処理結果からなる入力レコードに対して、所定の情報処理を実行する部分である。この所定の情報処理については、後述する。なお、情報処理部２０２は、二分木生成装置１００における仮二分木生成部１０１で生成した仮二分木に関する情報を取得し、または記憶しており、この情報に従って処理（例えば対ノードのキー情報の取得や、子ノードのキー情報の取得）を実行可能にする。
【００２９】
出力部２０３は、二分木生成装置１００からの収集処理に応じて、情報処理した処理結果を含んだ処理結果レコードを出力する部分である。
【００３０】
このサーバ２００は、上述した通り、複数台からなるものであって、キー情報ごとに初期レコードまたは入力レコードが割り振られて、それぞれ所定の情報処理を実行することにより、分散処理を行うことができる。
【００３１】
図４に、二分木生成から分散処理をして、最終的な二分木を生成する処理について説明する。図４は、その処理を示すフローチャートである。
【００３２】
まず、二分木生成装置１００において、二分木生成元情報記憶部１０５に記憶されているデータに基づいて、仮二分木の生成が行われる（Ｓ１０１）。そして、サーバ２００の分散処理に従って、仮二分木における各ノードにおけるデータ数が所定条件を満たさないノードに基づいて、初期情報におけるデータ数が所定条件を満たさない最上位のノードが特定ノードとして抽出される（Ｓ１０２）。
【００３３】
そして、この特定ノードに基づいて、統合先となる統合先ノードが抽出される。すなわち、各サーバ２００において、特定ノード決定情報に基づいて、当該特定ノードの上位ノードをルートとした兄弟ノードおよびその下位の全ノードである統合先ノードのそれぞれを示す統合先キー情報が抽出される（Ｓ１０３）。そして、複数の統合先ノードと、統合元となるノードとのそれぞれのキー情報およびそのデータ数が、各サーバ２００に割り振られ、各サーバ２００における分散処理により、統合処理が行われる（Ｓ１０４）。そして、統合処理によって、二分木生成部１０４により、新たな二分木が生成される（Ｓ１０５）。なお、生成した二分木のすべてのノードが所定条件を満たしていない場合には、再度、Ｓ１０２〜Ｓ１０５の処理が繰り返し行われ、ノードのすべてが所定条件を満たすまで繰り返し、分散処理が行われる。
【００３４】
つぎに、この処理について、より具体的に説明する。図５は、Ｓ１０１の処理である仮二分木生成の処理を示す模式図である。図５に示される通り、仮二分木生成部１０１は、閲覧履歴データに基づいて、サイトＡの閲覧履歴を保持するユーザ数、保持しないユーザ数をデータ数として抽出する。ここでは、それぞれ、保持：１００１、不保持：９９が抽出される。なお、保持のノードのキー情報が１であり、不保持のノードのキー情報が０である。
【００３５】
同様に、サイトＡを閲覧履歴に保持するユーザ数のうち、サイトＢを閲覧履歴に保持するユーザ数および保持しないユーザ数をデータ数として抽出する。それぞれ、保持：９１、不保持：９１０が抽出される。なお、保持ノードのキー情報が１１、不保持ノードのキー情報が１０である。ほかも同様に、ノード（キー情報）ごとにユーザ数が抽出されることで、二分木が生成される。
【００３６】
つぎに、このようにして仮二分木を生成することで、キー情報とユーザ数（データ数）とからなる初期情報を利用して、キー情報ごとにデータ数を各サーバ２００に割り振る。そして、各サーバ２００における分散処理を行うことができる。以下、その具体的に処理について、図６から図１４を用いて説明する。
【００３７】
図６は、二分木生成装置１００において生成された初期情報３０１（キー情報とデータ数）に基づいた処理を示す模式図である。図６に示されるように、初期情報３０１がキー情報ごとのレコード単位に分割された初期レコードが、そのキー情報に応じて、それぞれのサーバ２００に出力される。例えば、サーバ２００ａには、初期レコードとして、キー情報：０、データ数：９９の初期レコード３０１ａが出力され、サーバ２００ｂには、キー情報：１、データ数：１００１の初期レコード３０１ｂが出力され、以下同様にサーバ２００ごとに、キー情報ごとのレコード単位に分割された初期レコードが出力される。なお、サーバ数が初期レコード数より少ない場合には、同じサーバにおいて、異なるキー情報の初期レコードを出力する。以降の処理においても同様に、入力レコード数がサーバ数を上回った場合、一のサーバにおいて異なるキー情報に対応する入力レコードに対する処理を行うよう出力処理を行う。以降説明する分散処理をさせる際において、入力レコードまたはそのキー情報がサーバ数より多い場合には、同様に一のサーバにキー情報が異なる複数の入力レコードを出力する。
【００３８】
そして、各サーバ２００においては、初期レコードにおいて所定条件（本実施形態ではデータ数が１００以上のもの）を満たす場合については、処理結果を出力せず、所定条件を満たさない場合には、処理結果として、初期レコードに記述されているキー情報、および所定条件を満たさないことを示す識別子である“ＵＮＤＥＲ”からなる第零処理結果レコードを生成し、出力する。
【００３９】
図６においては、サーバ２００ａは、初期レコード３０１ａとしてキー情報：０、データ数：９９を入力し、データ数：９９は、１００未満であるため、所定条件を満たさず、自キー情報（入力したキー情報のノードを示すキー情報）および所定条件を満たさないことを示す識別子情報である“ＵＮＤＥＲ”をバリュー値とした第零処理結果レコード３０２ａを生成して、出力する。ここでは、キー情報：０、バリュー値：ＵＮＤＥＲを第零処理結果レコード３０２ａとして出力する。一方、所定条件を満たす場合には、第零処理結果レコード３０２ａは出力されない。例えば、サーバ２００ｂでは、キー情報：１、バリュー値：１００１からなる初期レコード３０１ｂが入力され、バリュー値は所定条件（１００以上）を満たしているため、サーバ２００ｂからは何も出力しない。他のサーバ２００においても同様の処理を行う。
【００４０】
この図６における第零処理結果レコード３０２ａ等は、二分木生成装置１００により収集されて合成され、その結果、出力３０２（第零処理結果情報）が生成される。
【００４１】
図７は、第零処理結果情報である入力３０３に基づいた処理を示す模式図である。図７に示される通り、処理結果収集部１０２では、出力３０２を入力３０３−１として扱い、出力部１０３は、その入力３０３−１をそれぞれキー情報ごとのレコード単位に分割して、第零入力レコード３０３−１ａ、３０３−１ｂ等を生成し、キー情報に応じて、第零入力レコード３０３−１ａ等をサーバ２００に出力する。
そして、各サーバ２００において、第零入力レコード３０３−１ａ等をそれぞれ入力し、当該第零入力レコード３０３−１ａ等のキー情報に基づいて、それぞれのノードに対して下位にある子ノードのキー情報、当該第零入力レコード３０３−１ａ等に記述されているキー情報で示されるノードの兄弟ノードのキー情報を取得し、第一処理結果レコード３０３−２ａ等として出力する。なお、一のノードの兄弟ノードとは、一のノードの親ノードの二分木における反対側の子ノードのことである。
例えば、図７において、サーバ２００ａは、第零入力レコード３０３−１ａを入力すると、そのキー情報に基づいて、そのノードの兄弟ノードのキー情報：１、および下位にある子ノードのキー情報：００、０１からなる第一処理結果レコード３０３−２ａを出力する。なお、そのキー情報が示すノードがリーフ(子ノードを持たないノード)であった場合、兄弟ノードのキー情報のみを出力することになり、その子ノードのキー情報は出力しない。
二分木生成装置１００の処理結果収集部１０２は、各サーバ２００から出力された処理結果レコードを収集して合成することにより出力３０３−２を、第一処理結果情報として生成する。
図８は、入力３０３−１、および第一処理結果情報である入力３０３Ａに基づいた処理を示す模式図である。図８に示される通り、処理結果収集部１０２では、出力３０３−２を入力３０３Ａとして扱い、また前の処理において導出した出力３０２を入力３０３−１として扱う。そして、出力部１０３は、入力３０３−１および入力３０３Ａをそれぞれキー情報ごとのレコード単位に分割して、第一入力レコード３０３ａ、３０３ｂ１、３０３ｂ２等を生成して、キー情報に応じて、第一入力レコード３０３ａ等をサーバ２００に出力する。なお、入力３０３Ａは、キー情報のみからなるレコードとして生成される。このとき、同一のキー情報を有する入力レコードについては、それぞれの同一のサーバ２００に出力される。例えば、第一入力レコード３０３ｂ１および３０３ｂ２は、サーバ２００ｂに入力される。なお、入力３０３−１をキー情報ごとに分割したレコードを各サーバ２００に出力する際、それに応じて入力３０３Ａをキー情報ごとに分割したレコードを対応付けて、各サーバ２００に出力してもよい。すなわち、入力３０３−１に基づくレコードがないキー情報についてはサーバ２００に配布されないようにすることもできる。
【００４２】
そして、各サーバ２００において、一つの入力レコードを入力し、かつそのレコードにバリュー値として“ＵＮＤＥＲ”が付与されていた場合のみ、当該入力レコードのキー情報を処理結果レコードとして、出力する。また、キー情報のみからなる入力レコードを含んで入力した場合には、処理結果レコードを出力しない。例えば、図８においては、サーバ２００ａは、第一入力レコード３０３ａのみを入力したため、この第一入力レコード３０３ａに含まれているキー情報を第一処理結果レコード３０４ａとして出力するが、サーバ２００ｂは、第一入力レコード３０３ｂ１および３０３ｂ２の２つの入力レコードを入力した（すなわち、入力３０３Ａに基づくレコードである第一入力レコード３０３ｂ２を含んでいる）ため、第二処理結果レコードは出力しない。
【００４３】
そして、図８では、サーバ２００ａおよびサーバ２００ｄ（図示せず）は、それぞれ処理結果レコードを出力し、処理結果収集部１０２では、これを収集して合成することで、キー情報：０およびキー情報：１１からなる出力３０４（第二処理結果情報）を生成する。
【００４４】
図９は、入力３０５に基づいた処理を示す模式図である。図９において、出力３０４は、入力３０５として、二分木生成装置１００により扱われ、出力部１０３は、出力３０４をキー情報ごとのレコード単位に分けた入力レコード（第二入力レコード３０５ａ等）のそれぞれを、キー情報ごとに分けて各サーバ２００のそれぞれに出力する。
【００４５】
サーバ２００ａには、キー情報：０からなる第二入力レコード３０５ａが、サーバ２００ｂには、キー情報：１１からなる第二入力レコード３０５ｂが、それぞれ入力される。各サーバ２００では、入力されたキー情報で示されるノードの上位ノードの兄弟ノードを示すキー情報（以下、対キー情報とする）および自ノードを示すキー情報に対して、入力レコードのキー情報をバリュー値として対応付けて出力する。すなわち、当該入力レコード（第二入力レコード３０５ａ等）に記述されているキー情報である自キー情報およびキー情報で示されるノードの上位にある上位ノードの兄弟ノードを示す対キー情報に対して、それぞれ入力レコードにおけるキー情報をバリュー値として対応付けた処理結果レコード（第三処理結果レコード３０６ａ等）を生成して出力する。ただし、対キー情報が存在しない場合はレコードは出力しない。
【００４６】
図９では、サーバ２００ａへの入力レコード３０５aは”０”であり、キー情報“０”に対する上位ノードは存在しないため、サーバ２００aからは、キー情報として、自キー情報と、バリュー値としての自キー情報とからなる“０：０”からなる第三処理結果レコード３０６ａが出力される。また、サーバ２００ｂへの入力レコード３０５ｂは“１１”であり、キー情報“１１”に対する上位ノードの兄弟ノードを示すキー情報（対キー情報）は“０”であり、キー情報“０”は入力３０５に存在するため、サーバ２００ｂからは、自キー情報、対キー情報と、バリュー値としての自キー情報とからなる“０：１１”および“１１：１１”からなる第三処理結果レコード３０６ｂが出力される。
【００４７】
図９において示される通り、各サーバ２００から第三処理結果レコード３０６ａ等の処理結果レコードが出力され、処理結果収集部１０２により、処理結果レコードが収集され、出力３０６が第三処理結果情報として生成される。
【００４８】
図１０は、入力３０７に対する処理を示す模式図である。図１０において示される通り、出力３０６は、入力３０７として、二分木生成装置１００により扱われ、出力部１０３は、当該入力３０７（第三処理結果情報）をキー情報ごとのレコード単位に分けた入力レコード（第三入力レコード３０７ａ等）のそれぞれを、キー情報ごとに分けて各サーバ２００のそれぞれに出力する。
【００４９】
例えば、図１０に示される通り、二分木生成装置１００により、入力３０７がレコード単位に分割され、サーバ２００ａには、キー情報と、そのバリュー値との組み合わせである“０：０”からなる第三入力レコード３０７ａ１および“０：１１”からなる第三入力レコード３０７ａ２が入力される。また、サーバ２００ｂには、同様に“１１：１１”からなる第三入力レコード３０７ｂが入力される。
【００５０】
各サーバ２００では、その組み合わせが同じもの、すなわち、キー情報とバリュー値とが一致する場合には、ＯＫとし、不一致の場合にはＮＧを、それぞれ、バリュー値をキー情報に置き換えた形式の処理結果レコードを出力する。すなわち、各サーバ２００では、入力レコード（第三入力レコード３０７ａ１等）を入力し、当該入力レコードにおけるキー情報と、そのバリュー値との一致・不一致を示す一致情報を、キー情報と対応付けた処理結果レコードを生成して出力する。
【００５１】
例えば、図１０においては、サーバ２００ａは、“０：ＯＫ”からなる第四処理結果レコード３０８ａ１および“１１：ＮＧ”からなる第四処理結果レコード３０８ａ２を出力する。同様に、サーバ２００ｂは、“１１：ＯＫ”からなる第四処理結果レコード３０８ｂを出力する。
【００５２】
二分木生成装置１００の処理結果収集部１０２は、各サーバ２００から出力された処理結果レコードを収集して合成することにより出力３０８を、第四処理結果情報として生成する。
【００５３】
図１１は、入力３０９に対する処理を示す模式図である。  図１１において、出力３０８は、入力３０９として、二分木生成装置１００により扱われ、出力部１０３は、当該入力３０９をキー情報ごとのレコード単位に分けた入力レコード（第四入力レコード３０９ａ等）のそれぞれを、キー情報ごとに分けて各サーバ２００のそれぞれに出力する。
【００５４】
図１１に示される通り、各サーバ２００には、“０：ＯＫ”からなる第四入力レコード３０９ａが入力される。また、サーバ２００ｂには、同様に“１１：ＮＧ”からなる第四入力レコード３０９ｂ１および“１１：ＯＫ”からなる第四入力レコード３０９ｂ２が出力される。
【００５５】
各サーバ２００では、その入力レコード内における組み合わせにおいて、ＮＧを含んでいる場合、その処理結果レコードを出力せず、ＮＧを含んでいない場合には、その処理結果レコードとして、その入力レコードに含まれているキー情報のみを出力する。すなわち、一致情報がＯＫを示す入力レコードのみを入力した場合には、当該入力レコードを処理結果レコードとして出力する。
【００５６】
図１１では、サーバ２００ａにおいて、第四入力レコード３０９ａのみがＯＫであり、サーバ２００ｂにおいて、第四入力レコード３０９ｂ１がＮＧを含んでいるため、サーバ２００ａから第五処理結果レコード３１０ａが出力される。
【００５７】
そして、二分木生成装置１００は、第五処理結果レコード３１０ａを収集し、これを出力３１０とする。ここでは一つの処理結果レコードのみを取得しているため、合成処理はしていないが、複数の処理結果レコードを取得した場合には、合成処理を行うことにより、出力３１０（第五処理結果情報および特定ノード決定情報）を生成する。
【００５８】
図１２は、入力３１１に対する処理を示す模式図である。図１２において、出力３１０は、入力３１１として扱われ、二分木生成装置１００の出力部１０３は、特定ノード決定情報をキー情報ごとのレコード単位に分けた入力レコードのそれぞれを、キー情報ごとに分けて各サーバ２００のそれぞれに出力する。ここでは、第五入力レコード３１１ａのみが出力対象となるため、サーバ２００のうちの一のサーバ２００ａに、出力される。なお、サーバ２００ａに限るものではない。
【００５９】
そして、図１２に示される通り、サーバ２００ａにおいて、入力３１１に含まれているキー情報に基づいて、当該キー情報のノードの下位にある全下位ノードの下位キー情報をキー情報として、当該キー情報のノードの兄弟ノードの兄弟キー情報および当該兄弟ノードの下位にある全下位ノードの下位キー情報をバリュー値として、それぞれ対応付けを行う。なお、実際の処理としては、サーバ２００ａにおいては、キー情報および下位キー情報を抽出し、この複数の下位キー情報を構成するビット列のうち、当該キー情報のノードを示すビット列のみを反転することにより、兄弟ノードの下位ノードの下位キー情報をバリュー値として抽出することができる。
【００６０】
そして、当該第五入力レコードのキー情報で示される特定ノードの下位にある全下位ノードの下位キー情報のすべてと、当該下位キー情報のそれぞれを二進数で構成されるビット列のうち前記特定ノードを示すビットを反転した反転キー情報とを対応付けた処理結果レコード（第六処理結果レコード３１２ａ）を生成する。
【００６１】
例えば、キー情報“０”を反転すると、兄弟キー情報は、“１”となり、下位キー情報“００”のうちキー情報に該当する部分を反転すると、兄弟下位キー情報は“１０”となる。ほかのキー情報については、図１２の出力３１２に示される通りである。
【００６２】
サーバ２００ａにおいては、キー情報および下位キー情報と、兄弟キー情報およびその下位キー情報とを対応付けた第六処理結果レコード３１２ａを出力する。そして、処理結果収集部１０２は、出力３１２を統合先情報（第六処理結果情報）として生成する。
【００６３】
図１３は、入力３１３に対する処理を示す模式図である。図１３において示される通り、出力３１２は、入力３１３として、二分木生成装置１００により扱われ、初期情報３０１に記述されているキー情報ごとのレコード単位に分けた初期レコード３０１ａ等のそれぞれ、および当該統合先情報をキー情報ごとのレコード単位に分けた入力レコード（第六入力レコード３１３ａ等）のそれぞれを、キー情報ごとに分けて各サーバ２００のそれぞれに出力する。
【００６４】
図１３に示される通り、各サーバ２００において、初期レコード３０１ａ等および第六入力レコード３１３ａ等が入力された場合には、当該第六入力レコード３１３ａ等における反転キー情報をキー情報として、初期レコードのデータ数をバリュー値として対応付けた処理結果レコード（第七処理結果レコード３１４ａ）を生成し、初期レコードのみが入力された場合には、当該第初期レコードを処理結果レコード（第七処理結果レコード３１４ｂ）として、それぞれ出力する。
【００６５】
具体的には、サーバ２００ａには、第六入力レコード３１３ａおよび初期レコード３０１ａが入力される。第六レコード３１３ａは、“０：１”であり、初期レコード３０１ａは、“０：９９”である。また、サーバ２００ｂには、初期レコード３０１ｂのみが入力される。入力３１３においてキー情報“１”が存在しないため、第六入力レコード３１３ｂは入力されず、初期レコード３０１ｂである“１：１００１”が入力される。同様に、各サーバ２００には、キー情報ごとのレコード単位で、初期情報の初期レコードおよび入力３１３に基づいて生成された入力レコードが入力される。
【００６６】
そして、サーバ２００ａでは、初期レコード３０１ａと第六入力レコード３１３ａとの両方が入力されるため、初期レコード３０１ａにおけるバリュー値（：９９）と、第六入力レコード３１３ａのキー情報（：１）とを対応付けした第七処理結果レコード３１４ａを出力する。そして、二分木生成装置１００において、これら第七処理結果レコード３１４ａ等を収集して合成することで、出力３１４を第七処理結果情報として生成する。
【００６７】
図１４は、入力３１５に対する処理を示す模式図である。図１４において、出力３１４は、入力３１５として、二分木生成装置１００により扱われ、当該入力３１５を、キー情報ごとのレコード単位に分けた入力レコード（第七入力レコード３１５ａ１等）のそれぞれを、キー情報ごとに分けてサーバ２００のそれぞれに出力する。このとき同一のキー情報を有する入力レコードについては、同じサーバ２００に出力する。図１４に示される通り、各サーバ２００において、入力した入力レコードに含まれているデータ数を集計することで、当該キー情報に対応するデータ数を算出して、これを最終処理結果レコードとして出力する。
【００６８】
例えば、サーバ２００ａには、第七入力レコード３１５ａ１および第七入力レコード３１５ａ２が入力され、サーバ２００ｂには、第七入力レコード３１５ｂ１および第七入力レコード３１５ｂ２が入力される。ほか同様に、サーバ２００ｘには、第七入力レコード３１５ｘ１および第七入力レコード３１５ｘ２が入力される。そして、第七入力レコード３１５ａ１は、“１：９９”であり、第七入力レコード３１５ａ２は、“１：１００１”である。そして、サーバ２００ａにおいて、第七入力レコード３１５ａ１および第七入力レコード３１５ａ２のバリュー値を加算し、最終処理結果レコード３１６ａを出力する。この最終処理結果レコード３１６ａは、“１：１１００”である。ほか同様に、各サーバ２００は、最終処理結果レコード３１６ｂ〜３１６ｘを出力し、二分木生成装置１００は、これら最終処理結果レコードを収集して合成して出力３１６を、最終処理結果情報として出力する。
【００６９】
なお、図１４における出力３１６の例示では、キー情報：１１０に対応するバリュー値が“１１”となり、所定条件（１００以上）を満たしていない。よって、こういった場合には、再度、図６から図１４に示される処理を繰り返す。なお、その際、図６に示す処理の入力としては初期情報３０１の代わりに図１４の処理の出力３１６を用いる。
【００７０】
そして、二分木生成装置１００における二分木生成部１０４は、所定条件を満たした最終処理結果情報に基づいて二分木を生成する。
【００７１】
つぎに、本実施形態の分散生成処理システムの作用効果について説明する。本実施形態の分散生成処理システムにおいて、二分木生成装置１００は、初期情報のキー情報ごとに分けて当該初期情報を各サーバ２００に出力し、それぞれのサーバ２００では、入力した初期情報におけるデータ数が所定条件を満たさないノードに基づいて、初期情報におけるデータ数が所定条件を満たさない最上位のノードを特定ノードとして抽出し、当該特定ノードのキー情報を特定ノード決定情報として出力する。
【００７２】
そして、二分木生成装置１００では、特定ノード決定情報に基づいて、キー情報と統合先キー情報とからなる統合先情報を各サーバ２００に出力する。
【００７３】
そして、各サーバ２００において、統合先情報に基づいて、初期情報におけるキー情報ごとのデータ数を、当該キー情報に対応する統合先キー情報のデータ数に集計して、統合先キー情報ごとのデータ数を算出する。
【００７４】
二分木生成装置１００は、これら各サーバ２００から算出されたデータ数を収集して、これに基づいて所定条件を満たした二分木を生成する。
【００７５】
これにより、各情報処理装置において、分散処理をすることにより特定ノードの決定、統合先の決定をおこなって、これらに基づいて二分木を生成することができる。
【符号の説明】
【００７６】
１００…二分木生成装置、１０１…仮二分木生成部、１０２…処理結果収集部、１０３…出力部、１０４…二分木生成部、１０５…二分木生成元情報記憶部、２００…サーバ、２０１…入力部、２０２…情報処理部、２０３…出力部、３０１…初期情報、３０１ａ…初期レコード、３０１ｂ…初期レコード、３０２…出力、３０３…入力、３０３ａ、３０３ｂ１…第一入力レコード、３０４…出力、３０４ａ…第一処理結果レコード、３０５…入力、３０５ａ…第二入力レコード、３０５ｂ…第二入力レコード、３０６…出力、３０６ａ、３０６ｂ…第三処理結果レコード、３０７…入力、３０７…入力、３０７ａ、３０７ａ１、３０７ａ２、３０７ｂ…第三入力レコード、３０８…出力、３０８ａ１…第四処理結果レコード、３０８ａ２、３０８ｂ…第四処理結果レコード、３０９…入力、３０９ａ、３０９ｂ１、３０９ｂ２…第四入力レコード、３１０…出力、３１０ａ…第五処理結果レコード、３１１…入力、３１１ａ…第五入力レコード、３１２…出力、３１２ａ…第六処理結果レコード、３１３…入力、３１３ａ、３１３ｂ…第六入力レコード、３１４…出力、３１４ａ、３１４ｂ…第七処理結果レコード、３１５…入力、３１５ａ１、３１５ａ１、３１５ａ２、３１５ｂ１、３１５ｂ２、３１５ｘ１、３１５ｘ２…第七入力レコード、３１６…出力、３１６ａ…最終処理結果レコード。
【図１】
0005819235.tif 000002
【図２】
0005819235.tif 000003
【図３】
0005819235.tif 000004
【図４】
0005819235.tif 000005
【図５】
0005819235.tif 000006
【図６】
0005819235.tif 000007
【図７】
0005819235.tif 000008
【図８】
0005819235.tif 000009
【図９】
0005819235.tif 000010
【図１０】
0005819235.tif 000011
【図１１】
0005819235.tif 000012
【図１２】
0005819235.tif 000013
【図１３】
0005819235.tif 000014
【図１４】
0005819235.tif 000015