(57)【特許請求の範囲】
【請求項１】
それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方式において、
アイテム１個ずつを対象とする時は、各トランザクションに含まれるアイテム１個ずつをレコードとして記憶装置に格納し、ｉ（≧２）個のアイテムの組み合わせを対象とする時は、該ｉ個のアイテムの組み合わせに含まれるアイテムの部分的組み合わせまたはアイテム１個ずつのうちで、前記出現回数が与えられた条件に適合するアイテムの部分的組み合わせまたはアイテム１個ずつに含まれるアイテムに対応した制約条件であって、（ｉ−１）個のアイテムの組み合わせを対象とした処理において生成され、メモリに格納されているビットマップとしての組み合わせ生成制約条件に適合するアイテムの組み合わせのみを生成して、該組み合わせをレコードとして記憶装置に格納する組み合わせ生成手段と、
該記憶装置に格納されたレコードとしてのアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションにおける出現回数をカウントして、該アイテム１個ずつまたは２個以上のアイテムの組み合わせとしてのレコードと該出現回数とを合わせて、結果レコードとして出力する出現回数カウント手段と、
該出現回数カウント手段が出力するアイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで出現回数が与えられた条件に適合するものを選択する組み合わせ選択手段と、
該組み合わせ選択手段の選択結果に対応して、前記組み合わせ生成制約条件としてのビットマップを生成して前記メモリに格納する制約条件生成手段とを備えることを特徴とする相関のあるデータ組み合わせの数え上げ方式。
【請求項２】
前記制約条件生成手段が、前記組み合わせ選択手段による（ｉ−１）個のアイテムの組み合わせに対する選択結果としてのアイテム１個ずつ、または２個以上のアイテムの組み合わせあるいは部分的組み合わせに含まれるアイテムに対応したビット位置に“１”を立てたビットマップを、前記組み合わせ生成制約条件として生成して前記メモリに格納し、前記組み合わせ生成手段がｉ（≧２）個のアイテムの組み合わせの生成にあたって、該ビットマップ上で“１”が立っているビット位置に対応するアイテムの組み合わせのみを生成することを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項３】
前記組み合わせ生成手段が、前記トランザクションに含まれるアイテム以外に、アイテムの階層構造においてトランザクションに含まれる他のアイテムの親のアイテムを含めて、アイテムの組み合わせまたはアイテム１個ずつをレコードとして前記記憶装置に格納することを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項４】
前記組み合わせ生成手段が、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、該シーケンスにおける順序を維持した形式で、アイテムの組み合わせを生成し、レコードとして前記記憶装置に格納することを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項５】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によって該記憶装置上に出力されたハッシュ済レコードのリストを読み込み、該リストのレコードをキー値に従ってソートし、該ソート済レコードのリストに対してグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段とを備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項６】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されるハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置上で必ずしも連続でない領域に出力するハッシュ済レコード出力手段とを備えることを特徴とする請求項１記載の相関のあるデータ組み合わせ数え上げ方式。
【請求項７】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られ、前記記憶装置上で必ずしも連続でない領域に格納されたハッシュ関数値に対応したレコード列としてのハッシュ済リストと、該ハッシュ関数値に対応して格納された複数のレコードからなるブロック内のレコードを、ハッシュ関数値により検索可能とするための補助情報のリストとを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項８】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置上で必ずしも連続でない領域に出力する手段であって、前記レコード格納手段から前記ハッシュ関数値に対応して出力された複数のレコードを１つのブロックとして、該１つのブロックが前記記憶装置上で連続した領域に格納される形式で出力するハッシュ済レコード出力手段と、
該ブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを格納する補助情報リスト格納手段と、
前記ハッシュ関数値に対応して前記ハッシュ済レコード出力手段によって出力されたハッシュ済レコード列と、前記補助情報リスト格納手段に格納されている補助情報のリストとを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段とを備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項９】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段とを備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１０】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られるハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ハッシュ関数値に対応したレコードの格納にあたりハッシュ関数値を最小値から最大値まで連続的に変化させる間に格納されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１１】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うめたに、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
該ハッシュ済レコード出力手段によって出力されたレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ラン情報格納手段に格納されているラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１２】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力する手段であって、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードを該記憶装置上の連続領域に出力すると共に、異なるランのレコードは必ずしも互いに連続でない領域に格納するハッシュ済レコード出力手段と、
該ランのそれぞれに含まれるレコードの該記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
該ハッシュ済レコード出力手段によって出力されたレコードが該記憶装置上で格納されているハッシュ済レコード列の内容と、該ラン情報格納手段に格納されているラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１３】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置上で必ずしも連続でない領域に出力する手段であって、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域であって、相互に非連続である領域に格納される時、該２つのブロックの連結関係を示すデータを加えてレコードの出力を行うハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段とを備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１４】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られるハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ハッシュ関数値に対応したレコードの該記憶装置への出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報と、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域に格納され、該２つの連続領域が相互に非連続となっているとき、該２つのブロックの連結関係を示すデータとに基づいてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１５】
前記出現回数カウント手段が、前記記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置上で必ずしも連続でない領域に出力する手段であって、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域であって、相互に非連続である領域に格納される時、該２つのブロックの連結関係を示すデータを加えてレコードの出力を行うハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
前記ハッシュ済レコード出力手段によって出力され、ハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、前記ラン情報格納手段に格納されているラン情報と、前記２つのブロックの連結関係を示すデータとに基づいてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする請求項１記載の相関のあるデータ組み合わせの数え上げ方式。
【請求項１６】
それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げを行う計算機によって使用される記憶媒体であって、
１個ずつのアイテムを対象とする時は各トランザクションに含まれるアイテム１個ずつをレコードとして記憶装置に格納し、ｉ（≧２）個のアイテムの組み合わせを対象とする時は、該ｉ個のアイテムの組み合わせに含まれるアイテム１個ずつまたはアイテムの部分的組合わせのうちで、前記出現回数が与えられた条件に適合するアイテムの部分的組み合わせまたはアイテム１個ずつに含まれるアイテムに対応した制約条件であって、（ｉ−１）個のアイテムの組み合わせを対象とした処理において生成され、メモリに格納されているビットマップとしての組み合わせ生成制約条件に適合するアイテムの組み合わせのみを生成して、該組み合わせをレコードとして記憶装置に格納する組み合わせ生成機能と、
該記憶装置に格納されたレコードとしてのアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントして、該アイテム１個ずつまたは２個以上のアイテムの組み合わせとしてのレコードと該出現回数とを合わせて、結果レコードとして出力する出現回数カウント機能と、
該出現回数カウント機能が出力するアイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで出現回数が与えられた条件に適合するものを選択する組み合わせ選択機能と、
該組み合わせ選択機能の選択結果に対応して、前記組み合わせ生成制約条件としてのビットマップを生成して前記メモリに格納する制約条件生成機能とを計算機に実行させるためのプログラムを格納した計算機読出し可能記憶媒体。
【請求項１７】
それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中で出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方法において、
各トランザクションに含まれるアイテムを１個ずつ検出して、該検出されたアイテムをレコードとして記憶装置に格納し、
該検出され、該記憶装置に格納された１個ずつのアイテムの全トランザクションでの出現回数をカウントし、
該カウント回数が与えられた条件に適合するアイテムを選択して、該アイテムと該カウント回数との組を数え上げ結果として出力し、
該選択されたアイテムに対応したビット位置に“１”をセットしたビットマップを作成してメモリに格納し、
組み合わせ内のアイテムの個数を示すｉの値をｉ＝２とし、
前記メモリに格納されたビットマップに“１”が立っている位置に対応するアイテムを用いて、各トランザクションに含まれるｉ個のアイテムの組み合わせを生成して、該組みあわせをレコードとして前記記憶装置に格納し、
該生成され、該記憶装置に格納されたアイテムの組み合わせの全トランザクションでの出現回数をカウントし、
該カウント回数が与えられた条件に適合するアイテムの組みあわせを選択して、該アイテムの組み合わせと該カウント回数との組を数え上げ結果として出力し、
該選択されたアイテムの組み合わせあるいは部分的組み合わせ、または該組み合わせに含まれるアイテム１個ずつに対応したビット位置に“１”をセットしたビットマップを作成して前記メモリに格納し、
ｉの値をインクリメントして前記ｉ個のアイテムの組み合わせの生成以降の処理を繰り返すことを特徴とする相関のあるデータ組み合わせの数え上げ方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般的にはデータベースなどに記録された大量のデータのデータ処理に係り、まず第一にグループバイ処理に関し、第二にデータベースマイニングに関する。
【０００２】
本発明は、第一に、各レコードが持つキーの値に応じて大量のレコードを分類し、等しいキーの値を持つレコード群に対して、例えば平均値を求めるなど、指定された演算を行う処理、すなわちグループバイ処理に関し、更に詳しくはハッシュ処理に基づくグループバイ処理、すなわちキーの値に対して適切なハッシュ関数を適用して得られるハッシュ値に従って大量のレコードをハッシュしてハッシュ済みのレコードリストを作成し、そのハッシュ済みレコードリストをキーの値に従ってソートして、その結果でき上るソート済みレコードリストに対してグループバイ処理を行う、ハッシュ処理に基づくグループバイ処理方式に関する。
【０００３】
本発明は、第二に、データベースに記録されたデータの間の関連規則を発見するデータベースマイニングに関する。更に詳しくは、本発明はデータベースの中の膨大なデータのうちで相関のあるデータの組み合わせの出現回数を数え上げる方式に関し、この方式を用いて数え上げられた結果から、与えられた条件に適合する組み合わせとその出現回数を用いて、データマイニング手法の中の１つである相関ルールの生成処理が行われる。相関ルールを用いた相関分析は、近年米国を中心として広く注目されている。
【０００４】
【従来の技術】
一般にグループバイ処理における演算、すなわち等しいキーの値、例えばアイテム番号を持つレコード群に対する演算としては、アイテムセットのようなレコードの数を数えるカウント処理や、それらのレコード群の特定のフィールドの値の合計や平均を計算する演算などがある。このようなグループバイ処理は、関係データベースの処理や、統計処理などにおいて頻繁に行われるものである。
【０００５】
グループバイ処理方式としては、ソート処理に基づくものと、ハッシュ処理に基づくものとが知られている。ソート処理に基づく方式は、レコード群をキーの値に従ってソートすることによって、同一のキーの値を持つレコードが連続してアクセス可能となることを利用するものである。すなわち、まずレコード群をキーの値に従ってソートし、その結果できあがるソート済のレコードリストを頭からたどって、同一のキー値が続く限り指定された演算の実行を繰り返し、キーの値が変化した時点で演算の初期化を行う。
【０００６】
ハッシュ処理に基づく方式は、レコード群をキーの値に従ってハッシュすることによって、同一のキーの値を持つレコードが１つのハッシュバケットに集まることを利用するものである。すなわち、まずキーの値に対して適切なハッシュ関数を適用することによって得られるハッシュ値に従ってレコード群をハッシュし、その結果できあがるハッシュバケット毎に含まれているレコードをキーの値に従ってソートし、ソート済のレコードリストを作成して、そのソート済レコードリストにおいて同一のキー値が続く限り、指定された演算の実行を繰り返し、キーの値が変化した時点で演算の初期化を行う。
【０００７】
図１６４はソート処理に基づくグループバイ処理方式の従来例のフローチャートである。同図において処理が開始されると、まずステップＳ２０１でグループバイ対象レコード群がキー値によってソートされ、ステップＳ２０２でソートされたレコード群の先頭のレコードが読み出され、ステップＳ２０３で関数の初期化が行われ、ステップＳ２０４で読み出されたレコードに関して関数の演算が実行され、ステップＳ２０５でソートされたレコード群の中にまだレコードが存在するか否かが判定される。
【０００８】
まだレコードが存在する場合には、ステップＳ２０６でソートされたレコード群の先頭が読み出され、ステップＳ２０７でそのレコードのキーの値が先立つレコード、すなわちその前に読み出されたレコードのキーの値と等しいか否かが判定され、等しい場合にはステップＳ２０４以降の処理が繰り返される。
【０００９】
先立つレコードのキーの値と等しくない時にはステップＳ２０８で関数の終了処理が行われ、ステップＳ２０９で先立つレコードと関数の処理結果を合わせたものが結果レコードとして出力された後に、ステップＳ２０３以降の処理が繰り返される。
【００１０】
ステップＳ２０５でソートされたレコード群のレコードが全てすでに読み出されていると判定されると、ステップＳ２１０で関数の終了処理が行われ、ステップＳ２１１で先立つレコードと関数の処理結果とを合わせたものが結果レコードとして出力されて、処理を終了する。
【００１１】
図１６５は、図１６４のフローチャートを用いて実行されるグループバイ処理の経過を示す具体例である。同図（１）に示すように、グループバイ対象レコード群は１０個のレコードからなり、簡単のためにここでは各レコードはキー値、例えば１つのアイテムの番号のみからなるものとする。ステップＳ２０１の処理が済むと、図１６５（２）の状態が実現される。
【００１２】
ここでは、グループバイ処理の演算としては同一キー値を持つレコードの数を求めるカウント処理を行うものとし、ステップＳ２０２とＳ２０３の処理が終了すると（３）に示す状態となる。すなわちＳ２０３の関数の初期化では、カウント値が０にリセットされることになる。
【００１３】
ステップＳ２０４ではカウント値が１だけインクリメントされ、（４）の状態となる。ステップＳ２０５の判定はここではＹＥＳとなり、ステップＳ２０６で現在のレコード“１”が先立つレコードとされ、新しいレコード、すなわち“１”が現在のレコードとなる。そしてステップＳ２０７の判定はＹＥＳとなり、ステップＳ２０４でカウント値がインクリメントされて（５）に示す状態となる。
【００１４】
ステップＳ２０５の判定は再びＹＥＳとなり、ステップＳ２０６で新しいレコードが読み込まれる。このレコードのキーの値は２であり、先立つレコードのキーの値１とは異なるため、ステップＳ２０８で関数の終了処理が行われる。カウント演算の場合には、終了処理は単に現在のカウントの値を固定するだけであり、ステップＳ２０９ではこの固定された値が関数の処理結果とされ、先立つレコード、ここでは“１”と合わされて結果レコードとして出力される。すなわち出力される結果レコードは“１，２”である。図１６５（６）はこの結果を示す。
【００１５】
同様に処理を実行することによって最終的には処理結果として次のレコード群が得られる。
１，２
２，２
３，３
４，１
５，２
この結果はグループバイ対象レコード群の中にキーの値として１を持つものが２個、２を持つものが２個、３を持つものが３個、４を持つものが１個、５を持つものが２個あったことを示す。
【００１６】
図１６６はハッシュ処理に基づくグループバイ処理方式のフローチャートの従来例である。同図を図１６４に示したソート処理に基づくフローチャートと比較すると、まずステップＳ２２１でグループバイ対象レコード群がキー値によりハッシュされ、ステップＳ２２２で各ハッシュバケット内のレコードがキー値によりソートされ、全てのソートされたハッシュバケットの内容が結合され、１つの列が作られた後に、図１６４のステップＳ２０２以降の処理と実質的に同一の処理がステップＳ２２３〜Ｓ２３２において実行される。
【００１７】
図１６７は、図１６６のフローチャートを用いて実行される処理の経過の具体例である。グループバイ対象レコード群は図１６５におけると同じである。ハッシュ処理に基づく場合には、まずグループバイ対象レコード群が適当なハッシュ関数を用いてハッシュされる。ここではハッシュ関数としてｍｏｄ３を使うことにする。すなわちキーの値を３で割り、余りの値に応じてハッシュバケットに振り分ける処理が行われる。余りがｉであればハッシュバケットｉにそのレコードは格納される。ここでは余りの値としては０，１、および２の３種類があり、従ってハッシュバケットは３つとなる。
【００１８】
図１６６のステップＳ２２１の処理が実行され、ハッシュが終わった状態が図１６７の（２）である。各ハッシュバケット内のレコード群をキーの値によってソートした結果が（３）、全てのハッシュバケットの内容を１つの列にまとめた結果が（４）であり、ステップＳ２２２までの処理が終了する。以後の処理はソート処理に基づく場合と同じである。最終的に結果レコード群として次のレコードが得られる。
【００１９】
３，３
１，２
４，１
２，２
５，２
図１６５の場合とはレコードの出現順序が異なっているが、集合全体としてはソート処理に基づく場合と同一の結果が得られる。
【００２０】
次に本発明におけるデータ組み合わせの数え上げ方式に関する従来技術について説明する。このデータ組み合わせの数え上げは前述のデータベースマイニングにおける相関ルール生成処理の一部を成すものであるため、まず相関ルールについて説明する。なお後述するように本発明におけるデータ組み合わせの数え上げでは、その処理の一部として本発明のグループバイ処理方式が用いられる。
【００２１】
例として小売業においてＰＯＳ（Ｐｏｉｎｔ−Ｏｆ−Ｓａｌｅｓ）  で収集した  １００人の顧客のレシートのうち、２０人の顧客が商品Ａを購入し、また、１２人の顧客が商品Ａと商品Ｂの両方を購入しているとする。１つの商品をアイテムと呼び、また、１枚のレシートをトランザクションと呼ぶ。１つのトランザクションには、通常、複数のアイテムが含まれる。このとき、以下の定義式
アイテムのサポート＝アイテムを含むトランザクションの数／全トランザクション数
に基づいて商品Ａの「サポート」＝２０％、  商品Ａと商品Ｂの「サポート」＝１２％となる。さらに、単純な条件付き確率計算により、「Ａを購入する顧客の６０％（１２％／２０％）がＢも購入する」と結論できる。これを「Ａ→Ｂ  確信度６０％、サポート１２％」と表わし、相関ルールと定義する。つまり、相関ルール「Ａ→Ｂ」における確信度は、
「Ａ→Ｂ」の確信度＝Ａ∧Ｂ（ＡとＢの両方購入）のサポート／Ａのサポートである。さらに、Ａ→Ｂといった単純なルールだけでなく、Ａ∧Ｂ→Ｃ∧Ｄ∧Ｅ（「ＡとＢを購入する顧客がＣとＤとＥを購入する」）の様な複雑なルールも用いられる。この場合の確信度は、
「Ａ∧Ｂ→Ｃ∧Ｄ∧Ｅ」の確信度＝Ａ∧Ｂ∧Ｃ∧Ｄ∧Ｅのサポート／Ａ∧Ｂのサポート
である。
【００２２】
相関ルールは、目玉商品がどの商品群の売り上げに貢献したかの評価、棚割り（どの商品とどの商品を近くに並べるべきか）の最適化や、クレジットカードのデータからダイレクトメールのヒット率を高めるといった、様々な局面に有効な情報である。
【００２３】
相関ルール生成処理は、（１）  トランザクションの中から、与えられたサポートの条件を満たすアイテムの組み合わせの出現回数を数え上げる処理と、（２）  （１）  で求められた組み合わせ群とその出現回数を基に、ルールとそのサポートおよび確信度の計算を行うという２つの段階からなる処理からなる。本発明は、（１）  の数え上げ処理の効率化を行うものである。
【００２４】
（１）  において、与えられたサポートの条件を満たすアイテムの組み合わせ群を「ラージアイテムセット」と呼ぶ。サポートの条件としては、最小値（０％〔＝すべての組み合わせを数える〕〜  １００％〔＝全部のトランザクションで購入されたアイテムを数える〕）から、最大値（最小値＜＝最大値＜＝  １００％）の範囲であたえる。従来では、多くの場合、最大値を  １００％に固定する手法が用いられている。
【００２５】
（１）  のラージアイテムセットの数え上げ処理は非常に時間のかかる処理であるため、各種の高速化手法が提案されている。中でも、ＳＱＬに基づくＳＥＴＭアルゴリズムと、ＩＢＭが提案するいくつかのアルゴリズム中のＡｐｒｉｏｒｉ  が代表的なものとして知られている。ＳＥＴＭアルゴリズムは次の文献１、Ａｐｒｉｏｒｉ  のアルゴリズムは次の文献２に述べられている。
【００２６】
文献１：Ｍａｕｒｉｃｅ  Ｈｏｕｔｓｍａ  ａｎｄ  Ａｒｕｎ  Ｓｗａｍｉ．  Ｓｅｔ−Ｏｒｉｅｎｔｅｄ  Ｍｉｎｉｎｇ  ｆｏｒ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ  ｉｎ  Ｒｅｌａｔｉｏｎａｌ  Ｄａｔａｂａｓｅｓ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ，  ｐａｇｅｓ  ２５−３３，  １９９５．  文献２：Ｒａｋｅｓｈ  Ａｇｒａｗａｌ  ａｎｄ  Ｒａｍａｋｒｉｓｈｎａｎ  Ｓｒｉｋａｎｔ．  Ｆａｓｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｉｎｉｎｇ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ，  ｐａｇｅｓ  ４８７−４９９，  Ｓａｎｔｉａｇｏ，  Ｃｈｉｌｅ，  １９９４．
ＳＥＴＭに基づく相関ルール生成処理は、関係データベース問い合わせ言語であるＳＱＬ言語をベースとしており、実装が容易である特徴を持つ。処理にあたっては、ＳＱＬの結合演算（Ｊｏｉｎ  Ｏｐｅｒａｔｉｏｎ）とグループバイ演算（ＧｒｏｕｐＢｙ  Ｏｐｅｒａｔｉｏｎ  ）を用いる。サポートの最小値の条件を満たす長さｋ−１のアイテムの組み合わせを含むトランザクションのテーブルを用いた自己結合演算を行い、長さｋのアイテムの組み合わせ候補を生成する。次に、グループバイ演算を用いて、長さｋのラージアイテムセットを数え上げる。さらに、結合演算を用いてサポートの最小値を満足するトランザクション群を生成し、次の長さｋ＋１のアイテムの組み合わせ生成に利用する。
【００２７】
図１６８は、ＳＥＴＭにおける具体的な処理の流れの説明図であり、図１６９はＳＥＴＭの処理における各機能ブロックの処理内容を示す図である。これらの図を用いて、従来技術としてのＳＥＴＭの処理について詳細に説明する。
【００２８】
図１６８において、テーブルＲ１′は各トランザクションｔ ｘに含まれるアイテムを示している。例えばトランザクション１にはアイテム１，２、および３が含まれていることが示されている。ＧＢ（１）は１個ずつのアイテムの出現回数のカウント処理（グループバイ処理）を行うものであり、テーブルＬ１はそのカウント結果を、カウント数が２以上のアイテムに対して示したものである。
【００２９】
テーブルＲ１は、ジョインの処理（結合処理）Ｊ（１）によって、テーブルＲ１′に含まれるデータのうちでテーブルＬ１に存在するアイテムだけを抜き出した結果を示す。
【００３０】
ＳＪ（１）は、テーブルＲ１に対するセルフジョインの処理を示し、その結果テーブルＲ２′として、各トランザクションに対して２つのアイテムの可能な組み合わせが生成される。
【００３１】
グループバイ処理ＧＢ（２）によって、２つのアイテムの組み合わせの出現回数がテーブルＲ２′の組み合わせに対してカウントされ、そのカウント結果のうちでカウント数が２以上のものがテーブルＬ２として作成される。
【００３２】
以下同様にして、３つのアイテムの組み合わせのうちでカウント数が２以上のもののテーブルＬ３が作られ、またアイテムが４個の組み合わせのうちでカウント数が２以上のものがテーブルＬ４として作られるが、テーブルＬ４の内容は空となる。
【００３３】
Ａｐｒｉｏｒｉ  アルゴリズムでは、サポートの最小値の条件を満たす長さｋ−１のラージアイテムセットを用いて長さｋのアイテムの組み合わせの候補を生成する。その際に、ｋ−１のラージアイテムセットがすべてメモリにのる場合、長さｋのアイテムの組み合わせの中の、長さｋ−１のすべての組み合わせがラージアイテムセットに含まれているかをチェックし、含まれている場合のみ、長さｋのアイテムの組み合わせの候補とみなす。長さｋ−１のアイテムの組み合わせをメモリ上のハッシュ表（Ｈａｓｈ  Ｔａｂｌｅ）に登録しておくことにより、不必要な候補を効率よくプルーニング（Ｐｒｕｎｉｎｇ  ）する。さらに、候補であるアイテムの組み合わせ群をハッシュ木（Ｈａｓｈ  Ｔｒｅｅ  ）に保持し、各トランザクション毎にトランザクション中に含まれるアイテムの組み合わせがハッシュ木に登録されている場合、そのカウント値を増やすことにより、長さｋのアイテムの組み合わせの候補の出現回数を数え上げる。ハッシュ木に登録されている組み合わせのみを対象とすることにより、不必要な組み合わせの数え上げをしない工夫がなされている。
【００３４】
図１７０は、Ａｐｒｉｏｒｉ  アルゴリズムによる処理の具体例、図１７１はＡｐｒｉｏｒｉ  アルゴリズムの処理における各機能ブロックの内容の説明図である。これらの図に基づいて、Ａｐｒｉｏｒｉ  アルゴリズムによるラージアイテムセットの数え上げ処理の具体例について説明する。
【００３５】
図１７０において、８つのトランザクションのリストＴＬの内容は実質的に図１６８と同じである。まず最初にこれらのトランザクションに含まれるアイテムが１つずつＳｕｂｓｅｔ（１）に入力され、１つ１つのアイテムの出現回数がＣ１としてカウントされる。そのカウント結果はＦに入力され、出現回数が２回以上のものがフィルタリングによって選択され、フィルタリング結果がＬ１として作成される。
【００３６】
Ｌ１の中に含まれるアイテムから２個の組み合わせが選択され、Ｃ２としてハッシュ木に登録される。そして各トランザクションの中にハッシュ木に登録された２個のアイテムの組み合わせが含まれている場合、Ｓｕｂｓｅｔ（２）によってその出現回数をカウントすることによって、２個のアイテムの組み合わせの出現回数が求められ、その結果がＦによってフィルタリングされることにより、２個のアイテムの組み合わせのうちで出現回数が２回以上のものがＬ２として得られる。
【００３７】
以下同様の処理を実行することによって、３個のアイテムの組み合わせのうちで出現回数が２回以上のものがＬ３として得られ、また４個の組み合わせのうちで出現回数が２回以上のものが、図１６８と同様に、存在しないことが判明した時点で処理を終了する。
【００３８】
【発明が解決しようとする課題】
まず最初に、グループバイ処理方式に関する従来技術の問題点を説明する。前述のようにグループバイ処理方式としてはソート処理に基づくものとハッシュ処理に基づくものとがあるが、ソート処理に基づく場合にはレコード群の全体を一度にソートする必要があり、このソートのために処理時間およびコストが大きくなるという問題点があった。
【００３９】
これに対してハッシュ処理に基づく場合には、ソートの処理は各ハッシュバケットに含まれるレコードの集合に対してのみ行われるために、ソート処理に基づく方式よりもコストは小さくなる。しかしながら、グループバイ処理対象レコード群全体のサイズが主記憶の上に乗り切らないほど大きい場合には、ハッシュバケットを二次記憶装置に書き出し、また書き出されたハッシュバケットを読み込む必要があり、二次記憶装置に対するアクセスに大きなコストがかかるという問題点があった。
【００４０】
すなわち従来のハッシュ方式では、例えば主記憶上にそれぞれのハッシュバケットに１対１に対応するレコードバッファを設け、ハッシュ対象レコードに対するハッシュ値に基づいてレコードをそれぞれのレコードバッファに格納し、ある１つのレコードバッファが一杯になった時点で、二次記憶装置上でそれぞれのレコードバッファに１対１に対応するハッシュバケット格納領域の１つにそのレコードバッファの内容を出力するような動作が行われる。それぞれのレコードバッファの大きさは一般にそれほど大きく取ることはできないため、各レコードバッファが一杯になるたびに二次記憶装置へのレコードの書き出しが行われる。このようにして二次記憶装置上にハッシュバケットが作られても、各ハッシュバケットの大きさがそれぞれ異なるため、二次記憶装置上での各ハッシュバケットの格納領域は全体として非連続の領域となる。一般に二次記憶装置として使われるディスク装置では、連続領域に対するアクセスよりも小さな飛び飛びの領域に対する非連続的なアクセスの方が時間がかかり、コストが大きくなってしまうという問題点があった。
【００４１】
次に、従来の相関ルール生成処理としてのＳＥＴＭアルゴリズムと、Ａｐｒｉｏｒｉ  アルゴリズムの問題点について説明する。ＳＥＴＭに基づく相関ルール生成処理では、最初の結合演算処理において、不必要な組み合わせをプルーニングする手段がないため、続くグループバイ演算処理が必要以上に重い処理となる問題点があった。
【００４２】
Ａｐｒｉｏｒｉ  アルゴリズムでは、ＳＥＴＭアルゴリズムに見られる問題点を解消する工夫がなされている。すなわち、サポートの最小値を満たす長さｋ−１のラージアイテムセットから長さｋのアイテムの組み合わせの候補を生成する際に、長さｋ−１のラージアイテムセットをハッシュ表に登録しておき、不必要な候補を生成しないようにプルーニングを行う。しかし、ハッシュ表がメモリ上に載らない場合には、プルーニングを行うことが出来ないことや、ｋ＝２においては長さ１のジョインの計算をしなければならず非常に重い処理となるという問題点があった。
【００４３】
さらに、Ａｐｒｉｏｒｉ  アルゴリズムではアイテムの組み合わせの数え上げを行う際に、アイテムの組み合わせ候補をハッシュ木に保持しておいてトランザクションをスキャンする。このため、ハッシュ木のすべてのアイテムの組み合わせ候補がメモリに載らない場合には、ハッシュ木を実メモリ上に載る大きさ毎に読み込んで処理を行うため、そのたびにトランザクションをスキャンし直さなければならず、大きなトランザクションの際には処理に非常な時間がかかるという問題点があった。
【００４５】
本発明の課題は、従来のApriori アルゴリズムにおけるハッシュ木のような、そのサイズが利用できるメモリ量を超える可能性があり、しかも、超えた場合には機能しなくなるプルーニング手段に代えて、常に利用できるメモリ量にフィットさせることのできるビットマップを用いることにより、不必要なアイテムの組み合わせ候補を効率的にプルーニングし、更にアイテムセットを数え上げるグループバイ処理を従来技術に比較して高速化することにより、相関のあるデータ組み合わせの数え上げを効率的に実行することである。
【００４６】
【課題を解決するための手段】
図１は本発明におけるグループバイ処理方式の原理構成を示すブロック図である。同図はレコード群を、各レコードのキー値に対応するハッシュ関数値を用いて参照可能な格納形式に変換するためのハッシュ処理の結果に基づいて、該レコード群に対するグループバイ処理を行うグループバイ処理方式の原理構成ブロック図である。
【００４７】
図１においてレコード格納手段１０６は、例えばレコードバッファであり、グループバイ処理の対象となるレコード群を一時的に格納するものである。またハッシュ値対応ポインタ格納手段１０７は、例えばハッシュ表であり、レコード格納手段１０６に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するものである。
【００４８】
ハッシュ済レコード出力手段１０８は、ハッシュ値対応ポインタ格納手段１０７に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置に出力するものである。
【００４９】
グループバイ処理実行手段１０９は、ハッシュ済レコード出力手段１０８によって前記記憶装置上に出力されたハッシュ済レコードのリストを読み込み、該リストのレコードをキー値に従ってソートし、該ソート済のレコードリストに対してグループバイ処理を実行するものである。
【００５０】
本発明におけるグループバイ処理方式においては、図１の構成手段に加えて、例えば更に補助情報リスト格納手段を備えることができる。この補助情報リストは、ハッシュ済レコード出力手段１０８が、レコード格納手段１０６からハッシュ関数値に対応して出力された複数のレコードを１つのブロックとして、前記記憶装置に出力する場合に、そのブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを格納するものである。
【００５１】
この場合には、グループバイ処理実行手段１０９は、ハッシュ処理の結果として得られるハッシュ関数値に対応したレコード列としてのハッシュ済リスト、ハッシュ関数値に対応して出力される複数のレコードからなるブロック内のレコードをハッシュ関数値により検索可能とするための補助情報のリストとを用いて、グループバイ処理を実行する。
【００５２】
また本発明におけるグループバイ処理方式においては、前述の補助情報リスト格納手段の代わりに、ラン情報格納手段を備えることもできる。このラン情報格納手段は、レコード出力手段１０８がレコード格納手段１０６から前記ハッシュ関数値に対応して出力されたレコードを記憶装置に出力するにあたって、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの記憶装置上の格納アドレスを示すラン情報を格納するものである。
【００５３】
そしてこの場合には、グループバイ処理実行手段１０９はハッシュ処理の結果として得られるハッシュ関数値に対応したハッシュ済レコード列の内容と、ラン情報格納手段に格納されているラン情報とを用いて、グループバイ処理を実行する。
【００５４】
このような補助情報リスト格納手段やラン情報格納手段のいずれを用いるとしても、本発明においてはハッシュ済レコード出力手段１０８がハッシュ関数値を例えばその最小値から最大値まで連続的に変化させてレコードを記憶装置の連続領域に逐次的、ブロック的に出力する動作、すなわちランの出力動作をグループバイ処理の対象となるレコード群が無くなるまで繰り返すことによりハッシュ済レコードのリストが作成され、そのリストに基づいてグループバイ処理が実行されることになる。
【００５５】
以上のように本発明におけるグループバイ処理方式によれば、例えばハッシュ関数値に対応して出力された複数のレコードを１つのブロックとして、例えばディスクなどの二次記憶装置に逐次的に出力することにより、記憶装置に対するアクセスの処理を高速化することが可能となる。
【００５６】
図２は本発明における相関のあるデータ組み合わせの数え上げ方式の原理構成ブロック図である。同図は、それぞれ１つ以上のアイテムをデータとして含む多数のトランザクションから、２つ以上のアイテムの組み合わせまたは１個のアイテムのみのうちで、トランザクションの中での出現回数が与えられた条件に適合する２個以上のアイテムの組み合わせ、または１個のアイテムのみと、その出現回数とを求めるデータ組み合わせの数え上げ方式の原理構成ブロック図である。
【００５７】
図２において組み合わせ生成手段１００は、１個のアイテムのみを対象とする時は各トランザクションに含まれるアイテムを１個ずつ出力し、ｉ個のアイテムの組み合わせを対象とする時は組み合わせ生成制約条件に適合する組み合わせのみを生成して、出力するものである。この生成制約条件は、ｉ個の組み合わせに含まれるアイテムの組み合わせ、または１個のアイテムのうちで、トランザクションの中での出現回数が前述の与えられた条件に適合するアイテムの組み合わせ、または１個のアイテムに含まれるアイテムに対応した条件である。
【００５８】
出現回数カウント手段１０１は、組み合わせ生成手段１００が出力する２個以上のアイテムの組み合わせ、または１個のアイテムのみの、トランザクション中での出現回数を、例えばグループバイ処理によってカウントするものである。
【００５９】
組み合わせ選択手段１０２は、出現回数カウント手段１０１が出力する２個以上のアイテムの組み合わせ、または１個のアイテムのうちで、出現回数が、例えば指定された回数以上というような与えられた条件に適合するものを選択するものである。
【００６０】
制約条件生成手段１０３は、組み合わせ選択手段１０２の選択結果に対応した、前述の組み合わせ生成制約条件を組み合わせ生成手段１００に与えるものであり、この組み合わせ生成制約条件は、例えば選択手段１０２の選択結果に出現するアイテムに対応するビット位置に“１”が立てられたビットマップである。
【００６１】
本発明の数え上げ方式においては、まず組み合わせ生成手段１００によって各トランザクションの中からアイテムが１つずつ取り出され、それぞれ１個のアイテムの出現回数が出現回数カウント手段１０１によってカウントされる。この時には組み合わせ生成制約条件は用いられず、トランザクションの中の全てのアイテムが１つずつ組み合わせ生成手段１００から出力され、その出現回数がカウントされる。
【００６２】
出現回数カウント手段１０１の出力、すなわち１つずつのアイテムの多数のトランザクション内部での出現回数のカウント結果は組み合わせ選択手段１０２に与えられる。組み合わせ選択手段１０２は、例えば出現回数がある回数以上であるものを選択し、その選択結果を１個のみのアイテムの出現回数として出力する。
【００６３】
その出力結果は制約条件生成手段１０３に与えられ、個々のアイテムに例えば１対１に対応するビットマップ上で組み合わせ選択手段１０２の出力に含まれるアイテムに対応するビットに“１”が立てられ、含まれないビットは“０”のままとされたビットマップが作成され、組み合わせ生成手段１００に組み合わせ生成制約条件として与えられる。
【００６４】
次に組み合わせ生成手段１００は、各トランザクションに含まれるアイテムのうちで、組み合わせ生成制約条件としてのビットマップ上に“１”が立っているビットに対応するアイテムの中から２個を選択し、その２個のアイテムの組み合わせを出現回数カウント手段１０１に出力する。出現回数カウント手段１０１は２個のアイテムの組み合わせの出現回数をカウントし、その結果を組み合わせ選択手段１０２に与える。組み合わせ選択手段１０２は、出現回数が与えられた条件に適合する２個のアイテムの組み合わせを選択して出力する。
【００６５】
同様の動作を繰り返すことにより、従来技術の図１６８や図１７０で説明したように、例えば３個のアイテムの組み合わせとしてラージアイテムセットが生成された段階で実質的な処理が終了する。
【００６６】
すなわち、図２に示す発明を要約すると、等しいキーの値を持つレコード群に対して指定された演算（平均値計算等）を行うグループバイ処理に関し、二次記憶装置へのアクセスを効率化し、処理を高速にすることを目的とし、レコードを一時的に格納する手段１０６と、手段１０６に格納されたレコードの格納位置を示すポインタを、キー値から計算されたハッシュ関数値に対応する位置に格納する手段１０７と、手段１０７内のポインタにより指されるレコードをハッシュ関数値に対応させて二次記憶装置に出力する手段１０８と、出力されたハッシュ済みレコードのリストを読み込み、キー値に従ってソートし、グループバイ処理を実行する手段１０９とを備えることを特徴とする。
【００６７】
従来技術で用いられたハッシュ表は、ラージアイテムセット中に存在する個々のアイテム、あるいは、アイテムの組み合わせの数に比例したメモリ量を必要とし、そのサイズを大きくして選択性を高めたり、小さくして選択性を多少低くして、メモリ使用量を少なくすることはできない。このため、従来技術では、処理対象のデータが大きく、ラージアイテムセットのサイズが大きくなる場合に、ハッシュ表が利用可能なメモリ量を超える可能性があり、その時にプルーニングができなくなるという問題があった。本発明におけるプルーニングは、個々のアイテム、または、アイテムの組み合わせがラージアイテムセット中に存在することを表現する１つまたは複数のビットマップを使って行われる。このビットマップは、複数のアイテム、あるいは、複数のアイテムの組み合わせの存在を単一のビットにより表現できるので、そのサイズを大きくして選択性を高めることや、小さくして選択性を多少低くして、メモリ使用量を少なくすることが可能である。この方式により、本発明はこの問題を解決している。
【００６８】
【発明の実施の形態】
本発明におけるグループバイ処理方式においてはハッシュ処理の結果に基づいてグループバイ処理が行われる。そこで以下の説明ではハッシュ処理の方式と、その結果を用いたグループバイ処理の方式との二段階に分けて、グループバイ処理方式の実施例を説明する。
【００６９】
図３は本発明におけるグループバイ処理方式の第１の実施例におけるハッシュ方式の説明図である。同図は、一般的に二次記憶装置に格納されているハッシュ対象リスト１１のレコード群を処理装置１２によってハッシュし、その結果をハッシュ済リスト２１、および補助情報リスト２２として、再び二次記憶装置に出力するハッシュ方式を示す。
【００７０】
入力バッファ１３はハッシュ対象リスト１１のレコードが一旦格納されるバッファである。レコードバッファ１４は入力バッファ１３に格納されているレコードを格納するものであり、例えばその容量は４であるとする。ハッシュ表１５は、入力バッファ１３からレコードバッファ１４に格納されるレコードのレコードバッファ内での格納位置へのポインタを、そのレコードのキーの値から計算されるハッシュ関数値に対応して格納するものである。リンク管理表１６は、レコードバッファ１４の内部に同一のハッシュ関数値を持つ複数のレコードが格納された時、その複数のレコードの間のリンクを管理するためのものである。
【００７１】
ハッシュ済リスト用出力バッファ１８は、レコードバッファ１４の内容が一杯になった時点でその内容を格納するものである。この場合格納されるレコードは、特定のハッシュ関数値を指定することによって、ハッシュ表１５内のポインタからポイントされるレコードである。出力ハッシュ値メモリ１７はその特定のハッシュ関数値を指定するものである。
【００７２】
指定されたハッシュ関数値を持つレコードがハッシュ済リスト用出力バッファ１８に格納されると、出力ハッシュ値メモリ１７の内容がインクリメントされ、その結果のハッシュ関数値を持つレコードが、レコードバッファ１４からハッシュ済リスト用出力バッファ１８に格納される。ハッシュ済リスト用出力バッファ１８が一杯になると、その内容としてのレコード群のハッシュ済リスト３１への出力がブロック的に行われる。補助情報リスト用出力バッファ１９は、このブロック的な出力に際して、そのブロックが二次記憶装置内で格納される領域の最初のアドレス（ブロック番号に対応）、そのブロック内のレコードに対応するハッシュ関数値の最小値、および最大値を補助情報として格納するものであり、このバッファ１９の内容も補助情報リスト２２として出力される。
【００７３】
一方レコードバッファ１４から１つのレコードがハッシュ済リスト用出力バッファ１８に格納されるたびに、入力バッファ１３内のレコードがレコードバッファ１４に格納され、以下同様の動作が続行される。
【００７４】
図４〜図７は本発明におけるグループバイ処理方式の第１の実施例におけるハッシュ処理のフローチャートである。ここでは図３のレコードバッファ１４が一杯になった時点で、１つのレコードをハッシュ済リスト用出力バッファ１８に移動させると共に、レコードバッファ１４の空き領域には入力バッファ１３から直ちにレコードを補充し、またハッシュ済リスト用出力バッファ１８が一杯になった時点で、その内容が１つのブロックのデータとしてハッシュ済リスト２１に出力されると同時に、そのブロックに対する補助情報が生成され、その補助情報は補助情報リスト用出力バッファ１９に格納されるものとしてハッシュ処理を説明する。
【００７５】
図４において処理が開始されると、まずステップＳ１でハッシュ対象リスト１１から入力バッファ１３にレコード群が読み込まれ、ステップＳ２で入力バッファ１３の中の先頭のレコードがレコードバッファ１４の空き領域に移動され、ステップＳ３でそのレコードのキー値に対するハッシュ関数値が計算され、ステップＳ４でそのハッシュ関数値に対応するハッシュ表１５のエントリにそのレコードがつながれる。すでにそのエントリにつながれているレコードが存在する場合には、既に存在したレコードに対するポインタはハッシュ表１５から削除され、リンク管理表１６を用いてすでに存在したレコードが新しいレコードにリンクされる。
【００７６】
続いてステップＳ５でレコードバッファ１４に空きがあるか否かが判定され、空きがある場合にはステップＳ７で入力バッファ１３にレコードがあるか否かが判定され、ある場合にはステップＳ２以降の処理が繰り返される。
【００７７】
ステップＳ５でレコードバッファに空きがないと判定された時には、レコードバッファ１４内のレコードをハッシュ済リスト用出力バッファ１８に移動させる出力処理がステップＳ６で行われ、出力処理終了後にステップＳ７の処理に移行する。出力処理の詳細については図５で説明する。またステップＳ７で入力バッファ１３にレコードがないと判定された時には、ステップＳ８でハッシュ対象リスト１１に未入力のレコードがあるか否かが判定され、ある場合にはステップＳ９でハッシュ対象リスト１１からレコード群が入力バッファ１３に読み込まれた後に、ステップＳ２以降の処理が繰り返される。
【００７８】
ステップＳ８でハッシュ対象リスト１１に未入力のレコードが存在しないと判定されると、ステップＳ１０でレコードバッファ１４にレコードが残っているか否かが判定され、残っている時にはステップＳ１１の出力処理が行われた後にＳ１０以降の処理が繰り返される。ステップＳ１０でレコードバッファ１４にレコードが存在しないと判定されると、ステップＳ１２の終了処理が行われた後に処理を終了する。終了処理の詳細については図６で説明する。
【００７９】
図５は図４におけるステップＳ６，Ｓ１１の出力処理の詳細フローチャートである。同図において処理が開始されると、まずステップＳ１６で出力ハッシュ値メモリ１７によって指定されるハッシュ表のエントリにつながれているレコードがあるか否かが判定され、ない場合にはＳ１７で出力ハッシュ値メモリ１７の値がインクリメントされ、ステップＳ１８で出力ハッシュ値がハッシュ値の最大値、例えばレコードのキー値を２０で割った剰余をハッシュ関数値としてとるものとすれば、その最大値１９を越えるか否かが判定され、越えない場合にはステップＳ１６以降の処理が繰り返される。
【００８０】
最大ハッシュ値を越える場合には、ここで出力ハッシュ値の値を０に戻してしまうと、ハッシュ済リスト用出力バッファ１８に格納され、１つのブロックとして取り扱われるべきレコードに対するハッシュ関数値の順序が後述するようにずれてしまうことになるため、ハッシュ済リスト用出力バッファ１８の内容を直ちにハッシュ済リスト２１に出力するためにステップＳ１９の出力バッファ出力処理が行われた後に、ステップＳ２０の処理に移行する。出力バッファ出力処理の詳細は図７で説明する。
【００８１】
出力バッファ出力処理の終了後にステップＳ２０で出力ハッシュ値の値が０に戻され、ステップＳ１６以降の処理が繰り返される。ステップＳ１６で出力ハッシュ値によって指定されるハッシュ表のエントリにつながれているレコードがあると判定された場合には、ステップＳ２１で出力ハッシュ値によって指定されるハッシュ表のエントリにつながれているレコードがハッシュ済リスト用出力バッファ１８に移動させられる。複数のレコードがそのエントリにリンク管理表１６を介してつながれている場合には、移動させられたレコードの次にリンクされているレコードがそのハッシュ表のエントリにつながれる。そしてステップＳ２２でハッシュ済リスト用出力バッファ１８が一杯か否かが判定され、一杯である場合にはステップＳ２３の出力バッファ出力処理が行われた後に、また一杯でない時には直ちに図４のステップＳ７、またはＳ１０の処理に戻る。
【００８２】
図６は図４のステップＳ１２、すなわち終了処理の詳細フローチャートである。同図において処理が開始されると、まずステップＳ２６でハッシュ済リスト用出力バッファ１８にレコードがあるか否かが判定され、レコードがある場合にはそこに残っているレコードをハッシュ済リスト２１に出力するための出力バッファ出力処理、すなわちステップＳ２７の処理が行われた後に、残っていない場合には直ちにステップＳ２８の処理に移行する。ステップＳ２８では補助情報リスト用出力バッファ１９にレコードが残っているか否かが判定され、残っている場合にはステップＳ２９でその内容が補助情報リスト２２に出力された後に、またレコードが残っていない場合には直ちに図４に戻り、全ての処理を終了する。
【００８３】
図７はステップＳ１９，Ｓ２３、およびＳ２７の出力バッファ出力処理の詳細フローチャートである。同図において処理が開始されると、まずステップＳ３１でハッシュ済リスト用出力バッファ１８の先頭、および末尾のレコードのハッシュキー値と、ハッシュ済リスト用出力バッファ１８の内容が出力されるべきハッシュ済リスト２１内のブロックの先頭アドレスとが１組の補助情報レコードとされて、そのレコードが補助情報リスト用出力バッファ１９に格納され、ステップＳ３２で補助情報リスト用出力バッファ１９が一杯か否かが判定され、一杯である場合にはステップＳ３３でその内容が補助情報リスト２２に出力された後に、また一杯でない時には直ちにステップＳ３４でハッシュ済リスト用出力バッファ１８の内容がハッシュ済リスト２１に出力された後に、図５のステップＳ２０、図４のステップＳ７，Ｓ１０、または図６のステップＳ２８に戻る。
【００８４】
図８は、図１６５で説明したグループバイ対象レコード群に対する図４〜図７のフローチャートによるハッシュ処理の経過の説明図である。同図において、ハッシュ表は上から順にハッシュ値の０，１および２を示し、左側の＊印は図３の出力ハッシュ値メモリ１７の内容（どのハッシュ値か）を示す。
【００８５】
図８（１）  のグループバイ対象レコード群の最初のレコードが、レコードバッファ１４に格納された状態を（２）  に示す。すなわち、最初のレコードとしての“５”に対するハッシュ値は２であり、ハッシュ表中の２のエントリから、レコードバッファ１４に格納されたレコード“５”をポイントするポインタがつながれる。
【００８６】
図８（３）  は次のレコードとしての“３”がそのハッシュ関数値０のエントリにつながれた状態を、また（４）  はその次のレコード“３”が更にハッシュ表のハッシュ値０のエントリにつながれた状態を示す。このようにハッシュ表の１つのエントリからポイントされるレコードが複数になると、その複数のレコードの間のリンク関係は図３のリンク管理表１６によって管理される。その詳細は出願人の次の先願に詳細に記述されている。
【００８７】
特開平８−１２９５５１（平成８年５月２１日公開）、
発明の名称「ハッシュ方式」
図８（５）  は、更にその次のレコード“４”がハッシュ表中のハッシュ値１のエントリからポイントされた状態を示す。前述のように、レコードバッファ１４の容量がレコード４個分であるとすると、この時点でレコードバッファは一杯になる。
【００８８】
そこで図８（６）  に示すように１つのレコード、ここでは“３”がレコードバッファ１４からハッシュ済リスト用出力バッファ１８に出力される。この時出力されるレコードは、出力ハッシュ値メモリ１７の内容としてのハッシュ値、ここでは０を持つものである。
【００８９】
図８（７）  は更にその次のレコード“２”が、ハッシュ表の２のエントリにつながれた状態を示す。この時点でもレコードバッファ１４が一杯であるため、出力ハッシュ値メモリ１７の値、ここでは０のエントリにつながれているレコード“３”がハッシュ済リスト用出力バッファ１８に出力される。
【００９０】
図８（８）  はその次のレコード“１”がハッシュ表の１のエントリにつながれた状態を示す。この時点でハッシュ済リスト用出力バッファ１８に出力すべきレコードは、ハッシュ表の１のエントリから指されるレコード、すなわち入力バッファ１３からレコードバッファ１４に格納されたばかりのレコード“１”である。これは（７）  の時点で出力ハッシュ値メモリ１７の値０のエントリにつながれているレコード“３”が出力された後に、そのエントリにつながれているレコードがなくなってしまい、その結果出力ハッシュ値メモリ１７の内容がインクリメントされたことによる。
【００９１】
以下同様にして処理が実行されるが、図３のハッシュ済リスト用出力バッファ１８の内容が一杯になるたびに、その内容は二次記憶装置上のハッシュ済リスト２１に出力される。図９は最終的に二次記憶装置内に作られたハッシュ済リストの内容を示す。ブロック番号２に対して格納されているレコードは２個であるが、これは図５のステップＳ１８で出力ハッシュ値が最大ハッシュ値を越えたと判定されると、その時点で出力バッファ出力処理、すなわちステップＳ１９が実行されるためである。図９に対応する補助情報リストは［０，０，１］［１，１，２］［２，２，２］および［３，０，１］である。
【００９２】
グループバイ処理方式の第１の実施例における後半の処理、すなわちハッシュ処理の結果を用いたグループバイ処理について説明する前に、グループバイ処理方式の第２の実施例におけるハッシュ処理について説明する。図１０は第２の実施例におけるハッシュ処理の説明図である。第１の実施例における図３と比較すると、処理装置１２の内部に出力ブロック数カウンタ２０が備えられている点のみが異なっている。これは第１の実施例において、補助情報レコードがブロック番号、ブロック内のレコードの最小ハッシュ値、および最大ハッシュ値からなっているのに対して、この第２の実施例ではブロック番号、ブロック内のレコードの最小ハッシュ値、および補助情報レコードの生成順の番号、すなわち出力ブロックの生成順の番号の３つからなっていることによる。この補助情報レコードの内容、およびそのソートについては後述する。
【００９３】
第２の実施例におけるハッシュ処理のフローチャートは図４〜図７とほぼ同様であるが、図７の出力バッファ出力処理に一部異なる部分があり、そのフローチャートを図１１に示す。同図において、ステップＳ３６でハッシュ済リスト用出力バッファ１８の先頭のレコードのハッシュ値、出力ブロック数カウンタ２０のカウント値、ハッシュ済リスト用出力バッファの内容が出力されるべきハッシュ済リスト内のアドレスが組とされて、補助情報レコードが作られ、それが補助情報リスト用出力バッファ１９に格納される。その後ステップＳ３７の判定で補助情報用出力バッファ１９が一杯の時にはステップＳ３８でその内容が補助情報リスト２２に出力された後に、補助情報リスト用出力バッファ１９が一杯でない時にはステップＳ３８の処理が行われることなく、ステップＳ３９で出力ブロック数カウンタ２０のカウント値がインクリメントされ、ステップＳ４０でハッシュ済リスト用出力バッファ１８の内容がハッシュ済リスト２１に出力されて、処理が呼び出し元に戻る。
【００９４】
第１、および第２の実施例における後半の処理、すなわちグループバイ処理自体について説明する前に、補助情報リストのソートについて説明する。第１、および第２の実施例では、ハッシュ処理によって作成された補助情報リストのソートが実行された後に、グループバイ処理が実行される。
【００９５】
一般的にソートの手法のうちで入力データ、すなわちソート対象データの中で等しいキーを持つデータの順序がソートの後でも保存されているものを安定なソートという。すなわち安定なソートでは、同じキーを持つレコードの相対的な順序がソート前とソート後とで変化しないことになるが、この安定なソートはソートの手法のうちの１つのカテゴリに入るものであり、全てのソートが安定なソートというわけではない。
【００９６】
そこで、補助情報リストのソートにおいてどのようなソート方式を用いるかが問題となるが、ソートの手法として安定なソートだけに限定せず、一般的なソートの手法を用いることができるようにするためには、第１、および第２の実施例において説明したように、補助情報リストの内容としてブロック番号と最小ハッシュ値の２つの情報だけでは不足であり、第３の情報として最大ハッシュ値、または補助情報レコードの生成順の番号も持たせる必要がある。
【００９７】
これに対して補助情報リストのソートの方法として安定なソートを保証できる方法を用いることができる場合には、補助情報レコードが持つべき情報は、例えばブロック番号と最小ハッシュ値の２つだけに限定することができる。このように安定なソートを用いる場合には、補助情報レコードの大きさを小さくできるという利点があるが、補助情報リストのソート方式が安定なソートのみに限定されてしまうという欠点がある。
【００９８】
補助情報リストのソート方式として安定なソートを用いる場合には、キーとして最小ハッシュ値を使用してソートを行うことによって、同じキーを持つ補助情報レコードに対しては、ソート後の補助情報リストの順序がソート前の補助情報リストの順序と同じになるようにソートすることが可能となり、その結果ソート後の補助情報リストの順序がソート前のランの中での順序と同じになるようにソートすることができる。
【００９９】
これに対して補助情報リストのソート方式として安定なソートのみに限定せず、一般的なソートの方法を用いる場合には、補助情報のうちの第３の情報として最大ハッシュ値、あるいは補助情報レコードの生成順の番号を持たせることによって最小ハッシュ値を第１キー、最大ハッシュ値、あるいは補助情報レコードの生成順の番号を第２キーとしてソートを実行すれば、ソート後の補助情報リストの順序がソート前のランの中での順序と同じになるようにすることが可能である。この第３の情報としての最大ハッシュ値、または補助情報レコードの生成順の番号も補助情報として持たせ、安定なソートを実行しても当然何ら問題は生じない。
【０１００】
補助情報リストのソートは、例えば図３の処理装置１２の内部に補助情報リストソート装置を備えることによって実行される。安定なソートが保証されている場合には、補助情報リストの内容を補助情報リストソート装置に読み込み、開始ハッシュ値をキーとしてソートを実行し、ソート結果をソートされた補助情報リストとして出力する。
【０１０１】
補助情報リストのソートについては、第１に補助情報リストソート装置が安定なソートを保証しているか否か、第２に補助情報リストがすでに二次記憶装置に出力されているか否か、第３に二次記憶装置に出力されている補助情報リストが、補助情報リストソート装置が使えるメモリ上に全て格納できるか否かによって、その処理が異なる。補助情報リストが二次記憶装置に出力されていない場合には、補助情報リスト用出力バッファ１９の中で、すなわち主記憶上のみでソートを行うことが可能であり、これらに関連して補助情報リストのソート処理については、図１２〜図１７の６種類の処理フローチャートのいずれかを使用することができる。
【０１０２】
図１２は補助情報リストソート処理（第１の方法）のフローチャートである。このフローチャートは安定なソートが保証され、補助情報リストが二次記憶装置に出力されていない場合の処理フローチャートを示す。この場合には、ステップＳ４１で参照ハッシュ値をキーとしてソートが実行され、ステップＳ４２でソート処理の結果が後述するソートされた補助情報リスト用入力バッファに格納できるか否かが判定され、格納できる場合にはステップＳ４３でその入力バッファにソート結果が格納され、格納できない場合にはステップＳ４４でソート結果が二次記憶装置に出力されて、処理を終了する。ここでソートされた補助情報リスト用入力バッファは、図３の処理装置１２の内部、例えば主記憶上に設けられるものであり、一般にその容量はあまり大きくないため、ステップＳ４２の判定が行われる。
【０１０３】
図１３は補助情報リストソート処理（第２の方法）のフローチャートを示す。このフローチャートは安定なソートが保証されておらず、補助情報リストが二次記憶装置に出力されていない場合の処理を示す。この場合は、ステップＳ４６で最小ハッシュ値を第１キー、最大ハッシュ値あるいは補助情報レコード生成順の番号を第２キーとしてソートが実行され、その後図１２と同様にステップＳ４２〜Ｓ４４の処理が実行されて、処理を終了する。
【０１０４】
図１４は補助情報リストソート処理（第３の方法）のフローチャートである。同図は安定なソートが保証され、補助情報リストが二次記憶装置に出力されており、かつ出力されている補助情報リストが、補助情報リストソート装置が使用できるメモリ上に全て格納できる場合に対応する。この場合には、まずステップＳ４８で二次記憶装置上に格納されている補助情報リストがソート装置のメモリ上に展開されて、ステップＳ４９で最小ハッシュ値をキーとしたソートが実行された後に、図１２と同様にステップＳ４２〜Ｓ４４の処理が実行されて、処理を終了する。
【０１０５】
図１５は補助情報リストソート処理（第４の方法）のフローチャートを示す。同図は安定なソートが保証されておらず、補助情報リストが二次記憶装置に出力されており、出力されている補助情報リストの大きさが、補助情報リストソート処理装置が使用できるメモリ上に全て格納できる大きさである場合に対応する。この場合には、図１４と同様にステップＳ４８で補助情報リストがメモリ上に展開された後に、図１３と同様にステップＳ４６でソートが実行された後に、ステップＳ４２〜Ｓ４４の処理が実行されて、処理を終了する。
【０１０６】
図１６は補助情報リストソート処理（第５の方法）のフローチャートである。これは安定なソートが保証され、補助情報リストが二次記憶装置に出力されており、出力された補助情報リストが、補助情報リストソート処理装置が使用できるメモリ上にその全てを格納することができない大きさを持つ場合に対応する。この場合には、ステップＳ５１で最小ハッシュ値をキーとして外部ソートが実行され、ステップＳ５２でそのソート結果が二次記憶装置に出力されて、処理を終了する。この場合には外部ソートを行わなければならないほど補助情報リストの大きさが大きいために、図１２のステップＳ４２における判定、すなわち補助情報リスト用入力バッファがソート結果を格納できるか否かの判定が実行されず、ステップＳ５２でソート結果が直ちに二次記憶装置に出力される。
【０１０７】
図１７は補助情報リストソート処理（第６の方法）のフローチャートである。これは図１６と比較して安定なソートが保証されていない点のみが異なる場合に対応する。この場合には、ステップＳ５３で最小ハッシュ値が第１キー、最大ハッシュ値、または補助情報レコード生成順の番号が第２キーとして使われて、外部ソートが実行され、ステップＳ５２でそのソート結果が二次記憶装置に出力されて、処理を終了する。
【０１０８】
以上で補助情報リストのソート処理についての説明を終わり、第１の実施例および第２の実施例における後半の処理、すなわちハッシュ処理の結果を用いたグループバイ処理について説明する。この後半の処理、すなわちグループバイ処理自体については、本発明のグループバイ処理方式の一部であることから、以後グループバイ関数処理と呼ぶことにする。図１８はこのグループバイ関数処理の全体説明図である。同図において、処理装置１２の内部には前述のソートされた補助情報リスト用入力バッファ３１と、ランの数に等しい個数のハッシュ済リスト用入力バッファ３２ａ，３２ｂ，・・・，３２ｎが設けられ、図１２〜図１７のいずれかのフローチャートを用いてソートされた結果としての、ソートされた補助情報リスト３０はソートされた補助情報リスト用入力バッファ３１に読み込まれ、ハッシュ済リスト２１の内容はハッシュ済リスト入力バッファ３２ａ〜３２ｎのいずれかに読み込まれ、最小ハッシュ値レコード取り出し装置３３、ハッシュ値が等しいレコード群のソート装置３４、グループバイ関数演算処理装置３５が使用されて最終的な処理結果が出力される。
【０１０９】
図１９はグループバイ処理方式の第１および第２の実施例におけるグループバイ関数処理の全体フローチャートである。同図において処理が開始されると、まずステップＳ６１でハッシュ済リスト用入力バッファ３２ａ〜３２ｎのいずれかに空のものがあるか否かが判定され、ある場合にはステップＳ６２でソートされた補助情報リスト用入力バッファ３１にレコードが格納されていないか否かが判定され、格納されていない場合にはステップＳ６３でソートされた補助情報リスト３０にレコードがあるか否かが判定され、ある場合にはステップＳ６４でそのリスト３０から入力バッファ３１にレコード群が読み込まれる。
【０１１０】
続いてステップＳ６５で補助情報リスト用入力バッファ３１から１つのレコードが読み出され、そのレコードが指すブロックがハッシュ済リスト２１から読み出されて、ハッシュ済リスト用入力バッファ３２ａ〜３２ｎのうちで空のバッファに格納された後に、ステップＳ６１以降の処理が繰り返される。
【０１１１】
ステップＳ６２で補助情報リスト用入力バッファにレコードがある場合には、ステップＳ６３，Ｓ６４の処理を行うことなく、ステップＳ６５の処理に移行し、その後ステップＳ６１以降の処理が繰り返される。
【０１１２】
ステップＳ６１でハッシュ済リスト入力バッファに空のものがないと判定されるか、ステップＳ６３で補助情報リスト３０にレコードがないと判定されると、ステップＳ６６で空でないハッシュ済リスト用入力バッファがあるか否かが判定される。ある場合には、ステップＳ６７で最小ハッシュ値レコード取り出し装置３３を用いて、空でないハッシュ済リスト用入力バッファの先頭のレコードの中でハッシュ値が最も小さいものを取り出し、ハッシュ値が等しいレコード群のソート装置３４にそのレコードを与える。その後ステップＳ６８で、ソート装置３４に入力されたレコードのハッシュ値がその直前に入力されたレコードのハッシュ値と異なるか否かが判定され、異なっていない場合にはステップＳ６１以降の処理が繰り返される。
【０１１３】
これに対してハッシュ値が異なる場合には、同一のハッシュ値を持つレコードの取り出しが終了したことになるため、ステップＳ６９でソート装置３４にたまっているレコードをキー値を用いてソートし、その結果をグループバイ関数演算処理装置３５に出力してソート装置３４を空にした後に、ステップＳ７０で図２０で説明するグループバイ関数演算処理が行われ、その後ステップＳ６１以降の処理が繰り返される。そしてステップＳ６６で空でないハッシュ済リスト用入力バッファが存在しないと判定された時点で、処理を終了する。
【０１１４】
図２０は、図１９のステップＳ７０、すなわちグループバイ関数演算処理の詳細フローチャートである。同図を従来例の図１６６と比較すると、ステップＳ７１〜Ｓ８０の内容は図１６６のステップＳ２２３〜Ｓ２３２と実質的に同じであり、グループバイ関数演算処理自体は従来例と基本的に同じである。
【０１１５】
次に本発明におけるグループバイ処理方式の第３の実施例について説明する。図２１は第３の実施例におけるハッシュ処理の説明図である。同図を図３に示した第１の実施例におけるハッシュ処理と比較すると、ハッシュ済リスト用出力バッファ１８に代わってハッシュ済レコード用出力バッファ３８が備えられている点と、ハッシュ済リスト２１の代わりにハッシュ済レコード出力領域４０が二次記憶装置上に設けられている点とが異なっている。すなわち、第３の実施例ではハッシュ済レコード用出力バッファ３８の内容を二次記憶装置に出力するにあたって、ハッシュ済リスト２１のように連続した領域に逐次的に書込みを行う代わりに、二次記憶装置上の必ずしも連続でない領域に書込みを行うという点が第１、および第２の実施例と異なる。この第３の実施例は、二次記憶装置上に空き領域が多いにもかかわらず、その空き領域は連続した領域ではないという状況において有効であり、二次記憶装置への書込みは逐次書込みではないが、ハッシュ済レコード用出力バッファ３８の内容を一度に出力することにより、書込みデータのサイズを大きく取ることができ、連続領域に対する書込みに近い性能で処理を実行することができる。
【０１１６】
第３の実施例における処理のフローチャートは、第１の実施例に対する図４〜図７とほぼ同様であるが、図７と出力バッファ出力処理の内容がやや異なり、その処理は図２２に示される。
【０１１７】
図２２において処理が開始されると、まずステップＳ８１で図２１のハッシュ済レコード出力領域４０から、ハッシュ済レコード用出力バッファ１８の大きさ分の連続した領域が探され、その領域が確保され、確保された連続領域の先頭アドレスが得られる。ステップＳ８２でハッシュ済レコード用出力バッファ３８の先頭、および末尾のレコードに対応するハッシュ値、すなわち最小ハッシュ値および最大ハッシュ値と、ステップＳ８１で得られた領域の先頭アドレスが組とされて補助情報レコードが作られ、それが補助情報リスト用出力バッファ１９に格納された後、ステップＳ８３、Ｓ８４で図７のステップＳ３２，Ｓ３３と同様の処理が行われた後に、ステップＳ８５でハッシュ済レコード用出力バッファ３８の内容が、ハッシュ済レコード出力領域４０の中のステップＳ８１で確保された領域に出力されて、処理が呼出し元に戻る。
【０１１８】
図２３は第３の実施例における後半の処理、すなわちグループバイ関数処理の全体説明図である。同図を図１８に示した第１、および第２の実施例におけるグループバイ関数処理と比較すると、ハッシュ済リスト２１の代わりにハッシュ済レコード出力領域４０が二次記憶装置上に設けられている点と、処理装置１２内のラン数分のハッシュ済リスト用入力バッファ３２ａ〜３２ｎに代わって、同様のハッシュ済レコード用入力バッファ３６ａ〜３６ｎが設けられている点が異なっている。
【０１１９】
図２４は第３の実施例におけるグループバイ関数処理の全体フローチャートである。同図を第１、第２の実施例における図１９と比較すると、ハッシュ済リスト用入力バッファの代わりにハッシュ済レコード用入力バッファという用語が、またハッシュ済リストの代わりにハッシュ済レコード出力領域という用語が用いられている点のみが異なっている。
【０１２０】
図２５はグループバイ処理方式の第４の実施例におけるハッシュ処理の説明図である。この第４の実施例では、第１〜第３の実施例と異なって、補助情報リストの代わりに処理装置１２の内部にラン情報メモリ２３、およびラン番号メモリ２４を備える点に大きな特徴がある。このラン情報としては、二次記憶装置上で１つのランの最初のレコードの格納アドレス、すなわち開始アドレス（開始ブロック番号）と、そのランにおける最後のレコードの格納アドレス、すなわちランの終了アドレス（終了ブロック番号）の２つの情報を持つものである。第１の実施例に対する図３と同様に、二次記憶装置上のハッシュ済リスト２１は連続領域であり、その領域への逐次書込みと逐次読出しとによって処理が実行されるために、高速に処理を行うことができる。
【０１２１】
この第４の実施例においては、補助情報リストの代わりにラン情報が用いられるが、それ以外のハッシュ処理の方法は第１の実施例におけるとほぼ同じであり、処理のフローチャートも第１の実施例に対応する図４〜図７と類似したものとなる。特に図４に対応する全体処理のフローチャートは第１の実施例におけると同じであり、その説明を省略する。
【０１２２】
ラン情報を使用する点で図５の出力処理、図６の終了処理、および図７の出力バッファ出力処理とは一部異なる処理が生ずる。図２６〜図２８は第４の実施例におけるこれらの処理のフローチャートである。図２６は出力処理のフローチャートであり、図５と比較するとステップＳ２０で出力ハッシュ値の値が０に戻される、すなわち１つのランが終了した時点で、ステップＳ９０の処理が追加され、ラン番号メモリ２４に格納されているラン番号のインクリメントが行われる点が異なっている。
【０１２３】
図２７は第４の実施例における終了処理のフローチャートであり、図６と比較すると、補助情報を用いないために、ステップＳ２８、およびＳ２９の処理が不要となる点が異なっている。
【０１２４】
図２８は第４の実施例における出力バッファ出力処理のフローチャートである。このフローチャートでは、補助情報リストを使用しないことに関連して、第１の実施例に対する図７とはかなり異なる処理が行われる。まずステップＳ９１でハッシュ済リスト用出力バッファ１８の内容がハッシュ済リスト２１に出力された後、ステップＳ９２でラン番号が指すラン情報の開始アドレスが設定されているか否かが判定される。設定されていない場合には、ステップＳ９３でラン情報の開始アドレスとして、ハッシュ済リストの一部として出力されるレコードの二次記憶装置上でのアドレス（ブロック番号）がセットされた後に、また開始アドレスがすでに設定されていると判定された場合には、ステップＳ９３の処理を行うことなく、ステップＳ９４で終了アドレスとして、出力されるレコードの二次記憶装置上でのアドレス（ブロック番号）がセットされて、処理が元に戻る。
【０１２５】
図２８のステップＳ９２〜Ｓ９４の処理について、図８のハッシュ処理を具体例として説明する。図８（１）  のグループバイ対象レコード群のハッシュ処理が開始され、図８（８）  まで処理が進んだ時点を考える。ここでラン情報は（開始ブロック番号、終了ブロック番号）の形式で表現するものとし、処理を始める前の初期状態としてラン番号は１、ラン情報は（未設定、未設定）となっていたものとする。（８）  の状態で図９に示すようにブロック０にレコード３，３，１が出力される。この出力処理は図２８のステップＳ９１において行われる。
【０１２６】
ステップＳ９２で開始アドレスが設定されているか否かが判定されるが、ここでは未設定であるために、ステップＳ９３でラン情報に開始ブロック番号がセットされ、ラン情報は（０、未設定）となる。更にステップＳ９４でラン情報は（０，０）となる。
【０１２７】
ハッシュ処理が続いて図８（１１）まで処理が進んだとすると、ブロック１にレコード４，２，５がステップＳ９１で出力され、ステップＳ９２ではラン番号１に対応するラン情報の開始アドレスがすでに設定されているため、ステップＳ９３の処理を行うことなく、ステップＳ９４でラン情報の終了アドレスが更新され、ラン番号１のラン情報は（０，１）となる。
【０１２８】
更にハッシュ処理が続き、図８（１３）まで処理が進んだとすると、ステップＳ９１でブロック２にレコード２，５が出力される。すでにラン番号１のラン情報の開始アドレスは設定されているため、ステップＳ９３の処理を行うことなく、ステップＳ９４で終了アドレスが更新され、ラン番号１に対するラン情報は（０，２）となる。
【０１２９】
ここでラン番号１のランに対するレコードの出力は終了しており、図２６のステップＳ２０の後にＳ９０の処理が実行され、ラン番号がインクリメントされて２となる。ラン番号２に対するラン情報は、この時点では（未設定、未設定）である。
【０１３０】
ハッシュ処理が更に進行し、図８（１５）まで処理が進んだとすると、ステップＳ９１でブロック３にレコード３，１が出力される。この時ラン情報の開始アドレスは設定されていないため、ステップＳ９３でラン情報は（３、未設定）となり、ステップＳ９４でラン情報は（３，３）となる。以上の経過を経てラン情報として（０，２）（３，３）が得られる。
【０１３１】
第４の実施例においても、第１の実施例に対する第２の実施例の関係と同様に、二次記憶装置上の連続領域としてのハッシュ済リスト２１の格納領域の代わりに、飛び飛びのレコード格納領域、すなわち図２１のハッシュ済レコード出力領域４０を利用することも可能である。この場合の処理も、第３の実施例における図２６〜図２８の処理とほぼ同様であるが、図２６に示した出力処理の一部が変更される。
【０１３２】
図２９はこのようにグループバイ処理方式の第４の実施例において、二次記憶装置上の飛び飛びの領域をハッシュ済レコード出力領域として用いる場合の、出力処理のフローチャートである。同図を図２６と比較すると、ステップＳ９０でラン番号がインクリメントされ、新しいランに対するレコードの出力を開始する前に、ステップＳ９６でハッシュ済レコード出力領域内で新しいランを格納できる連続領域が探し出された後に、ステップＳ１６以降の処理が実行される点が異なっている。
【０１３３】
なおここで新しいランを格納できる連続領域を探し出す場合に、新しいランの長さは一般的に不明であるが、ハッシュ対象レコードがハッシュ値としてランダムな値を持つという仮定ができる場合には、ランの長さは例えばレコードバッファ１４の容量の２倍の長さを持つようになるといえるが、一般的には２倍の長さには限定されず、その長さは不明である。しかしながら、例えば第１の実施例に対応する図３においても、二次記憶装置上でハッシュ済リスト２１が格納される連続領域の長さを明確に決定することが必ずしも困難でないと考えられることに対応して、新しいランを格納できる連続領域を探し出すことは実用的にはそれほど困難でないものと考えられる。
【０１３４】
図３０は第４の実施例において、ハッシュ処理の結果を図２５のハッシュ済リスト２１、すなわち連続領域の形式でなく、図２１のハッシュ済レコード出力領域４０のように飛び飛びの領域に出力する場合の出力結果を示す。この場合には、ハッシュ済レコードの出力は、その一部が逐次書込みであるが、全てが逐次書込みである必要はないという特徴がある。すなわち、１つのランの内部では逐次書込みを行い、異なるランは離れた領域にあってよいということになる。
【０１３５】
図３０は、図８と同様のハッシュ動作が行われた場合の、二次記憶装置上へのハッシュ済レコードの出力結果であるが、ラン番号１のランはブロック番号０からブロック番号２までの連続領域に格納されているのに対し、ラン番号２のランはブロック番号１０のみの連続領域に格納されている。従ってラン情報は（０，２）および（１０，１０）である。この場合図２５のハッシュ処理と比較すると、ハッシュ済レコードの二次記憶装置への書込みは完全に逐次ではないが、ランの内部では逐次書込みを行うため、高速に処理を行うことが可能であり、二次記憶装置上に空いている連続領域の長さがあまり長くない場合などに有効である。
【０１３６】
図３１は第４の実施例における後半の処理、すなわちグループバイ関数処理の全体説明図である。同図を例えば第３の実施例に対応する図２３と比較すると、補助情報リストを使用しないことから、ソートされた補助情報リスト用入力バッファ３１の代わりに、ラン情報メモリ２３が用いられる点が異なっている。なおここでハッシュ済レコード出力領域４０は連続領域のように見えるが、前述のように第４の実施例ではこの領域は連続であっても、非連続であっても、どちらでもよく、図３１ではどちらの場合をも表していると考えてよい。
【０１３７】
図３２は第４の実施例におけるグループバイ関数処理の全体フローチャートである。同図において処理が開始されると、まずステップＳ１０１で図３１のハッシュ済レコード用入力バッファ３６ａ〜３６ｎのそれぞれに１対１に対応するようにランの割り当てが行われ、ステップＳ１０２でラン情報の各エントリにある各先頭ブロックのレコードが各ハッシュ済レコード入力バッファに格納された後に、ステップＳ１０３〜Ｓ１０９の処理が繰り返される。
【０１３８】
まずステップＳ１０３で空でないハッシュ済レコード用入力バッファがあるか否かが判定され、ある場合にはステップＳ１０４で最小ハッシュ値レコード取り出し装置３３を用いて、空でないハッシュ済レコード用入力バッファの先頭のレコードの中でハッシュ値が最も小さいものが取り出され、ソート装置３４に入力される。そしてステップＳ１０５で入力されたレコードのハッシュ値が直前に入力されたもののハッシュ値と異なるか否かが判定され、異なる場合にはステップＳ１０６でソート装置３４に溜まっているレコードがキー値によってソートされ、その結果がグループバイ関数演算処理装置３５に入力され、ソート装置３４が空にされた後、ステップＳ１０７でグループバイ関数演算処理が行われる。
【０１３９】
その後ステップＳ１０８で空となったハッシュ済リスト用入力バッファがあるか否かが判定され、ある場合にはステップＳ１０９でその入力バッファに割り当てられたランにおいて読み出されていないブロックがあれば、その中の先頭ブロックがハッシュ済レコード用入力バッファに格納された後、ステップＳ１０３以降の処理が繰り返される。
【０１４０】
またステップＳ１０５で２つのハッシュ値が同じであると判定された場合には、ステップＳ１０６，Ｓ１０７の処理を実行することなく、ステップＳ１０８の処理に移行する。そしてステップＳ１０３で空でないハッシュ済レコード用入力バッファが存在しないと判定された時点で、処理を終了する。
【０１４１】
ステップＳ１０７のグループバイ関数演算処理は、第１の実施例に対応する図２０におけると同じであるので、その説明を省略する。
以上のようにグループバイ処理方式の第４の実施例では、ラン数分のハッシュ済レコード用入力バッファが用意され、各ハッシュ済レコード用入力バッファにはそれぞれ１対１に対応する特定のランのブロックのレコードしか格納されないように処理が実行される。それぞれのランのブロックのレコードが、ラン情報に従って順番に格納されるように処理が行われる。ハッシュ済レコード出力領域からハッシュ済レコード用入力バッファへの読込みを行う時に発生する二次記憶装置への読出し要求は連続領域に対するものではないが、１つ１つの読出し要求に対応する領域のサイズを比較的大きく取ることができるため、連続領域に対する読出し要求に近い性能で処理を実行することが可能となる。
【０１４２】
図３３はグループバイ処理方式の第５の実施例におけるハッシュ処理の説明図である。この第５の実施例では、第４の実施例と同様に補助情報リストでなくラン情報が用いられるが、二次記憶装置上のハッシュ済レコード出力領域４１としての飛び飛びの領域の１つ１つが必ずしも１つのランの全てのレコードを格納できる大きさを持っていない場合の実施例であり、このためその飛び飛びの領域を連結する情報を用いて、ハッシュ済レコードを出力するものである。
【０１４３】
グループバイ処理方式の第５の実施例におけるハッシュ処理のフローチャートは、第４の実施例に対する図２６〜図２８とほぼ同様であるが、出力バッファ出力処理の一部に異なる点があり、この処理のフローチャートを図３４に示す。図３４を第４の実施例における図２８と比較すると、ステップＳ９１に対応するステップＳ１１１で出力バッファの内容をハッシュ済レコード出力領域に出力するにあたり、次にレコードを出力すべき領域のアドレスも一緒に出力する点のみが異なっている。
【０１４４】
図３５はグループバイ処理方式の第５の実施例における後半の処理、すなわちグループバイ関数処理の全体説明図である。同図を第４の実施例における図３１と比較すると、ハッシュ済レコード出力領域４１が飛び飛びの領域であり、しかも各領域の内部に、次のレコードが格納されている領域のアドレスも格納されている点のみが異なっている。
【０１４５】
図３６は第５の実施例におけるグループバイ関数処理の全体フローチャートである。同図を第４の実施例における図３２と比較すると、ステップＳ１０２に対応するＳ１１３でラン情報の各エントリにある各先頭ブロックのレコードが各ハッシュ済レコード用入力バッファに格納されるにあたり、同時に次にレコードを読み込むべきブロックのアドレスが獲得される点と、ステップＳ１０９に対応するＳ１１４で読み出されていないブロックがハッシュ済レコード用入力バッファに格納されるにあたり、同時に次にレコードを読み込むべきブロックのアドレスが獲得される点が異なっている。
【０１４６】
以上で本発明におけるグループバイ処理方式の実施例を詳細に説明したが、以下で具体的なグループ対象リストとしてのレコード群を用いて、本発明におけるグループバイ処理方式をさらに詳細に説明する。
【０１４７】
図３７はデータの具体例とともに、本発明におけるグループバイ処理方式の全体処理方式を示す図である。同図は前述の第１の実施例にほぼ対応するものである。
【０１４８】
図３７において処理装置１２の内部には、図１８におけると同様の構成要素に加えて、ハッシュ処理装置５０、補助情報リストソート装置５１が備えられ、また図１８のグループバイ関数演算処理装置３５の具体例としてカウント処理装置５２が備えられている。また二次記憶装置５３には、ハッシュ処理の後にグループバイ関数処理の対象となるグループバイ対象リスト５４が格納され、ハッシュ処理の結果としてのハッシュ済リストを格納する領域２１、補助情報リストを格納する領域２２、および補助情報リストのソート結果としてのソートされた補助情報リストを格納する領域３０が備えられている。
【０１４９】
図３８は図３７のハッシュ処理装置５０の構成を示す。その構成は、図３と比較して、入力バッファ１３とほぼ同様の役割をはたすグループバイ対象リスト用入力バッファ５５が、入力バッファ１３に代わって備えられている点のみが異なっている。
【０１５０】
ここで具体的なグループバイ対象データが、次の３０個のレコード（キー値のみからなる）によって構成されるリストとして与えられるものとする。
５，３，３，４，２，１，２，３，５，１，２，３，３，２，１，１，５，５，４，１，４，２，３，３，２，５，１，１，３，３
このグループバイ対象データに対するハッシュ処理のためのハッシュ関数として、キーの値のｍｏｄ３を用いるものとする。すなわちキーの値を３で割り、その時の余りの値をハッシュ関数の値とする。ハッシュ表１５のエントリはこれに合わせて３つとなっている。グループバイ対象リスト用入力バッファ５５、ハッシュ済リスト用出力バッファ１８には共に３つのレコードが格納されるものとし、またレコードバッファ１４には４つのレコードが格納されるものとする。これに合わせてリンク管理表１６のエントリ数も４となっている。
【０１５１】
ハッシュ処理の結果として次に示すハッシュ済リストが得られる。
３，３，１，４，２，５，２，２，５，３，３，３，１，１，１，４，１，４，２，５，５，２，５，２，３，３，３，３，１，１
同時に次に示す補助情報リストが得られる。
【０１５２】
〔１０，０，１〕〔１１，１，２〕〔１２，２，２〕〔１３，０，０〕〔１４，１，１〕〔１５，１，１〕〔１６，２，２〕
〔１７，２，２〕〔１８，０，０〕〔１９，０，１〕
ここではハッシュ済リストの中にハッシュ値でソートされた次の３つの列が含まれる。
【０１５３】
３，３，１，４，２，５，２，２，５
３，３，３，１，１，１，４，１，４，２，５，５，２，５，２
３，３，３，３，１，１
列が３つであるためラン数は３である。これらのレコードをそれぞれ対応するハッシュ値で置き替えると、次のようになっている。
【０１５４】
０，０，１，１，２，２，２，２，２
０，０，０，１，１，１，１，１，１，２，２，２，２，２，２
０，０，０，０，１，１
図３９はこのような具体的データを対象とするグループバイ処理の全体フローチャートである。同図において処理が開始されると、ステップＳ１１６でハッシュ処理が行われ、ステップＳ１１７で補助情報リストのソートが行われ、その結果がソートされた補助情報リスト３０に格納され、ステップＳ１１８でグループバイ処理が行われて、全体処理を終了する。
【０１５５】
図４０〜図４２はハッシュ処理、およびグループバイ処理の詳細フローチャートである。図４０はハッシュ処理のフローチャートであり、これを第１の実施例における図４と比較すると、例えばステップＳ１２１において図４のステップＳ１のハッシュ対象リストの代わりに、グループバイ対象リストという用語が用いられている点のみが異なっている。
【０１５６】
図４１はグループバイ処理の全体フローチャートである。同図を第１および第２の実施例に対応する図１９と比較すると、ステップＳ７０のグループバイ関数処理の代わりに、ステップＳ１５０でカウント処理が行われる点のみが異なっている。
【０１５７】
図４２は図４１のステップＳ１５０におけるカウント処理の詳細フローチャートである。同図を第１、第２の実施例に対応する図２０と比較すると、ステップＳ７２における関数の初期化の代わりに、ステップＳ１５２でカウンタが０に初期設定されることと、ステップＳ７３で読み出されたレコードに関して関数演算を実行する代わりに、ステップＳ１５３でカウンタのカウント値をインクリメントすることと、ステップＳ７７、およびＳ７９における関数の終了処理に対して、特別な処理が実行されないこととが異なっている。
【０１５８】
図４３はハッシュ処理の経過の説明図である。その意味は図８とほぼ同様であり、図３７で説明したグループバイ対象リストの入力に対するハッシュ処理の経過を示す。
【０１５９】
前半の処理としてのハッシュ処理が終了すると、ハッシュ処理によって得られた補助情報リストのソートが行われる。このソートでは各レコードの２番目の数値である開始ハッシュ値を第１キー、３番目の数値である終了ハッシュ値を第２キーとしてソートを実行することにより、ソートされた補助情報リスト３０として次のものが得られる。
【０１６０】
〔１３，０，０〕〔１８，０，０〕〔１０，０，１〕〔１９，０，１〕〔１４，１，１〕〔１５，１，１〕〔１１，１，２〕
〔１２，２，２〕〔１６，２，２〕〔１７，２，２〕
ソートされた補助情報リスト３０とハッシュ済リスト２１とを用いてグループバイ関数処理を行うことができる。ハッシュ済リストの中のランの数が３であるため、ハッシュ済リスト用入力バッファ３２ａ〜３２ｎの数は３個である。最小ハッシュ値レコード取り出し装置３３による処理の経過が図４４に示される。
【０１６１】
図４４で、最小ハッシュ値を持つレコードが３つの入力バッファの先頭に複数ある場合には、左にある入力バッファにあるレコードが優先して取り出されるものとしているが、この優先順位はどのように付けてもかまわないことは当然である。例えば１番上の左から２番目の状態は、ブロック１３の３つのレコードが１つづつ取り出され、空になった状態を示している。その右側の状態は、空になった最も左側の入力バッファにブロック番号１９のレコードが格納された状態を示している。更にその右側、最上部の最も右側の状態は、最も左側の入力バッファの先頭レコードのみが新たに取り出された状態を示している。このような処理が続けられることにより、最小ハッシュ値レコード取り出し装置３３による処理の結果は以下のようになる。
【０１６２】
３，３，３，３，３，３，３，３，３，１，１，４，１，４，４，１，１，１，１，２，５，２，５，２，２，２，５，２，５，５
ここで同一のハッシュ値を持つレコードが連続するような結果が得られている。この各レコードに対応するハッシュ値を列で示すと以下のようになる。
【０１６３】
０，０，０，０，０，０，０，０，０，１，１，１，１，１，１，１，１，１，１，２，２
２，２，２，２，２，２，２，２，２
この結果はハッシュ値が等しいレコード群のソート装置３４に与えられる。これによってハッシュ値が０を持つ９個のレコード（３，３，３，３，３，３，３，３，３）  がまずソートされ、次にハッシュ値が１を持つ１０個のレコード（１，１，４，１，４，４，１，１，１，１）  がソートされ、最後にハッシュ値が２を持つ１１個のレコード（２，５，２，５，２，２，２，５，２，５，５）  がソートされる。この結果カウント処理装置５２に与えられるレコード列は以下のようになる。
【０１６４】
３，３，３，３，３，３，３，３，３，１，１，１，１，１，１，１，４，４，４，２，２，２，２，２，２，５，５，５，５，５
カウント処理装置５２は、入力レコードキーの値が等しい間はカウント値をインクリメントするため、カウント処理装置５２の出力は以下のようになる。
【０１６５】
〔３，９〕〔１，７〕〔４，３〕〔２，６〕〔５，５〕
次に前述の第４の実施例に対応させて具体的なデータのグループバイ処理について説明する。グループバイ対象データは前述のものと同じとし、ハッシュ関数、ハッシュ表１５のエントリの数、レコードバッファ１４、グループバイ対象リスト用入力バッファ５５、およびハッシュ済リスト用出力バッファ１８のレコード格納数も前述のものと同じとする。ハッシュ処理の結果として得られるハッシュ済リストも前述のものと同じである。補助情報リストの代わりに得られるラン情報は、図３７の補助情報リスト２２の内容に対応して次のようになる。
【０１６６】
（１０，１２）  （１３，１７）  （１８，１９）
このラン情報は１番目のランがブロック番号１０〜１２の連続領域、２番目のランがブロック番号１３〜１７の連続領域、３番目のランがブロック番号１８〜１９に格納されていることを示す。ハッシュ済リストの中にハッシュ値でソートされた３つの列が得られるが、これも前述のものと同じである。
【０１６７】
第４の実施例における後半の処理、すなわちグループバイ関数処理について説明する。図４５はこの場合の最小ハッシュ値レコード取り出し装置３３による処理経過の説明図である。ここではハッシュ済リスト用入力バッファの左から順に１番目のラン、２番目のラン、３番目のランに割り付けてあるが、ハッシュ済リスト入力バッファはランに対して１対１に対応すれば、どのように割り当ててもかまわない。最小ハッシュ値レコードを取り出した結果は次のようになる。
【０１６８】
３，３，３，３，３，３，３，３，３，１，４，１，１，１，４，１，４，１，１，２，５，２，２，５，２，５，５，２，５，２
ハッシュ値が等しいレコード群のソート装置３４にこのレコード列が与えられると、ハッシュ値が０を持つ９個のレコード（３，３，３，３，３，３，３，３，３）  がまずソートされ、次にハッシュ値が１を持つ１０個のレコード（１，４，１，１，１，４，１，４，１，１）  がソートされ、最後にハッシュ値が２を持つ１１個のレコード（２，５，２，２，５，２，５，５，２，５，２）  がソートされる。この結果カウント処理装置５２に与えられるレコード列とその出力は前述のものと同じになる。
【０１６９】
以上において本発明におけるグループバイ処理方式の実施例を詳細に説明したが、次にこのグループバイ処理方式を利用する、相関のあるデータ組み合わせ数え上げ方式について、その実施例を説明する。
【０１７０】
図４６は本発明の組み合わせ数え上げ方式の実施例の構成の説明図である。同図において、本発明の数え上げ方式は相関があると考えられるアイテムの組み合わせの候補を生成する組み合わせ生成部Ｃ（ｉ）  １、グループバイ処理によって組み合わせ候補のトランザクション内部での出現回数をカウントする出現回数数え上げ部Ｇ（ｉ）  ２、出現回数のカウント値が例えばある指定された範囲にある場合にその組み合わせを相関のある組み合わせとして、ラージアイテムセットＬ（ｉ）  の要素として選択する組み合わせ選択部Ｆ３、および組み合わせ選択部Ｆ３の出力するラージアイテムセットから、組み合わせ生成部Ｃ（ｉ）  １によって組み合わせのプルーニングのために使用されるビットマップｂ１５，ｂ（ｉ−１）  ６を生成し、Ｃ（ｉ＋１）  によって使用されるビットマップｂｉ７を追加するビットマップ生成部Ｂ（ｉ）  ４から構成されている。
【０１７１】
図４６の各部は以下のような処理を実行する。
Ｃ（ｉ）
・ｉ＝１の時：同一トランザクションに含まれるアイテムを１つづつＧ（ｉ）  へ送る。
【０１７２】
・ｉ＞２の時：同一トランザクションに含まれるｉ個のアイテムの組み合わせの内、ビットマップフィルタｂ１，ｂ２，．．．，  ｂ（ｉ−１）  により除外されないものをＧ（ｉ）  へ送る。ここで、フィルタｂ１，ｂ２，．．．，  ｂ（ｉ−１）  は図４６のｂ１，．．．，  ｂ（ｉ−１）  に相当するが、その詳細は後述する。
【０１７３】
Ｇ（ｉ）
ｉ個のアイテムが並んだレコードを受け取り、そのレコード全体をキーとして後述のグループバイ処理を行い、各グループに含まれるレコードの個数を計算し、レコードにその個数を付け加えたものを出力する。
【０１７４】
Ｆ
Ｇ（ｉ）  の出力を受け取り、個数が与えられた条件に合うものを長さｉのラージアイテムセットＬ（ｉ）  として出力する。
【０１７５】
Ｂ（ｉ）
Ｆの出力［アイテム１．．．  アイテムｉ，個数］を受け取り、ビットマップフィルタｂｊ（１≦ｊ≦ｉ）に対して、［アイテム１，．．．アイテムｉ］の中から、全てのｊ個のアイテムの組み合わせを取り出し、それぞれの組み合わせに対して、Ｈｊ（ｊ個のアイテムの組み合わせ）で計算されるビット位置に“１”を立てる操作を行う。この時、ｂ１，．．．，  ｂ（ｉ−１）  は既に存在するので、これらを更新する。ｂｉはまだ存在しないので、これを新規に作成し、更新を行う。
【０１７６】
図４７は、本発明の組み合わせの数え上げ方式の全体処理フローチャートである。同図において処理が開始されると、まずステップＳ５０１でアイテムの組み合わせの個数としてのｉが１とされた後に、ステップＳ５０２でＬ（ｉ）  、ここではＬ（１）  が生成される。このＬ（１）  は１個のアイテムのみからなるラージアイテムセットである。
【０１７７】
その後ステップＳ５０３でＬ（ｉ）  の要素数、すなわち組み合わせの数がｉ＋１以上あるか否かが判定される。ここではＬ（１）  のラージアイテムセットの要素数が２個以上であるか否かが判定され、この判定がＹｅｓの場合にはステップＳ５０４でｉの値が１インクリメントされた後に、ステップＳ５０２以降の処理が繰り返される。
【０１７８】
すなわち、ここでは２個のアイテムの組み合わせのうちで出現回数が指定された範囲にあるものの集合としてのラージアイテムセットＬ（２）  の生成がＳ５０２で行われ、続いてＳ５０３以降の処理が実行される。そしてステップＳ５０３でラージアイテムセットＬ（ｉ）  に含まれる要素の数がｉ＋１個以上でないと判定された時点で、処理を終了する。
【０１７９】
図４８はラージアイテムセットＬ（ｉ）  生成処理のフローチャートである。同図において処理が開始されると、まずステップＳ５１０でトランザクションリストＴＬの先頭のトランザクションが読み出され、ステップＳ５１１でｉ個のアイテムの組み合わせ候補が生成され、その組み合わせ候補、すなわちアイテム１からアイテムｉまでの組み合わせが出現回数数え上げ部Ｇ（ｉ）  に送り込まれ、ステップＳ５１２でトランザクションリストが空か否かが判定され、空でない時にはステップＳ５１０以降の処理が繰り返され、トランザクションリストの内部から組み合わせ候補の生成とＧ（ｉ）  への送り込みが実行される。
【０１８０】
ステップＳ５１２でトランザクションリストが空になったと判定されると、ステップＳ５１３で数え上げ部Ｇ（ｉ）  から、アイテムの組み合わせ候補とそのトランザクション内での出現回数、すなわち個数が組み合わせ選択部Ｆに送られ、組み合わせ選択処理が行われる。そしてステップＳ５１４で組み合わせ選択結果がラージアイテムセットＬ（ｉ）  として格納され、同時にラージアイテムセットにおけるアイテムの組み合わせの部分がビットマップ生成部Ｂ（ｉ）  に送られる。ステップＳ５１５でビットマップ生成処理が行われ、ステップＳ５１６で数え上げ部Ｇ（ｉ）  にまだレコードが存在するか否かが判定され、存在する場合にはステップＳ５１３以降の処理が繰り返され、存在しない場合には処理を終了する。
【０１８１】
次に具体例を用いて、本発明の組み合わせの数え上げ方式の処理について更に詳細に説明する。ここでは具体例として、以下の４つのトランザクションＴ１〜Ｔ４からなるトランザクションリストＴＬを対象とする。
【０１８２】
Ｔ１＝［１，２，４］          Ｔ２＝［２，３，６］
Ｔ３＝［１，４，５，６］      Ｔ４＝［１，２，４，５］
各トランザクション内部のアイテムは、その番号順にソートされているものとする。ここではラージアイテムセットとして選択される組み合わせ候補の出現回数、すなわち個数のサポートの最小値として５０％以上の条件を満たす個数、すなわち全トランザクションの数の４に対して個数が２以上となる条件を満たすものを組み合わせ選択部Ｆにおける選択条件とする。
【０１８３】
まず長さ１のアイテムセットＬ（１）  の生成について説明する。図４９〜図５２は長さ１のアイテムの組み合わせ候補の生成とその出現回数数え上げの説明図である。
【０１８４】
はじめに、図４９でトランザクションＴ１［１，２，４］を読み込んで、Ｃ（１）  に入力する。Ｃ（１）  では、同一トランザクション中に含まれるアイテムを１つづつ、すなわち［１］，［２］，［４］の３個を出現回数数え上げ部Ｇ（１）  に入力する。Ｇ（１）  では、Ｃ（１）  から入力されたアイテム、［１］，［２］，［４］の出現個数を数え上げ、アイテムと個数をペアとして保持する。ここでは、アイテム［１］，［２］，［４］がそれぞれ１回づつ入力されたので、［アイテム，個数］の形式で、［１，１］，［２，１］，［４，１］を保持する。以上で、Ｔ１についての処理が終わる。
【０１８５】
１つのトランザクションについてＧ（１）  への入力処理が終了したら、Ｃ（１）  にもどって、次のトランザクションの処理を行う。図５０では、Ｔ２＝［２，３，６］について、［２］，［３］，［６］の３個のアイテムとしてＧ（１）  に入力する。Ｇ（１）  では、それまでのトランザクションの処理で数え上げたアイテムと個数に、入力されたアイテムと個数を追加していく。アイテム［２］はＴ１とＴ２の両方で入力されるので、Ｔ２の処理が終了した段階では、［アイテム，個数］の形式で［２，２］と保持される。
【０１８６】
以下同様にすべてのトランザクションについて、Ｃ（１）  でアイテムを１つづつＧ（１）  に入力して、Ｇ（１）  で数え上げを行う。Ｔ４までのトランザクションをすべて処理した結果、［アイテム，個数］の組は、［１，３］，［２，３］，［４，３］，［３，１］，［６，２］，［５，２］となる。この結果が図９である。
【０１８７】
すべてのトランザクションについてＧ（１）  への入力処理が終了したら、Ｇ（１）  から［アイテム，個数］の組を取り出し、Ｆにおいてサポートの最小値を満たすアイテムを選ぶ。図５３〜図５８はこの処理の説明図である。図５３では、［１，３］の個数３がサポートの最小値５０％を満たしているので、これをラージアイテムセットＬ（１）  に登録する。と同時に、Ｂ（１）  では、アイテム［１］をビットマップｂ１に登録する。ここではアイテムに対応するビット位置（０〜５）は以下のハッシュ関数Ｈ１によって得られる。
【０１８８】
Ｈ１（アイテム１）＝アイテム１の番号ｍｏｄ６．
この場合、トランザクション中のユニークなアイテムの総個数が６個であるから、ビットマップのビット数はそれに合わせて６とした。もし、ビットマップがメモリに入らない、あるいは他の処理のためにメモリを予約したいのであれば、ユニークなアイテムの総個数６より小さな値を取ることも可能である。ビットマップのすべてのビットは、最初は“０”である。アイテム［１］にハッシュ関数を適用すると、１ｍｏｄ６＝１を得るので、ｂ１の１に対応する上から２番目のビットに“１”を立てる。
【０１８９】
次に、図５４でＧ（１）  から［２，３］を取り出し、アイテム［２］の個数３がサポートの最小値である５０％以上の条件を満たすのでラージアイテムセットとして登録する。同時に、２ｍｏｄ６＝２であるから、Ｂ（１）  ではビットマップｂ１の３番目のビットに“１”を立てる。
【０１９０】
図５５，図５７，図５８ではアイテムと個数のペアのうち［４，３］，［６，２］，［５，２］についてサポートの最小値の条件を満たしているので、［４］，［６］，［５］と個数の組をラージアイテムセットＬ（１）  に登録し、同時にビットマップｂ１のハッシュ関数値に対応する位置に“１”をセットする。
【０１９１】
しかし、図５６では［３，１］について個数１がサポートの最小値の条件を満たしていないので、ラージアイテムセットＬ（１）  およびビットマップｂ１への登録は行わない。処理の結果、ビットマップｂ１＝｛１，１，１，０，１，１｝となり、長さ１のラージアイテムセットＬ（１）  ＝｛［１，３］，［２，３］，［４，３］，［６，２］，［５，２］｝が生成される。
【０１９２】
次に長さ２のラージアイテムセットＬ（２）  の生成について説明する。図５９〜図６２はアイテムの組み合わせ候補の数え上げまでの説明図である。長さ２のアイテムの組み合わせ生成では、既に作成されたビットマップｂ１を利用する。はじめに、図５９でトランザクションＴ１＝［１，２，４］を読み込んで、ビットマップｂ１でセットされたアイテムだけを使って長さ２のアイテムの組み合わせの候補を生成する。ここでは、ｂ１に３つのアイテムが登録されているので、［１］，［２］，［４］の３つのアイテムから［１２］，［１４］，［２４］の３つのアイテムの組み合わせの候補を生成し、数え上げ部であるＧ（２）  に入力する。Ｇ（２）  では、Ｃ（２）  から入力されたアイテムの組み合わせ［１２］，［１４］，［２４］の出現個数を数え上げ、アイテムと個数を組として保持する。［１２］，［１４］，［２４］がそれぞれ１回づつ入力されたので、［アイテム１アイテム２，個数］の形式で、［１２，１］，［１４，１］［２４，１］を保持する。以上で、Ｔ１についての処理が終わる。
【０１９３】
次のトランザクションＴ２＝［２，３，６］のアイテムをビットマップｂ１でフィルタリングすると、アイテム［３］が落とされるので、その結果アイテムの組み合わせの候補として［２６］１つだけを図６０でＧ（２）  に入力する。Ｔ３，Ｔ４についても同様の処理を行うが、Ｔ３とＴ４にはビットマップｂ１でふるいにかけられて落とされるアイテムがないので、トランザクションから生成されるすべての長さ２のアイテムの組み合わせを図６１、図６２でＧ（２）  に入力する。
【０１９４】
すべてのトランザクションについてＧ（２）  への入力処理が終了したら、Ｇ（２）  から、［アイテム１アイテム２，個数］を取り出し、Ｆで個数がサポートの最小値の条件を満たすものを選ぶ。この処理を図６３〜図７２に示す。［１２，２］の個数２がサポートの最小値５０％以上の条件を満たしているので、アイテムの組み合わせ候補［１２］と出現回数を図６３でラージアイテムセットＬ（２）  に登録する。同時に、Ｂ（２）  では、アイテムの組み合わせ［１２］の各アイテム［１］，［２］をビットマップｂ１に登録する。この場合、ｂ１のビット位置１と２に“１”を立てる。さらに、［１２］については以下のハッシュ関数Ｈ２で計算されるビットマップｂ２（ビット位置０〜４）のビット位置３に“１”を立てる。
【０１９５】
Ｈ２（アイテム１，アイテム２）＝（アイテム１の番号＋アイテム２の番号）ｍｏｄ５．
このハッシュ関数Ｈ２ではアイテム１アイテム２の番号の和のｍｏｄ５を取るものを用いたので、ビットマップのビット数はこれに合わせて５とした。最初は、ｂ２のすべての５つのビットは“０”である。なお、ここでのハッシュ関数は例として設定したもので、実際にはハッシュ関数の効率を考慮して任意に設定できる。また、ビットマップの大さもメモリの大きさを考慮に入れて任意に設定できる。ｂ１では常に１つのアイテムで“１”を立てるビット位置を決めるが、ｂ２は２個のアイテムを引数としたハッシュ関数によりビット位置を決定する。
【０１９６】
図６４，図６５，図６７，図６９に示すように、［１４，３］，［２４，２］，［１５，２］，［４５，２］についてはサポートの最小値を満たすので、アイテムをラージアイテムセットＬ（２）  に登録し、同時にビットマップｂ１とｂ２を更新する。これに対して図６６，図６８，図７０〜図７２では、サポートの最小値が満たされていないためアイテムセットへの登録とビットマップの更新は行われない。以上の処理の結果、長さ２のラージアイテムセットＬ（２）  ＝｛［１２，２］，［１４，３］，［２４，２］，［１５，２］，［４５，２］｝および、ｂ１＝｛０，１，１，０，１，１｝，ｂ２＝｛１，１，０，１，１｝が生成される。この結果を図７２に示す。
【０１９７】
次にＬ（３）  の生成について説明する。図７３〜図７６は組み合わせ候補数え上げまでの説明図である。長さ３のアイテムの組み合わせの生成では長さ２のラージアイテムセットを作成した際に生成したビットマップｂ１およびｂ２を利用する。まず、トランザクションＴ１＝［１，２，４］を読み込んで、ビットマップｂ１でセットされたアイテムだけを使って長さ３のアイテムの組み合わせを生成する。ここでは、［１］，［２］，［４］の３つのアイテムがｂ１にセットされている。次に長さ２のアイテムの組み合わせ［１２］，［１４］，［２，４］がビットマップｂ２でセットされているかどうかを調べる。この場合、ｂ２［Ｈ２（１，２）］＝ｂ２［Ｈ２（１，４）］＝ｂ２［Ｈ２（２，４）］＝１とすべてセットされていることから［１２４］を組み合わせ候補としてＧ（３）  に入力する。この処理を図７３に示す。
【０１９８】
図７４に示すように、Ｔ２＝［２，３，６］の場合、ｂ１に［３］がセットされていないためふるい落とされて、トランザクションの長さが２となってしまうため、長さ３のアイテムの組み合わせ候補が生成できずＧ（３）  への入力は行わない。
【０１９９】
Ｔ３＝［１，４，５，６］の場合、［１］，［４］，［５］，［６］に対応するｂ１のビットがセットされているので、４つの長さ３のアイテムの組み合わせ［１４５］，［１４６］，［１５６］，［４５６］が考えられるが、まず、それぞれについて、ビットマップｂ２のチェックを行う。［１４５］の場合、［１４］，［１５］，［４５］のすべてについて、対応するｂ２のビットがセットされているので、組み合わせの候補として図７５でＧ（３）  に入力する。
【０２００】
しかし、［１４６］の場合、［１４］，［４６］に対応するｂ２のビットはセットされているが、［１６］のビットがセットされていないため、［１４６］を組み合わせの候補としてＧ（３）  に入力しない。同様に、［４５６］のすべての２個のアイテムの組み合わせ［４５］，［４６］，［５６］に対応するｂ２のビットはセットされているので、［４５６］は組み合わせの候補としてＧ（３）  に入力されるが、［１５６］の中の［１６］のｂ２のビットはセットされていないためＧ（３）  に入力されない。
【０２０１】
Ｔ４＝［１，２，４，５］についても同様なｂ１とｂ２のチェックを行い、組み合わせの候補として［１２４］と［１４５］をＧ（３）  に入力する。この結果を図７６に示す。
【０２０２】
この例では、不要な候補の生成をふせぐため、長さ３のアイテムの組み合わせ候補を生成する際に、すべての長さ２のアイテムの組み合わせに対応するビットマップｂ２のビットをチェックした。この手法は、不要な数え上げを防止するプルーニングとして有効であるが、例えば、処理に使用できるメモリの量が十分でない場合には各アイテムのチェック、あるいは２の長さのアイテムの組み合わせのチェックを行わない方法、すなわちｂ１あるいはｂ２を使用しない方法を取ることもできる。また、ｂ１とｂ２を使うが、チェックする長さ２の組み合わせを少なくする方式もあり得る。
【０２０３】
例えば、長さ３のアイテムの組み合わせを生成する際に、先頭の長さ２の組み合わせ１つだけをチェックするやり方を考えることが出来る。もちろん、この様にすると、チェック漏れが発生しやすくなり、組み合わせ候補は増大するのでＧ（３）  での処理の負荷は高くなるが、チェック作業の負荷を減らすことが出来る。どの方式が最も高速であるかは、データや、プログラムの実装方式や、システムの特性に依存する。
【０２０４】
Ｇ（３）  への入力処理が終了したら、図７７〜図７９に示すように、Ｇ（３）  から［アイテム１アイテム２アイテム３，個数］の組を取り出し、Ｆで個数がサポートの最小値の条件を満たすアイテムを選ぶ。図７７では、［１２４，２］の個数２がサポートの最小値５０％以上という条件を満たしているので、これを長さ３のラージアイテムセットＬ（３）  に登録する。同時に、Ｂ（３）  では、［１２４］の各アイテム［１］，［２］，［４］それぞれに対応するビットマップｂ１のビット位置に“１”を立てる。また、ハッシュ関数Ｈ３を用いて、すべての３つのアイテムの組み合わせ［１２４］に対応するビットマップｂ３のビット位置に“１”を立てる。
【０２０５】
Ｈ３（アイテム１，アイテム２，アイテム３）＝（アイテム１の番号＋アイテム２の番号＋アイテム３の番号）ｍｏｄ５．
同時に、［１２４］の中から、２個のアイテムの組み合わせを取り出し、ビットマップｂ２を生成することもできるが、ここではｂ１とｂ３のみを生成する。
【０２０６】
続いて行われる図７８，図７９の処理の結果、長さ３のラージアイテムセットＬ（３）  ＝｛［１２４，２］，［１４５，２］｝，ビットマップｂ１＝｛０，１，１，０，１，１｝，ｂ３＝｛１，０，１，０，０｝が生成される。
【０２０７】
図７９では、長さ３のラージアイテムセットＬ（３）  の個数が２個であり、図４７のステップＳ５０３における終了条件の４個以下となったので処理を終了する。以上で、ラージアイテムセットの数え上げ処理が終了し、この結果を用いて相関ルールを生成することが出来る。
【０２０８】
以上に述べた実施例では、ｉ＞１の場合のＣ（ｉ）  では、各トランザクションに対し、ビットマップｂ１，ｂ（ｉ−１）  により除外されない長さｉのアイテムの組み合わせ候補が生成される。それと同時に、各トランザクションに対し、ビットマップｂ１，ｂ（ｉ−１）  により除外されないアイテムのみを新たなトランザクションとして格納することもできる。これにより、ｉ＞２の場合、基のトランザクション群ＴＬではなく、Ｃ（ｉ−１）  で生成されたリダクションされたトランザクション群からアイテムの組み合わせの候補を生成することができる。
【０２０９】
以上において相関ルール生成のために使用されるデータ組み合わせの数え上げ方式について詳細に説明したが、以上の説明はいわゆる基本相関分析に関するものである。相関分析の手法としては、この基本相関分析に加えて階層相関分析と時系列分析という２つの手法が知られており、本発明はこれら２つの手法に対しても適用可能である。
【０２１０】
そこで、まず階層相関分析におけるデータ組み合わせの数え上げ方式について、具体例を用いて説明する。図８０はこの階層相関分析に用いられるデータの階層構造の具体例の説明図である。同図において、例えばアイテム１のエビス  ５００ｍｌと、アイテム２のラガー  ３５０ｍｌとの親はアイテム７としてのビールであり、またアイテム７のビール、アイテム８のジュース、アイテム９の牛乳の親はアイテム１０の飲料であるという階層構造が示されている。
【０２１１】
階層相関分析は、分類法が異なるレベルにあるデータを対象とするデータベースのマイニングに有効である。前述の基本相関分析では例えばエビスビール  ５００ｍｌを購入する顧客が同時に「ピーナッツ」を購入するという相関ルールを生成するこはできるが、より一般化されたルールとしてビールまたは飲料を購入する顧客が同時にピーナッツを購入するというルールを生成することができない。すなわち基本相関分析のみでは、多くのより一般的で重要な相関ルールの生成が行われないことになる可能性がある。
【０２１２】
階層相関分析と基本相関分析との違いは、アイテムの組み合わせを生成する組み合わせ生成部Ｃ（ｉ）  の動作にある。基本分析の場合には、それぞれのトランザクションに含まれるアイテムのみで組み合わせが生成されるのに対して、階層分析の場合には階層構造における親データも含めて組み合わせが生成される。しかし１つのアイテムとそのアイテムの親からなる組み合わせは生成されない。
【０２１３】
例えばトランザクションＴ＝［１，３，５］から生成される２個のアイテムの組み合わせとして、基本分析で生成される［１３］，［１５］，［３５］以外に、次のアイテムの組み合わせがある。
【０２１４】
［１８］，［３７］，［７８］，［１９］，［５７］，［７９］，［３９］，［５８］，［８９］
これに対して生成されないアイテムの組み合わせとしては次のものがある。
【０２１５】
［１７］，［１１０］，［７１０］，［３８］，［３１０］，［８１０］，［５９］，［５１０］，［９１０］
階層相関分析のための組み合わせ数え上げ方式の具体例を説明するためのトランザクションリストＴＬとして、次の４つのトランザクションＴ１〜Ｔ４を用いる。
【０２１６】
Ｔ１＝［２，３，５，６］，    Ｔ２＝［１，３，５］
Ｔ３＝［１，２，４］          Ｔ４＝［５］
アイテムの組み合わせのうちからラージアイテムセットとして選択される時のサポートの最小値は５０％、最大値は７５％とする。トランザクションが４個であるため、出現回数が２、および３の場合に、アイテムの組み合わせ候補がラージアイテムセットに入れられることになる。
【０２１７】
図８１〜図８４は１個のみのアイテムの組み合わせ候補の数え上げとしてのＧ（１）  までの処理を示す。図８１では最初のトランザクション［２，３，５，６］が組み合わせ生成部Ｃ（１）  に与えられ、図８０で説明した親データも含めて１個ずつのアイテムが数え上げ部Ｇ（１）  に出力され、アイテムの数え上げが行われる。
【０２１８】
図８２においてはトランザクションＴ２＝［１，３，５］が、また図８３においてはＴ３＝［１，２，４］が、また図４１においては［５］が組み合わせ生成部Ｃ（１）  に与えられ、親を含む１個ずつのアイテムが数え上げ部Ｇ（１）  に出力され、１個ずつのアイテムの数え上げが行われ、最終的な結果が図８４において得られる。
【０２１９】
図８５〜図９４は、図８１〜図８４で数え上げられた１個ずつのアイテムの出現回数を用いて、出現回数がサポートの値を満たす２、または３であるアイテムをラージアイテムセットの要素として選択し、また選択されたラージアイテムセットに対するビットマップｂ１を作成する処理の説明図である。図８５において、アイテムとその出現回数としての最初のデータ［２，２］が組み合わせ選択部Ｆに与えられ、これがラージアイテムセットのＬ（１）  の要素として出力されると同時に、そのアイテムの番号２がビットマップ生成部Ｂ（１）  に与えられ、次のハッシュ関数によって与えられるビット位置に対して“１”が立てられる。
【０２２０】
アイテム番号ｍｏｄ１０
図８６においては［７，３］、図８８においては［３，２］、図８９においては［８，３］、図９０においては［５，３］、図９１においては［９，３］、図９３においては［１，２］がラージアイテムセットＬ（１）  の要素として選択され、ビットマップｂ１のハッシュ関数によって指定される位置に“１”が立てられる。
【０２２１】
これに対して図８７においては［１０，４］、図９２においては［６，１］、図９４においては［４，１］が組み合わせ選択部Ｆに与えられるが、これらはサポート値を満たしていないためにラージアイテムセットＬ（１）  としては選択されず、ビットマップｂ１の対応する位置に“１”が立てられることもない。
【０２２２】
図９５〜図９８は、２個のアイテムの組み合わせ候補の数え上げ処理としてのＧ（２）  までの処理の説明図である。図９５においては、トランザクションＴ１＝［２，３，５，６］が組み合わせ生成部Ｃ（２）  に与えられ、図８０の階層構造における親も含めて２個のアイテムの組み合わせ候補が数え上げ部Ｇ（２）  に与えられ、２個のアイテムの組み合わせ候補の出現回数がカウントされる。
【０２２３】
但しこの場合、２個のアイテムの組み合わせ候補の生成において、図８５〜図９４で作成されたビットマップｂ１の対応する位置に“１”が立っていないアイテムは使用されない。例えば階層構造において最上位の親である１０は、前述のハッシュ関数によって指定されるビット位置０に“１”が立っていないために、組み合わせ候補を生成するためには使用されない。
【０２２４】
図９６においてはトランザクションＴ２＝［１，３，５］、図９７においてはトランザクションＴ３＝［１，２，４］、図９８においてはトランザクションＴ４＝［５］が組み合わせ生成部Ｃ（２）  に与えられ、数え上げ部Ｇ（２）  によって２個のアイテムの組み合わせ候補の出現回数がカウントされる。ここで例えば図９７においてＣ（２）  に入力されるトランザクションに含まれるアイテム４は、対応するビット位置に“１”が立っていないために組み合わせ候補の生成には使用されないが、その親であるアイテム８は使用される。また、図９８においてはトランザクションに含まれるアイテムが１個のみであるために、組み合わせ候補の生成は行われない。
【０２２５】
図９９〜図１０９はＧ（２）  によってカウントされた２個のアイテムの組み合わせ候補のうちで、与えられたサポート条件を満足する組み合わせ候補のラージアイテムセットＬ（２）  の要素としての選択処理の説明図である。図９９においては、最初の組み合わせ候補としての［２３，１］が組み合わせ選択部Ｆに入力されるが、ここで出現回数１はサポート条件を満たしていないために、この組み合わせ候補はラージアイテムセットＬ（２）  としては選択されず、従ってビットマップへの登録も行われない。
【０２２６】
図１００においては、組み合わせ候補［２８，２］が組み合わせ選択部Ｆに与えられ、この組み合わせ候補はサポート条件を満たしているため、ラージアイテムセットＬ（２）  の要素として選択されると同時に、ビットマップ生成部Ｂ（２）  によってビットマップｂ１、およびｂ２の対応する位置へのビット設定が行われる。これらのビットマップのうちｂ１に対して使用されるハッシュ関数は図８５〜図９４で説明したものと同じである。これに対してｂ２の設定に対して使用されるハッシュ関数は次のものである。
【０２２７】
（アイテム１の番号＋アイテム２の番号）ｍｏｄ７
図１０１，図１０２，図１０５，図１０６，図１０７，図１０８においては、組み合わせ選択部Ｆに入力されるアイテムの組み合わせ候補がラージアイテムセットＬ（２）  の要素として選択され、ビットマップｂ１、およびｂ２の対応する位置へのビット設定が行われる。
【０２２８】
これに対して図１０３，図１０４，図１０９においては、組み合わせ選択部Ｆに入力されるアイテムの組み合わせ候補がサポート条件を満たしていないため、ラージアイテムセットの要素としての選択は行われず、またビットマップの対応するビット位置へのビット設定も行われない。
【０２２９】
図９９〜図１０９において組み合わせ候補のうち、［５８，２］から［１９，１］に対する処理は示されていないが、最終的に得られる結果は図１０９に示されている。
【０２３０】
図１１０〜図１１３は３個のアイテムの組み合わせ候補の数え上げ処理としてのＧ（３）  までの説明図である。図１１０において、トランザクションＴ１＝［２，３，５，６］が組み合わせ生成部Ｃ（３）  に入力され、アイテムの親も含めて３個のアイテムの組み合わせ候補が生成され、その出現回数がＧ（３）  によってカウントされる。但しこの場合、ビットマップｂ１において“１”が立っていないビット位置に対応するアイテム、またはビットマップｂ２の対応する位置に“１”が立っていない２個のアイテムの組み合わせを含む組み合わせ候補は生成されない。
【０２３１】
例えば前述と同様にｂ１において“１”が立っていない階層構造の最上位の親である１０は組み合わせ候補の生成には使用されない。また例えば［２３５］は３個のアイテムのうちの２個のアイテムの組み合わせの中に、図９９〜図１０９で説明したハッシュ関数値に対応する位置に“１”が立っていないものがあるため、組み合わせ候補としては生成されない。
【０２３２】
同様にして図１１１においてはＴ２＝［１，３，５］、図１１２においてはＴ３＝［１，２，４］が組み合わせ生成部Ｃ（３）  に与えられ、Ｇ（３）  によって組み合わせ候補のカウントが行われる。
【０２３３】
これに対して図１１３においては、トランザクションに含まれるアイテムの個数が１個のみであるため、組み合わせ候補は生成されず、図１１２において得られた結果がこの処理の最終結果となる。
【０２３４】
図１１４〜図１１９は、図１１０〜図１１３で生成された３個のアイテムの組み合わせ候補のうち、サポート条件を満足する候補のラージアイテムセットＬ（３）  への選択処理の説明図である。図１１４において、選択部Ｆに入力される最初の組み合わせ候補［３５７，２］はサポート条件を満足しているため、ラージアイテムセットＬ（３）  の要素として選択されると同時に、３個のアイテムの組み合わせがビットマップ生成部Ｂ（３）  に与えられ、ビットマップｂ１、およびｂ３の設定が行われる。
【０２３５】
ここでビットマップｂ１の設定に使用されるハッシュ関数は図８５〜図９４で説明したものと同じであるが、ｂ３の設定に使用されるハッシュ関数は次に示すものである。
【０２３６】
（アイテム１の番号＋アイテム２の番号＋アイテム３の番号）ｍｏｄ７
図１１５においては組み合わせ候補［３７９，２］、図１１６においては［５７８，２］、図１１７においては［７８９，２］が組み合わせ選択部Ｆに入力され、これらの組み合わせ候補はいずれもサポート条件を満たしているために、ラージアイテムセットＬ（３）  の要素として選択されると同時に、ビットマップへのビット設定が行われる。
【０２３７】
これに対して図１１８においての［１５８，１］、図１１９においての［１２８，１］、および図示しない［１８９，１］の入力時においては、いずれもサポート条件を満たしていないために、ラージアイテムセットの要素としての選択は行われず、ビットマップへの設定も行われない。そしてこの処理の最終結果は図１１９に示すものとなる。
【０２３８】
図１２０〜図１２３は４つのアイテムの組み合わせ候補の生成と、その数え上げ処理の説明図であるが、図１２０〜図１２３のいずれにおいても４つのアイテムの組み合わせ候補は生成されず、組み合わせの数え上げ処理は終了する。
【０２３９】
相関分析の次の手法としての時系列分析への本発明の応用について説明する。この時系列分析は、長期間に渡る顧客の商品購入パターンの分析に利用される。顧客が第１のアイテムを購入した後に、所定の期間内に第２のアイテムを購入する確率を相関ルールとして知ることができれば、例えば小売業者はより効果的に在庫管理を行うことができる。
【０２４０】
図１２４は顧客の長期間に渡る商品購入パターンとしてのシーケンスリストの説明図である。この図で第１のシーケンスは、ある顧客がアイテム３を１個だけ購入した後に、例えば次の日にアイテム８だけを購入し、更にその１週間後にアイテム３と８とを１つずつ購入したというような、商品購入の時系列パターンを示している。
【０２４１】
図１２４の説明において、１つのエレメントは前述のトランザクション、すなわち１枚のレシートに対応し、例えばアイテム３と８が同じエレメントに属するということは、アイテム３と８とが同一のレシートに記録されていることを示す。
【０２４２】
以下に説明する時系列分析においてはサポートの最小値を４０％とする。図１２４のシーケンスリストは５つのシーケンスによって構成されているために、４０％のサポートはアイテムの組み合わせの出現回数が２以上であることを示す。
【０２４３】
時系列分析における組み合わせ生成部Ｃ（ｉ）  、数え上げ部Ｇ（ｉ）  、組み合わせ選択部Ｆ、およびビットマップ生成部Ｂ（ｉ）  の動作を以下に説明する。
Ｃ（ｉ）
・ｉ＝１の時：同一シーケンスに含まれるアイテムを１つづつＧ（ｉ）  へ送る。
【０２４４】
・ｉ＞２の時：同一シーケンスに含まれるｉ個のアイテムの順列の内、ビットマップフィルタｂ１，ｂ２，．．．，  ｂ（ｉ−１）  により除外されないものをＧ（ｉ）  へ送る。
【０２４５】
Ｇ（ｉ）
ｉ個のアイテムの順列を受け取り、後述するグループバイ処理を行い、その個数を付け加えたものを出力する。
【０２４６】
Ｆ
Ｇ（ｉ）  の出力を受け取り、個数が与えられた条件に合うものを長さｉのラージシーケンスＬ（ｉ）  として出力する。
【０２４７】
Ｂ（ｉ）
Ｆの出力を受け取り、ビットマップフィルタｂｊ（１≦ｊ≦ｉ）に対して、ｉ個のアイテムの順列の中から、全てのｊ個のアイテムの順列を取り出し、それぞれの順列に対して、Ｈｊ（ｊ個のアイテムの順列）で計算されるビット位置に“１”を立てる操作を行う。
【０２４８】
ｊ個のアイテムの順列の内部表現は
［アイテム１，．．．，  アイテムｊ，セパレータ１，．．．，  セパレータ（ｊ−１）  ］、
セパレータｋ（１≦ｋ≦ｊ−１  ）はアイテムｋとアイテム（ｋ＋１）  が同じエレメントに属する場合は０、異なるエレメントに属する場合は１となる。
【０２４９】
ハッシュ関数Ｈｊは、
Ｈｊ（アイテム１，．．．，  アイテムｊ，セパレータ１，．．．，  セパレータ（ｊ−１））＝（アイテム１の番号＋．．．，＋アイテムｊの番号＋セパレータ１＋．．．，＋セパレータ（ｊ−１））ｍｏｄＮとする。Ｎはビットマップのビット数を示す。
【０２５０】
図１２５〜図１２９はシーケンスリストに属するアイテム１個ずつの出現回数の数え上げ処理としてのＧ（１）  までの処理の説明図である。図１２５〜図１２９において、それぞれのシーケンスリストに含まれるアイテムが１個ずつＧ（１）  によってカウントされ、最終結果として図１２９が得られる。
【０２５１】
図１３０〜図１３７は、図１２５〜図１２９で得られたアイテム１個ずつの出現回数のカウント値に対応して、サポート値が４０％以上のアイテムを選択してラージシーケンスＬ（１）  を作成する処理と、同時にビットマップｂ１を作成する処理の説明図である。例えば図１３０において入力されるアイテム３はその個数が４であり、サポートの最小値を満たしているためラージシーケンスＬ（１）  の要素とされ、同時にそのアイテム３はビットマップ生成部Ｂ（１）  に与えられ、ビットマップｂ１へのビット設定が行われる。ここでビットマップｂ１のビット数は８である。
【０２５２】
図１３１〜図１３４においては、組み合わせ選択部Ｆに入力されるアイテムの出現回数がサポート値を満たしているため、それらのアイテムはラージシーケンスＬ（１）  に追加されるが、図１３５〜図１３７で入力されるアイテムの出現回数はサポート値以下であるためラージシーケンスＬ（１）  への登録は行われず、この処理の最終結果は図１３７となる。
【０２５３】
図１３８〜図１４２は２個のアイテムの組み合わせ候補の数え上げ処理の説明図である。図１３８において、Ｃ（２）  によって、ビットマップｂ１を用いたフィルタリングによって落とされないアイテムを用いて２つのアイテムの組み合わせ候補が生成され、その出現回数がＧ（２）  によってカウントされる。この組み合わせにおいては、シーケンスにおける順序があるため、また同じエレメントに属するか否かによって、次の３つの組み合わせ候補は別々のものとしてカウントされる。
【０２５４】
＜（３）  （８）  ＞，＜（８）  （３）  ＞，＜（３，８）  ＞
図１３９〜図１４２において、同様にして２つのアイテムの組み合わせ候補の数え上げが行われるが、例えば図１３９においてアイテム１，２、および６はビットマップｂ１によってフィルタリングされ、組み合わせ候補の生成には使用されない。また、図１４２においてシーケンスに含まれるアイテムは１個のみであるため、２個のアイテムの組み合わせ候補は生成されず、図１４１が最終結果となる。
【０２５５】
図１４３〜図１５３は、図１３８〜図１４２において作成された２個のアイテムの組み合わせ候補のうち、サポート値を満たすものによるラージシーケンスＬ（２）  の作成と、ビットマップ作成部Ｂ（２）  によるビットマップｂ１、およびｂ２生成の処理の説明図である。図１４３において、組み合わせ選択部Ｆに入力される２個のアイテムの組み合わせ候補はサポート値を満たしているため、ラージシーケンスＬ（２）  の要素とされ、２つのアイテム３，８に対してハッシュ関数Ｈ１、およびＨ２を用いてビットマップｂ１、およびｂ２のビット設定処理が行われる。
【０２５６】
図１４４〜図１４７、図１５１〜図１５３において入力される組み合わせ候補はサポート値を満たしていないため、ラージシーケンスへの登録、およびビットマップのビット設定は行われない。
【０２５７】
これに対して、図１４８〜図１５０において組み合わせ生成部Ｆに入力される組み合わせ候補はサポート値を満たしているため、ラージシーケンスＬ（２）  への登録と、ビットマップのビット設定処理が行われ、この処理の最終結果は図１５３となる。
【０２５８】
図１５４〜図１５８は、３個のアイテムの組み合わせ候補のＧ（３）  によるカウント処理などの説明図である。図１５４において最初のシーケンスが組み合わせ生成部Ｃ（３）  に入力されるが、このシーケンスから生成される３個のアイテムの組み合わせ候補はいずれもビットマップｂ２によってフィルタリングされ、Ｇ（３）  には入力されない。
【０２５９】
図１５５、および図１５７において、組み合わせ生成部Ｃ（３）  によって生成される３個のアイテムの組み合わせ候補１種類だけがそれぞれＧ（３）  によってカウントされる。図１５６および図１５８においては、Ｇ（３）  に入力される組み合わせ候補は存在せず、この処理の最終結果は図１５８となる。
【０２６０】
図１５９は、図１５４〜図１５８において作成された３個のアイテムの組み合わせ候補のうちサポート値を満足するものをラージシーケンスＬ（３）  に登録し、同時にビットマップｂ１、およびｂ３へビット設定を行う処理の説明図である。３個のアイテムの組み合わせ候補は１種類のみであり、組み合わせ生成部Ｆによってこの組み合わせ候補がラージシーケンスＬ（３）  とされ、またこの組み合わせ候補の中のアイテムを用いてビットマップｂ１、およびｂ３の設定が行われる。ラージシーケンスＬ（３）  の要素数は１個のみとなるため、組み合わせの数え上げ処理はここで終了する。
【０２６１】
図１６０は、従来技術の図１６８および図１７０におけると同じトランザクションリストを用いて、本発明における基本相関分析のためのアイテム組み合わせの数え上げ処理の流れを説明したものである。図１６０においては、例えばラージアイテムセットＬ１に対応して作成されるビットマップｂ１を用いて、トランザクションリストから組み合わせ生成部Ｃ（２）  によってフィルタリングされないアイテム２個の組み合わせ候補が生成され、数え上げ部Ｇ（２）  に与えられる点に本発明の基本的な特徴がある。
【０２６２】
このビットマップを生成する処理は簡単なものであり、またビットマップの容量は利用できるメモリ量にフィットするサイズにすることが常に可能であるため、図１６８における結合処理の処理量が大きいという問題点や、図１７０におけるハッシュ木の容量が利用できるメモリ量よりも大きくなる場合があるというような問題点を解決することが可能である。
【０２６３】
以上において本発明のデータ組み合わせの数え上げ方式の全体的処理の説明を終了し、次に組み合わせの出現回数数え上げ部Ｇ（ｉ）  において実行されるグループバイ処理について説明する。
【０２６４】
アイテムの組み合わせ候補の数え上げには本発明におけるグループバイ処理方式が用いられるが、その処理について具体例を用いて以下に説明する。
アイテムが１個のみのときにその出現回数を数え上げる場合には、アイテム番号をレコードのキー値と考えることによって、前述のグループバイ処理方式をそのまま用いることができるため、ここでは２個のアイテムの組み合わせ候補の数え上げを具体例として説明する。またグループバイ処理の方式としては、前述の第１の実施例と同様にまずハッシュ処理によってハッシュ済みリストと補助情報リストを作成した後に、グループバイ関数処理として同じキーの値を持つレコードの数え上げを行う場合を説明する。
【０２６５】
入力レコードは次の１６件であり、それぞれのレコードはアイテムの番号を２つ持っており、その２つのアイテム番号によってハッシュ処理、およびソート処理におけるキーが決定されるものとする。
【０２６６】
［１２］［１４］［２４］［２６］［１４］［１５］［１６］［４５］
［４６］［５６］［１２］［１４］［１５］［２４］［２５］［４５］
このような場合のキーの比較方法としては種々考えられるが、ここでは一例として辞書順を用いることにする。すなわち２つのレコードを比較する時、まず１番目のアイテム番号で比較して大小がつけばそのままレコードのキーの大小関係とし、１番目のアイテム番号が等しければ２番目のアイテム番号を比較して、大小がつけばそのままキーの大小関係とし、２番目のアイテム番号も等しければ更に３番目のアイテム番号を比較するというよな比較を続け、最後のアイテム番号まで等しければ２つのレコードのキーの値は等しいとする。そこで例えば［１２］と［１４］とは、１番目のアイテム番号は等しいが、２番目のアイテム番号で比較することにより、［１２］より［１４］の方がキーの値が大きいとすることができる。
【０２６７】
ハッシュ関数としては適当なものを選んで使用することができるが、ここではハッシュ関数の一例として、次式のようにアイテム番号の総和に対して、３で割った時の剰余をとることにする。つまり［１２］のハッシュ値は（１＋２）ｍｏｄ３＝０で０となり、［１４］のハッシュ値は（１＋４）ｍｏｄ３＝２で２となる。
【０２６８】
【数１】
0003601719.tif 000002
【０２６９】
ここでＩｋ  はアイテム番号、Ｒはレコード［Ｉ１，Ｉ２，．．．，Ｉｉ  ］
前述のグループバイ処理方式の第１の実施例と同様に、１６件の入力レコードからまずハッシュ済みリストが生成される。この時図３のハッシュ表１５の大きさは３、レコードバッファ１４は４つ分のレコードの格納領域を持ち、ハッシュ済みリスト用出力バッファ１８は３つのレコードを格納できるものとする。
【０２７０】
図１６１はハッシュ済みリスト生成処理の経過の説明図である。同図においては、図３の入力バッファ１３からレコードバッファ１４へのレコードの入力と、レコードバッファ１４からハッシュ済みリスト用出力バッファ１８へのレコードの出力の経過が示されている。図８におけると同様に、１つのレコードが入力される時、すでに同じハッシュ値を持つレコードがハッシュ表のそのハッシュ値の領域からポイントされている時には、新しく入力されるレコードがハッシュ表からポイントされ、すでに入力されているレコードはリンク管理表によって管理される。
【０２７１】
図１６２は、図１６１の処理結果としてのハッシュ済みリストである。図１６１と比較することにより、ランとしてはブロック番号０〜２のランと、ブロック番号３〜５の２本のランが得られることが分かる。
【０２７２】
次に補助情報リストとしては［ブロック番号、先頭レコードのハッシュ値、末尾レコードのハッシュ値］の形を用いるものとすると、次のような補助情報リストが得られる。この補助情報リストの形式はｉの値によっては変化しない。
【０２７３】
［０，０，０］［１，１，２］［２，２，２］［３，０，０］［４，０，１］
［５，１，１］
補助情報リストのソートによって、例えば次のようにソートされた補助情報リストが得られる。このソートの方式もｉの値によっては変化しないものとする。
【０２７４】
［０，０，０］［３，０，０］［４，０，１］［５，１，１］［１，１，２］
［２，２，２］
このソートされた補助情報リストをもとに、図１９のグループバイ関数処理が行われるが、まず図１８における最小ハッシュ値レコード取り出し装置３３による処理を図１６３に示す。ここではラン数分のハッシュ済みリスト用入力バッファは２個であり、２個のバッファにソートされた補助情報リスト３０の順番に従って入力されたレコードから最小ハッシュ値のレコードが１つずつ取り出され、最終的な結果は次のようになる。
【０２７５】
［２４］［１２］［１５］［４５］［４５］［１５］［２４］［１２］［２５］［１６］［４６］［１４］［２６］［５６］［１４］［１４］
この最小ハッシュ値レコード取り出し装置３３による処理結果を、ハッシュ値毎に分けると次のようになる。
【０２７６】
ハッシュ値０：［２４］［１２］［１５］［４５］［４５］［１５］［２４］
［１２］
ハッシュ値１：［２５］［１６］［４６］
ハッシュ値２：［１４］［２６］［５６］［１４］［１４］
このようにハッシュ値が等しいレコードに対しては、図１８のソート装置３４によるソート処理が行われ、その結果がグループバイ関数演算処理装置３５に送られ、数え上げが実行される。このソートでは、前述した辞書式順序を用いることにする。図１９では、ハッシュ値０のレコードが取り出されなくなった時点でハッシュ値０のレコードのソートが行われ、ハッシュ値１のレコードが取り出されなくなった時点でハッシュ値１のレコードのソートが行われる。このような動作が最後まで繰り返され、出力されるレコードは［キー値，個数］の形式で表される。キー値はここでは２つのアイテム番号からなる。
【０２７７】
まずハッシュ値（）のレコードのソートが行われ、
［１２］［１２］［１５］［１５］［２４］［２４］［４５］［４５］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１２，２］［１５，２］［２４，２］［４５，２］
が得られる。次にハッシュ値１のレコードのソートが行われ、
［１６］［２５］［４６］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１６，１］［２５，１］［４６，１］
が得られる。最後にハッシュ値２のレコードのソートが行われ、
［１４］［１４］［２６］［５６］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１４，３］［２６，１］［５６，１］
という結果が得られる。
【０２７８】
全体では、
［１２，２］［１５，２］［２４，２］［４５，２］［１６，１］［２５，１］［４６，１］［１４，３］［２６，１］［５６，１］
という結果が得れる。
【０２７９】
以上において、本発明におけるグループバイ処理方式と、このグループバイ処理方式を利用したデータ組み合わせ数え上げ方式について実施例を詳細に説明したが、本発明の実施例は以上の記述のみに限定されることはなく、特許請求の範囲の記載に適合する範囲で、様々な他の実施の形態を取ることができることは当然である。
【０２８０】
（付記１）  それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方式において、
アイテム１個ずつを対象とする時は、各トランザクションに含まれるアイテムを１個ずつ出力し、ｉ（≧２）個のアイテムの組み合わせを対象とする時は、該ｉ個のアイテムの組み合わせに含まれるアイテムの部分的組み合わせまたはアイテム１個ずつのうちで、前記出現回数が与えられた条件に適合するアイテムの部分的組み合わせまたはアイテム１個ずつに含まれるアイテムに対応した組み合わせ生成制約条件に適合するアイテムの組み合わせのみを生成して出力する組み合わせ生成手段と、
該組み合わせ生成手段が出力するアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションにおける出現回数をカウントする出現回数カウント手段と、
該出現回数カウント手段が出力するアイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで出現回数が与えられた条件に適合するものを選択する組み合わせ選択手段と、
該組み合わせ選択手段の選択結果に対応した前記生成制約条件を前記組み合わせ生成手段に与える制約条件生成手段とを備えることを特徴とする相関のあるデータ組み合わせの数え上げ方式。
【０２８１】
（付記２）  前記制約条件生成手段が、前記組み合わせ選択手段の選択結果としてのアイテム１個ずつ、または２個以上のアイテムの組み合わせあるいは部分的組み合わせに含まれるアイテムに対応したビット位置に“１”を立てたビットマップを、前記組み合わせ生成制約条件として生成し、
前記組み合わせ生成手段がｉ（≧２）個のアイテムの組み合わせの生成にあたって、該ビットマップ上で“１”が立っているビット位置に対応するアイテムの組み合わせのみを生成することを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８２】
（付記３）  前記制約条件生成手段が、前記ビットマップにおいて前記組み合わせ選択手段の選択結果としてのアイテム１個ずつまたはアイテムの組み合わせに含まれるアイテムの番号に対するハッシュ関数の値に対応したビット位置に“１”を立てることを特徴とする付記２記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８３】
（付記４）  前記組み合わせ生成手段が、前記トランザクションに含まれるアイテム以外に、アイテムの階層構造においてトランザクションに含まれる他のアイテムの親のアイテムを含めて、アイテムの組み合わせまたはアイテム１個ずつを出力することを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８４】
（付記５）  前記組み合わせ生成手段が、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、該シーケンスにおける順序を維持した形式で、アイテムの組み合わせを生成することを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８５】
（付記６）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によって該記憶装置上に出力されたハッシュ済レコードのリストを読み込み、該リストのレコードをキー値に従ってソートし、該ソート済レコードのリストに対してグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段とを備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８６】
（付記７）  前記ハッシュ済レコード出力手段が、前記レコード格納手段から前記ハッシュ関数の値に対応して出力された複数のレコードを１つのブロックとして前記記憶装置に出力すると共に、
該ブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを格納する補助情報リスト格納手段を更に備えることを特徴とする付記６記載の相関のあるデータ組み合わせの数え上げ方式。
【０２８７】
（付記８）  前記グループ化と集計演算処理実行手段が、前記複数のレコードを１つのブロックとして前記ハッシュ済レコード出力手段によって出力され、ハッシュ関数値に対応したレコード列としてのハッシュ済リストと、前記補助情報リスト格納手段に格納されている補助情報のリストとを用いてグループ化と集計演算処理を実行することを特徴とする付記７記載の相関のあるデータ組み合わせ数え上げ方式。
【０２８８】
（付記９）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されるハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置上で必ずしも連続でない領域に出力するハッシュ済レコード出力手段とを備えることを特徴とする付記１記載の相関のあるデータ組み合わせ数え上げ方式。
【０２８９】
（付記１０）  前記ハッシュ済レコード出力手段が、前記レコード格納手段から前記ハッシュ関数値に対応して出力された複数のレコードを１つのブロックとして、前記記憶装置に出力すると共に、
該ブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを格納する補助情報リスト格納手段を更に備えることを特徴とする付記９記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９０】
（付記１１）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られ、前記記憶装置上で必ずしも連続でない領域に格納されたハッシュ関数値に対応したレコード列としてのハッシュ済リストと、該ハッシュ関数値に対応して格納された複数のレコードからなるブロック内のレコードを、ハッシュ関数値により検索可能とするための補助情報のリストとを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９１】
（付記１２）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置上で必ずしも連続でない領域に出力する手段であって、前記レコード格納手段から前記ハッシュ関数値に対応して出力された複数のレコードを１つのブロックとして、該１つのブロックが前記記憶装置上で連続した領域に格納される形式で出力するハッシュ済レコード出力手段と、
該ブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを格納する補助情報リスト格納手段と、
前記ハッシュ関数値に対応して前記ハッシュ済レコード出力手段によって出力されたハッシュ済レコード列と、前記補助情報リスト格納手段に格納されている補助情報のリストとを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段とを備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９２】
（付記１３）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段とを備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９３】
（付記１４）  前記ハッシュ済レコード出力手段が、前記ポインタによって指示されるレコードを前記記憶装置に出力するにあたり、前記１つのランに含まれるレコードを該記憶装置上の連続領域に出力すると共に、異なるランのレコードは必ずしも互いに連続でない領域に格納することを特徴とする付記１３記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９４】
（付記１５）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られるハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ハッシュ関数値に対応したレコードの格納にあたりハッシュ関数値を最小値から最大値まで連続的に変化させる間に格納されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９５】
（付記１６）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うめたに、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力するハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
該ハッシュ済レコード出力手段によって出力されたレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ラン情報格納手段に格納されているラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９６】
（付記１７）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力する手段であって、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードを該記憶装置上の連続領域に出力すると共に、異なるランのレコードは必ずしも互いに連続でない領域に格納するハッシュ済レコード出力手段と、
該ランのそれぞれに含まれるレコードの該記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
該ハッシュ済レコード出力手段によって出力されたレコードが該記憶装置上で格納されているハッシュ済レコード列の内容と、該ラン情報格納手段に格納されているラン情報とを用いてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９７】
（付記１８）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うためのハッシュ処理方式において、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置上で必ずしも連続でない領域に出力する手段であって、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域であって、相互に非連続である領域に格納される時、該２つのブロックの連結関係を示すデータを加えてレコードの出力を行うハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段とを備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９８】
（付記１９）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
前記ハッシュ処理の結果として得られるハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、該ハッシュ関数値に対応したレコードの該記憶装置への出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報と、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域に格納され、該２つの連続領域が相互に非連続となっているとき、該２つのブロックの連結関係を示すデータとに基づいてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０２９９】
（付記２０）  前記出現回数カウント手段が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウント処理としてのレコードのグループ化と集計演算処理を行うために、
該レコードを一時的に格納するレコード格納手段と、
該レコード格納手段に格納されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に格納するハッシュ値対応ポインタ格納手段と、
該ハッシュ値対応ポインタ格納手段に格納されているポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置上で必ずしも連続でない領域に出力する手段であって、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域であって、相互に非連続である領域に格納される時、該２つのブロックの連結関係を示すデータを加えてレコードの出力を行うハッシュ済レコード出力手段と、
該ハッシュ済レコード出力手段によるレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を格納するラン情報格納手段と、
前記ハッシュ済レコード出力手段によって出力され、ハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、前記ラン情報格納手段に格納されているラン情報と、前記２つのブロックの連結関係を示すデータとに基づいてグループ化と集計演算処理を実行するグループ化と集計演算処理実行手段を備えることを特徴とする付記１記載の相関のあるデータ組み合わせの数え上げ方式。
【０３００】
（付記２１）  それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方式において、
１個ずつのアイテムを対象とする時は各トランザクションに含まれるアイテムを１個ずつ出力し、ｉ（≧２）個のアイテムの組み合わせを対象とする時は、該ｉ個の組み合わせに含まれるアイテム１個ずつまたはアイテムの部分的組み合わせのうちで、前記出現回数が与えられた条件に適合するアイテムの部分的組み合わせまたはアイテム１個ずつに含まれるアイテムに対応した組み合わせ生成制約条件に適合するアイテムの組み合わせのみを生成して出力するアイテム組み合わせ生成機能と、
該出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能と、
該カウントされた出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせを選択する機能と、
該選択結果に対応した前記生成制約条件を前記アイテム組み合わせ生成機能に与える機能とを計算機に実行させるためのプログラムを格納した計算機読み出し可能記憶媒体。
【０３０１】
（付記２２）  前記出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウントの処理としてのレコードのグループ化と集計演算処理を行う機能であって、
該レコードを一時的に記憶する機能と、
該一時的に記憶されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に記憶する機能と、
該ポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力する機能と、
該記憶装置上に出力されたハッシュ済レコードのリストを読み込み、該リストのレコードをキー値に従ってソートし、該ソート済レコードリストに対してグループ化と集計演算処理を実行する機能とを計算機に実行させるためのプログラムを格納した付記２１記載の計算機読出し可能記憶媒体。
【０３０２】
（付記２３）  前記出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウントの処理としてのレコードのグループ化と集計演算処理を行う機能であって、
該レコードを一時的に記憶する機能と、
該一時的に記憶されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に記憶する機能と、
該ポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置上で必ずしも連続でない領域に出力する機能であって、前記ハッシュ関数値に対応して出力されるべき複数のレコードを１つのブロックとして、該１つのブロックが前記記憶装置上で連続した領域に格納される形式で出力する機能と、
該ブロックのレコードに対するハッシュ関数値による検索を可能とするための補助情報のリストを記憶する機能と、
前記ハッシュ関数値に対応して前記記憶装置に出力されたハッシュ済レコード列と、前記補助情報のリストとを用いてグループ化と集計演算処理を実行する機能とを計算機に実行させるためのプログラムを格納した付記２１記載の計算機読出し可能記憶媒体。
【０３０３】
（付記２４）  前記出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウントの処理としてのレコードのグループ化と集計演算処理を行う機能であって、
該レコードを一時的に記憶する機能と、
該一時的に記憶されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に記憶する機能と、
該ポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力する機能と、
該記憶装置へのレコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を記憶する機能と、
該出力されたレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、前記ラン情報とを用いてグループ化と集計演算処理を実行する機能とを計算機に実行させるためのプログラムを格納した付記２１記載の計算機読出し可能記憶媒体。
【０３０４】
（付記２５）  前記出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウントの処理としてのレコードのグループ化と集計演算処理を行う機能であって、
該レコードを一時的に記憶する機能と、
該一時的に記憶されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に記憶する機能と、
該ポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて前記記憶装置に出力する機能であって、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードを該記憶装置上の連続領域に出力すると共に、異なるランのレコードは必ずしも互いに連続でない領域に出力する機能と、
該ランのそれぞれに含まれるレコードの該記憶装置上の格納アドレスを示すラン情報を記憶する機能と、
該出力されたレコードが該記憶装置上で格納されているハッシュ済レコード列の内容と、該ラン情報とを用いてグループ化と集計演算処理を実行する機能とを計算機に実行させるためのプログラムを格納した付記２１記載の計算機読出し格納記憶媒体。
【０３０５】
（付記２６）  前記出力されたアイテム１個ずつまたは２個以上のアイテムの組み合わせの全てのトランザクションでの出現回数をカウントする機能が、記憶装置に格納され、それぞれアイテム１個ずつまたは２個以上のアイテムの組み合わせを示すレコードの集合を、各レコードのキーの値に対応するハッシュ関数値によって参照可能な形式に変換するハッシュ処理の結果に基づいて、前記出現回数カウントの処理としてのレコードのグループ化と集計演算処理を行う機能であって、
該レコードを一時的に記憶する機能と、
該一時的に記憶されたレコードの格納位置を示すポインタを、該レコードのキー値から計算されたハッシュ関数値に対応する位置に記憶する機能と、
該ポインタによって指示されるレコードを、該ポインタの格納位置に対応するハッシュ関数値に対応させて、前記記憶装置上で必ずしも連続でない領域に出力する機能であって、それぞれ複数のレコードからなる２つの連続すべきブロックがそれぞれ独立の連続領域であって、相互に非連続である領域に格納される時、該２つのブロックの連結関係を示すデータを加えてレコードの出力を行う機能と、
該レコードの出力にあたり、ハッシュ関数値を最小値から最大値まで連続的に変化させる間に出力されるランのそれぞれに含まれるレコードの前記記憶装置上の格納アドレスを示すラン情報を記憶する機能と、
前記ハッシュ関数値に対応したレコードが前記記憶装置上で格納されているハッシュ済レコード列の内容と、前記ラン情報と、前記２つのブロックの連結関係を示すデータとに基づいて、グループ化と集計演算処理を実行する機能とを計算機に実行させるためのプログラムを格納した付記２１記載の計算機読出し可能記憶媒体。
【０３０６】
（付記２７）  それぞれ１個以上のアイテムをデータとして含む多数のトランザクションから、アイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方法において、
各トランザクションに含まれるアイテムを１個ずつカウントして、該１個ずつのアイテムの全トランザクションでの出現回数をカウントし、
該カウント回数が与えられた条件に適合するアイテムを選択して、該アイテムと該カウント回数との組を数え上げ結果として出力し、
該選択されたアイテムに対応したビット位置に“１”をセットしたビットマップを作成し、
組み合わせ内のアイテムの個数を示すｉの値をｉ＝２とし、
該ビットマップに“１”が立っている位置に対応するアイテムを用いて、各トランザクションに含まれるｉ個のアイテムの組み合わせを生成し、
該生成されたアイテムの組み合わせの全トランザクションでの出現回数をカウントし、
該カウント回数が与えられた条件に適合するアイテムの組み合わせを選択して、該アイテムの組み合わせと該カウント回数との組を数え上げ結果として出力し、
該選択されたアイテムの組み合わせあるいは部分的組み合わせ、または該組み合わせに含まれるアイテム１個ずつに対応したビット位置に“１”をセットしたビットマップを作成し、
ｉの値をインクリメントして前記ｉ個のアイテムの組み合わせの生成以降の処理を繰り返すことを特徴とする相関のあるデータ組み合わせの数え上げ方法。
【０３０７】
（付記２８）  前記ビットマップの作成において、
前記１個ずつのアイテムのうちで、前記選択されたアイテムに対応したビット位置への“１”のセットと、
前記ｉ個のアイテムの組み合わせのうちで、前記選択されたアイテムの組み合わせあるいは部分的組み合わせ、または該組み合わせに含まれるアイテム１個ずつに対応したビット位置への“１”のセットとにあたり、
アイテム１個ずつ、またはアイテムの組み合わせあるいは部分的組み合わせに含まれるアイテムの番号に対するハッシュ関数の値に対応したビット位置に“１”をセットすることを特徴とする付記２７記載の相関のあるデータ組み合わせの数え上げ方法。
【０３０８】
（付記２９）  前記データ組み合わせの数え上げ方法において、
前記トランザクションに含まれるアイテム以外に、アイテムの階層構造においてトランザクションに含まれる他のアイテムの親のアイテムを含めて、前記与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めることを特徴とする付記２７記載の相関のあるデータ組み合わせの数え上げ方法。
【０３０９】
（付記３０）  前記データ組み合わせの数え上げ方法において、
前記多数のトランザクションのうちで、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、前記与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めることを特徴とする付記２７記載の相関のあるデータ組み合わせの数え上げ方法。
【０３１０】
【発明の効果】
以上詳細に説明したように、本発明のグループバイ処理においては、二次記憶装置に対するアクセスをできるだけ連続的にするために、比較的大きなブロック単位でのデータの逐次読み出しと逐次書き込みを行うことによってハッシュ処理を高速化し、そのハッシュ処理の結果を用いたグループバイ処理を実行することにより、全体としての高速化が可能となる。次に、本発明のデータ組み合わせ数え上げ方式においては、不必要なアイテムの組み合わせ候補のプルーニングのためにメモリ使用量を小さくできるビットマップを用いることにより、利用可能なメモリ量が小さい場合にもプルーニングが効率よく行え、更にアイテムセットを数え上げるグループバイ処理を高速化することによって、組み合わせの数え上げを効率的に実行することが可能になる。本発明のデータ組み合わせ数え上げ方式を、データベースのマイニング手法としての相関ルールの生成処理に応用することによって、データベースマイニングの効率化に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明におけるグループバイ処理方式の原理構成を示すブロック図である。
【図２】本発明における相関のあるデータ組み合わせの数え上げ方式の原理構成を示すブロック図である。
【図３】グループバイ処理方式の第１の実施例におけるハッシュ処理を説明する図である。
【図４】グループバイ処理方式の第１の実施例におけるハッシュ処理の全体フローチャートである。
【図５】図４における出力処理の詳細フローチャートである。
【図６】図４における終了処理の詳細フローチャートである。
【図７】図５、図６における出力バッファ出力処理の詳細フローチャートである。
【図８】グループバイ処理方式の第１の実施例におけるハッシュ処理の経過を示す図である。
【図９】グループバイ処理方式の第１の実施例におけるハッシュ処理の結果として得られるハッシュ済リストを示す図である。
【図１０】グループバイ処理方式の第２の実施例におけるハッシュ処理の説明図である。
【図１１】グループバイ処理方式の第２の実施例における出力バッファ出力処理の詳細フローチャートである。
【図１２】補助情報リストソート処理（第１の方法）のフローチャートである。
【図１３】補助情報リストソート処理（第２の方法）のフローチャートである。
【図１４】補助情報リストソート処理（第３の方法）のフローチャートである。
【図１５】補助情報リストソート処理（第４の方法）のフローチャートである。
【図１６】補助情報リストソート処理（第５の方法）のフローチャートである。
【図１７】補助情報リストソート処理（第６の方法）のフローチャートである。
【図１８】グループバイ処理方式の第１および第２の実施例におけるグループバイ関数処理の全体説明図である。
【図１９】グループバイ処理方式の第１および第２の実施例におけるグループバイ関数処理の全体フローチャートである。
【図２０】図１９におけるグループバイ関数演算処理の詳細フローチャートである。
【図２１】グループバイ処理方式の第３の実施例におけるハッシュ処理の説明図である。
【図２２】グループバイ処理方式の第３の実施例における出力バッファ出力処理の詳細フローチャートである。
【図２３】グループバイ処理方式の第３の実施例におけるグループバイ関数処理の全体説明図である。
【図２４】グループバイ処理方式の第３の実施例におけるグループバイ関数処理の全体フローチャートである。
【図２５】グループバイ処理方式の第４の実施例におけるハッシュ処理の説明図である。
【図２６】グループバイ処理方式の第４の実施例のハッシュ処理における出力処理の詳細フローチャートである。
【図２７】グループバイ処理方式の第４の実施例のハッシュ処理における終了処理の詳細フローチャートである。
【図２８】図２６、図２７における出力バッファ出力処理の詳細フローチャートである。
【図２９】グループバイ処理方式の第４の実施例においてハッシュ済レコード出力領域が非連続である場合の出力処理の詳細フローチャートである。
【図３０】グループバイ処理方式の第４の実施例においてハッシュ済レコード出力領域が非連続である場合の出力結果の例を示す図である。
【図３１】グループバイ処理方式の第４の実施例におけるグループバイ関数処理の全体説明図である。
【図３２】グループバイ処理方式の第４の実施例におけるグループバイ関数処理の全体フローチャートである。
【図３３】グループバイ処理方式の第５の実施例におけるハッシュ処理の説明図である。
【図３４】グループバイ処理方式の第５の実施例のハッシュ処理における出力バッファ出力処理の詳細フローチャートである。
【図３５】グループバイ処理方式の第５の実施例におけるグループバイ関数処理の全体説明図である。
【図３６】グループバイ処理方式の第５の実施例におけるグループバイ関数処理の全体フローチャートである。
【図３７】具体的データを用いた本発明におけるグループバイ処理方式の実施例の全体説明図である。
【図３８】図３７におけるハッシュ処理装置の構成を示すブロック図である。
【図３９】具体例を用いた本発明におけるグループバイ処理方式の全体処理フローチャートである。
【図４０】具体的なデータを用いたハッシュ処理のフローチャートである。
【図４１】具体的なデータを用いたグループバイ処理の全体フローチャートである。
【図４２】図４１におけるカウント処理の詳細フローチャートである。
【図４３】具体的なデータを用いたハッシュ処理の経過の説明図である。
【図４４】具体的なデータを用いたグループバイ処理方式の第１の実施例に対応する最小ハッシュ値レコード取り出しの経過の説明図である。
【図４５】具体的なデータを用いたグループバイ処理方式の第４の実施例に対応する最小ハッシュ値レコード取り出しの経過の説明図である。
【図４６】本発明のデータ組み合わせ数え上げ方式の実施例の構成を説明する図である。
【図４７】本発明のデータ組み合わせ数え上げ方式の全体処理フローチャートである。
【図４８】ラージアイテムセット生成処理のフローチャートである。
【図４９】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）  とその数え上げＧ（１）  とを説明する図（その１）である。
【図５０】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）  とその数え上げＧ（１）  とを説明する図（その２）である。
【図５１】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）  とその数え上げＧ（１）  とを説明する図（その３）である。
【図５２】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）  とその数え上げＧ（１）  とを説明する図（その４）である。
【図５３】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その１）である。
【図５４】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その２）である。
【図５５】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その３）である。
【図５６】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その４）である。
【図５７】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その５）である。
【図５８】長さ１のラージアイテムセットＬ（１）  の選択を説明する図（その６）である。
【図５９】長さ２のアイテムの組み合わせ候補数え上げＧ（２）  までの処理を説明する図（その１）である。
【図６０】長さ２のアイテムの組み合わせ候補数え上げＧ（２）  までの処理を説明する図（その２）である。
【図６１】長さ２のアイテムの組み合わせ候補数え上げＧ（２）  までの処理を説明する図（その３）である。
【図６２】長さ２のアイテムの組み合わせ候補数え上げＧ（２）  までの処理を説明する図（その４）である。
【図６３】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その１）である。
【図６４】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その２）である。
【図６５】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その３）である。
【図６６】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その４）である。
【図６７】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その５）である。
【図６８】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その６）である。
【図６９】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その７）である。
【図７０】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その８）である。
【図７１】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その９）である。
【図７２】長さ２のラージアイテムセットＬ（２）  の選択を説明する図（その１０）である。
【図７３】長さ３のアイテムの組み合わせ候補数え上げＧ（３）  までの処理を説明する図（その１）である。
【図７４】長さ３のアイテムの組み合わせ候補数え上げＧ（３）  までの処理を説明する図（その２）である。
【図７５】長さ３のアイテムの組み合わせ候補数え上げＧ（３）  までの処理を説明する図（その３）である。
【図７６】長さ３のアイテムの組み合わせ候補数え上げＧ（３）  までの処理を説明する図（その４）である。
【図７７】長さ３のラージアイテムセットＬ（３）  の選択を説明する図（その１）である。
【図７８】長さ３のラージアイテムセットＬ（３）  の選択を説明する図（その２）である。
【図７９】長さ３のラージアイテムセットＬ（３）  の選択を説明する図（その３）である。
【図８０】階層相関分析に用いられるデータの階層構造の具体例を示す図である。
【図８１】階層相関分析におけるＧ（１）  までの処理を説明する図（その１）である。
【図８２】階層相関分析におけるＧ（１）  までの処理を説明する図（その２）である。
【図８３】階層相関分析におけるＧ（１）  までの処理を説明する図（その３）である。
【図８４】階層相関分析におけるＧ（１）  までの処理を説明する図（その４）である。
【図８５】階層相関分析におけるＬ（１）  の選択を説明する図（その１）である。
【図８６】階層相関分析におけるＬ（１）  の選択を説明する図（その２）である。
【図８７】階層相関分析におけるＬ（１）  の選択を説明する図（その３）である。
【図８８】階層相関分析におけるＬ（１）  の選択を説明する図（その４）である。
【図８９】階層相関分析におけるＬ（１）  の選択を説明する図（その５）である。
【図９０】階層相関分析におけるＬ（１）  の選択を説明する図（その６）である。
【図９１】階層相関分析におけるＬ（１）  の選択を説明する図（その７）である。
【図９２】階層相関分析におけるＬ（１）  の選択を説明する図（その８）である。
【図９３】階層相関分析におけるＬ（１）  の選択を説明する図（その９）である。
【図９４】階層相関分析におけるＬ（１）  の選択を説明する図（その１０）である。
【図９５】階層相関分析におけるＧ（２）  までの処理を説明する図（その１）である。
【図９６】階層相関分析におけるＧ（２）  までの処理を説明する図（その２）である。
【図９７】階層相関分析におけるＧ（２）  までの処理を説明する図（その３）である。
【図９８】階層相関分析におけるＧ（２）  までの処理を説明する図（その４）である。
【図９９】階層相関分析におけるＬ（２）  の選択を説明する図（その１）である。
【図１００】階層相関分析におけるＬ（２）  の選択を説明する図（その２）である。
【図１０１】階層相関分析におけるＬ（２）  の選択を説明する図（その３）である。
【図１０２】階層相関分析におけるＬ（２）  の選択を説明する図（その４）である。
【図１０３】階層相関分析におけるＬ（２）  の選択を説明する図（その５）である。
【図１０４】階層相関分析におけるＬ（２）  の選択を説明する図（その６）である。
【図１０５】階層相関分析におけるＬ（２）  の選択を説明する図（その７）である。
【図１０６】階層相関分析におけるＬ（２）  の選択を説明する図（その８）である。
【図１０７】階層相関分析におけるＬ（２）  の選択を説明する図（その９）である。
【図１０８】階層相関分析におけるＬ（２）  の選択を説明する図（その１０）である。
【図１０９】階層相関分析におけるＬ（２）  の選択を説明する図（その１１）である。
【図１１０】階層相関分析におけるＧ（３）  までの処理を説明する図（その１）である。
【図１１１】階層相関分析におけるＧ（３）  までの処理を説明する図（その２）である。
【図１１２】階層相関分析におけるＧ（３）  までの処理を説明する図（その３）である。
【図１１３】階層相関分析におけるＧ（３）  までの処理を説明する図（その４）である。
【図１１４】階層相関分析におけるＬ（３）  の選択を説明する図（その１）である。
【図１１５】階層相関分析におけるＬ（３）  の選択を説明する図（その２）である。
【図１１６】階層相関分析におけるＬ（３）  の選択を説明する図（その３）である。
【図１１７】階層相関分析におけるＬ（３）  の選択を説明する図（その４）である。
【図１１８】階層相関分析におけるＬ（３）  の選択を説明する図（その５）である。
【図１１９】階層相関分析におけるＬ（３）  の選択を説明する図（その６）である。
【図１２０】階層相関分析におけるＧ（４）  までの処理を説明する図（その１）である。
【図１２１】階層相関分析におけるＧ（４）  までの処理を説明する図（その２）である。
【図１２２】階層相関分析におけるＧ（４）  までの処理を説明する図（その３）である。
【図１２３】階層相関分析におけるＧ（４）  までの処理を説明する図（その４）である。
【図１２４】時系列分析におけるシーケンスリストの例を説明する図である。
【図１２５】時系列分析におけるＧ（１）  までの処理を説明する図（その１）である。
【図１２６】時系列分析におけるＧ（１）  までの処理を説明する図（その２）である。
【図１２７】時系列分析におけるＧ（１）  までの処理を説明する図（その３）である。
【図１２８】時系列分析におけるＧ（１）  までの処理を説明する図（その４）である。
【図１２９】時系列分析におけるＧ（１）  までの処理を説明する図（その５）である。
【図１３０】時系列分析におけるＬ（１）  の選択を説明する図（その１）である。
【図１３１】時系列分析におけるＬ（１）  の選択を説明する図（その２）である。
【図１３２】時系列分析におけるＬ（１）  の選択を説明する図（その３）である。
【図１３３】時系列分析におけるＬ（１）  の選択を説明する図（その４）である。
【図１３４】時系列分析におけるＬ（１）  の選択を説明する図（その５）である。
【図１３５】時系列分析におけるＬ（１）  の選択を説明する図（その６）である。
【図１３６】時系列分析におけるＬ（１）  の選択を説明する図（その７）である。
【図１３７】時系列分析におけるＬ（１）  の選択を説明する図（その８）である。
【図１３８】時系列分析におけるＧ（２）  までの処理を説明する図（その１）である。
【図１３９】時系列分析におけるＧ（２）  までの処理を説明する図（その２）である。
【図１４０】時系列分析におけるＧ（２）  までの処理を説明する図（その３）である。
【図１４１】時系列分析におけるＧ（２）  までの処理を説明する図（その４）である。
【図１４２】時系列分析におけるＧ（２）  までの処理を説明する図（その５）である。
【図１４３】時系列分析におけるＬ（２）  の選択を説明する図（その１）である。
【図１４４】時系列分析におけるＬ（２）  の選択を説明する図（その２）である。
【図１４５】時系列分析におけるＬ（２）  の選択を説明する図（その３）である。
【図１４６】時系列分析におけるＬ（２）  の選択を説明する図（その４）である。
【図１４７】時系列分析におけるＬ（２）  の選択を説明する図（その５）である。
【図１４８】時系列分析におけるＬ（２）  の選択を説明する図（その６）である。
【図１４９】時系列分析におけるＬ（２）  の選択を説明する図（その７）である。
【図１５０】時系列分析におけるＬ（２）  の選択を説明する図（その８）である。
【図１５１】時系列分析におけるＬ（２）  の選択を説明する図（その９）である。
【図１５２】時系列分析におけるＬ（２）  の選択を説明する図（その１０）である。
【図１５３】時系列分析におけるＬ（２）  の選択を説明する図（その１１）である。
【図１５４】時系列分析におけるＧ（３）  までの処理を説明する図（その１）である。
【図１５５】時系列分析におけるＧ（３）  までの処理を説明する図（その２）である。
【図１５６】時系列分析におけるＧ（３）  までの処理を説明する図（その３）である。
【図１５７】時系列分析におけるＧ（３）  までの処理を説明する図（その４）である。
【図１５８】時系列分析におけるＧ（３）  までの処理を説明する図（その５）である。
【図１５９】時系列分析におけるＬ（３）  の選択を説明する図である。
【図１６０】基本相関分析における本発明の処理の流れを説明する図である。
【図１６１】アイテム組み合わせ数え上げ処理におけるハッシュ済みリスト生成処理の経過を説明する図である。
【図１６２】図１６１の処理結果としてのハッシュ済みリストを示す図である。
【図１６３】図１６２のハッシュ済みリストに対する最小ハッシュ値レコード取り出し処理の経過を示す図である。
【図１６４】ソート処理に基づくグループバイ処理の従来例のフローチャートである。
【図１６５】図１６４のフローチャートを用いた具体的な処理経過の説明図である。
【図１６６】ハッシュ処理に基づくグループバイ処理の従来例のフローチャートである。
【図１６７】図１６６のフローチャートを用いた具体的な処理経過の説明図である。
【図１６８】ＳＥＴＭアルゴリズムにおける具体的な処理の流れを説明する図である。
【図１６９】ＳＥＴＭアルゴリズムの処理における各機能ブロック処理内容を示す図である。
【図１７０】アプリオリ・アルゴリズムにおける具体的な処理の流れを説明する図である。
【図１７１】アプリオリ・アルゴリズムの処理における各機能ブロックの内容を説明する図である。
【符号の説明】
１    組み合わせ生成部
２    出現回数数え上げ部
３    組み合わせ選択部
４    ビットマップ生成部
５，６    ビットマップ
１１    ハッシュ対象リスト
１２    処理装置
１３    入力バッファ
１４    レコードバッファ
１５    ハッシュ表
１６    リンク管理表
１７    出力ハッシュ値メモリ
１８    ハッシュ済リスト用出力バッファ
１９    補助情報リスト用出力バッファ
２０    出力ブロック数カウンタ
２１    ハッシュ済リスト
２２    補助情報リスト
２３    ラン情報メモリ
２４    ラン番号メモリ
３０    ソートされた補助情報リスト
３１    ソートされた補助情報リスト用入力バッファ
３２ａ〜３２ｎ    ハッシュ済リスト用入力バッファ
３３    最小ハッシュ値レコード取り出し装置
３４    ハッシュ値が等しいレコード群のソート装置
３５    グループバイ関数演算処理装置
３６ａ〜３６ｎ    ハッシュ済レコード用入力バッファ
３８    ハッシュ済レコード用出力バッファ
４０，４１    ハッシュ済レコード出力領域
【図１】
0003601719.tif 000003
【図２】
0003601719.tif 000004
【図３】
0003601719.tif 000005
【図４】
0003601719.tif 000006
【図５】
0003601719.tif 000007
【図６】
0003601719.tif 000008
【図７】
0003601719.tif 000009
【図８】
0003601719.tif 000010
【図９】
0003601719.tif 000011
【図１０】
0003601719.tif 000012
【図１１】
0003601719.tif 000013
【図１２】
0003601719.tif 000014
【図１３】
0003601719.tif 000015
【図１４】
0003601719.tif 000016
【図１５】
0003601719.tif 000017
【図１６】
0003601719.tif 000018
【図１７】
0003601719.tif 000019
【図１８】
0003601719.tif 000020
【図１９】
0003601719.tif 000021
【図２０】
0003601719.tif 000022
【図２１】
0003601719.tif 000023
【図２２】
0003601719.tif 000024
【図２３】
0003601719.tif 000025
【図２４】
0003601719.tif 000026
【図２５】
0003601719.tif 000027
【図２６】
0003601719.tif 000028
【図２７】
0003601719.tif 000029
【図２８】
0003601719.tif 000030
【図２９】
0003601719.tif 000031
【図３０】
0003601719.tif 000032
【図３１】
0003601719.tif 000033
【図３２】
0003601719.tif 000034
【図３３】
0003601719.tif 000035
【図３４】
0003601719.tif 000036
【図３５】
0003601719.tif 000037
【図３６】
0003601719.tif 000038
【図３７】
0003601719.tif 000039
【図３８】
0003601719.tif 000040
【図３９】
0003601719.tif 000041
【図４０】
0003601719.tif 000042
【図４１】
0003601719.tif 000043
【図４２】
0003601719.tif 000044
【図４３】
0003601719.tif 000045
【図４４】
0003601719.tif 000046
【図４５】
0003601719.tif 000047
【図４６】
0003601719.tif 000048
【図４７】
0003601719.tif 000049
【図４８】
0003601719.tif 000050
【図４９】
0003601719.tif 000051
【図５０】
0003601719.tif 000052
【図５１】
0003601719.tif 000053
【図５２】
0003601719.tif 000054
【図５３】
0003601719.tif 000055
【図５４】
0003601719.tif 000056
【図５５】
0003601719.tif 000057
【図５６】
0003601719.tif 000058
【図５７】
0003601719.tif 000059
【図５８】
0003601719.tif 000060
【図５９】
0003601719.tif 000061
【図６０】
0003601719.tif 000062
【図６１】
0003601719.tif 000063
【図６２】
0003601719.tif 000064
【図６３】
0003601719.tif 000065
【図６４】
0003601719.tif 000066
【図６５】
0003601719.tif 000067
【図６６】
0003601719.tif 000068
【図６７】
0003601719.tif 000069
【図６８】
0003601719.tif 000070
【図６９】
0003601719.tif 000071
【図７０】
0003601719.tif 000072
【図７１】
0003601719.tif 000073
【図７２】
0003601719.tif 000074
【図７３】
0003601719.tif 000075
【図７４】
0003601719.tif 000076
【図７５】
0003601719.tif 000077
【図７６】
0003601719.tif 000078
【図７７】
0003601719.tif 000079
【図７８】
0003601719.tif 000080
【図７９】
0003601719.tif 000081
【図８０】
0003601719.tif 000082
【図８１】
0003601719.tif 000083
【図８２】
0003601719.tif 000084
【図８３】
0003601719.tif 000085
【図８４】
0003601719.tif 000086
【図８５】
0003601719.tif 000087
【図８６】
0003601719.tif 000088
【図８７】
0003601719.tif 000089
【図８８】
0003601719.tif 000090
【図８９】
0003601719.tif 000091
【図９０】
0003601719.tif 000092
【図９１】
0003601719.tif 000093
【図９２】
0003601719.tif 000094
【図９３】
0003601719.tif 000095
【図９４】
0003601719.tif 000096
【図９５】
0003601719.tif 000097
【図９６】
0003601719.tif 000098
【図９７】
0003601719.tif 000099
【図９８】
0003601719.tif 000100
【図９９】
0003601719.tif 000101
【図１００】
0003601719.tif 000102
【図１０１】
0003601719.tif 000103
【図１０２】
0003601719.tif 000104
【図１０３】
0003601719.tif 000105
【図１０４】
0003601719.tif 000106
【図１０５】
0003601719.tif 000107
【図１０６】
0003601719.tif 000108
【図１０７】
0003601719.tif 000109
【図１０８】
0003601719.tif 000110
【図１０９】
0003601719.tif 000111
【図１１０】
0003601719.tif 000112
【図１１１】
0003601719.tif 000113
【図１１２】
0003601719.tif 000114
【図１１３】
0003601719.tif 000115
【図１１４】
0003601719.tif 000116
【図１１５】
0003601719.tif 000117
【図１１６】
0003601719.tif 000118
【図１１７】
0003601719.tif 000119
【図１１８】
0003601719.tif 000120
【図１１９】
0003601719.tif 000121
【図１２０】
0003601719.tif 000122
【図１２１】
0003601719.tif 000123
【図１２２】
0003601719.tif 000124
【図１２３】
0003601719.tif 000125
【図１２４】
0003601719.tif 000126
【図１２５】
0003601719.tif 000127
【図１２６】
0003601719.tif 000128
【図１２７】
0003601719.tif 000129
【図１２８】
0003601719.tif 000130
【図１２９】
0003601719.tif 000131
【図１３０】
0003601719.tif 000132
【図１３１】
0003601719.tif 000133
【図１３２】
0003601719.tif 000134
【図１３３】
0003601719.tif 000135
【図１３４】
0003601719.tif 000136
【図１３５】
0003601719.tif 000137
【図１３６】
0003601719.tif 000138
【図１３７】
0003601719.tif 000139
【図１３８】
0003601719.tif 000140
【図１３９】
0003601719.tif 000141
【図１４０】
0003601719.tif 000142
【図１４１】
0003601719.tif 000143
【図１４２】
0003601719.tif 000144
【図１４３】
0003601719.tif 000145
【図１４４】
0003601719.tif 000146
【図１４５】
0003601719.tif 000147
【図１４６】
0003601719.tif 000148
【図１４７】
0003601719.tif 000149
【図１４８】
0003601719.tif 000150
【図１４９】
0003601719.tif 000151
【図１５０】
0003601719.tif 000152
【図１５１】
0003601719.tif 000153
【図１５２】
0003601719.tif 000154
【図１５３】
0003601719.tif 000155
【図１５４】
0003601719.tif 000156
【図１５５】
0003601719.tif 000157
【図１５６】
0003601719.tif 000158
【図１５７】
0003601719.tif 000159
【図１５８】
0003601719.tif 000160
【図１５９】
0003601719.tif 000161
【図１６０】
0003601719.tif 000162
【図１６１】
0003601719.tif 000163
【図１６２】
0003601719.tif 000164
【図１６３】
0003601719.tif 000165
【図１６４】
0003601719.tif 000166
【図１６５】
0003601719.tif 000167
【図１６６】
0003601719.tif 000168
【図１６７】
0003601719.tif 000169
【図１６８】
0003601719.tif 000170
【図１６９】
0003601719.tif 000171
【図１７０】
0003601719.tif 000172
【図１７１】
0003601719.tif 000173