WO2014168199A1

WO2014168199A1 - 論理演算方法および情報処理装置

Info

Publication number: WO2014168199A1
Application number: PCT/JP2014/060386
Authority: WO
Inventors: 古庄　晋二
Original assignee: 株式会社ターボデータラボラトリー
Priority date: 2013-04-12
Filing date: 2014-04-10
Publication date: 2014-10-16
Also published as: JPWO2014168199A1; US20160070776A1

Abstract

大規模データにおいて、複数の集合間の論理演算を効率的に行う。論理演算対象の各集合を、メモリに配置可能なサイズの、予め定めた共通の区分に分類し、区分毎にメモリ上で論理演算を行う。共通の区分は、各集合の全レコードを重複無く分類できるよう設定する。そして、区分毎の論理演算結果の直和を計算することにより、論理演算結果を得る。なお、共通の区分のサイズは、分類されたレコードがメモリに展開可能なように決定する。

Description

論理演算方法および情報処理装置

　本発明は、大規模データ（Ｂｉｇ　Ｄａｔａ）の論理演算技術に関する。

　ネットワーク、サーバ、ストレージなどのハードウェアの革新と、それらの運用技術の発展に伴い、近年、データ量が爆発的に増加している。このようなデータは、大規模データと呼ばれている。大規模データは、ディスク上には保持できるが、その大きさのため、メモリ上には全てを展開できない。このため、大規模データの論理演算、例えば、大規模データから生成した複数の集合間でＡＮＤ、ＯＲといった論理演算を行う場合、集合をメモリにロード可能なサイズに機械的に分割した部分集合を生成し、部分集合の全ての組み合わせで論理演算処理を繰り返す必要がある。これを高速化するものとして、並列処理のＭａｐＲｅｄｕｃｅ技術がある（例えば、非特許文献１参照）。

"MapReduce"、[online]、2013年3月20日更新、[2013年3月21日検索]、インターネット、<URL:http://en.wikipedia.org/wiki/MapReduce>

　しかしながら、たとえＭａｐＲｅｄｕｃｅ技術を適用して並列化したとしても、各集合について分割した単位毎に総当りで論理演算を行うため、全演算回数が増大する。このため、処理自体が、非効率であるだけでなく、メモリへの展開のためにディスクへのアクセス回数が増加し、処理性能が劣化する。

　本発明は、上記事情に鑑みてなされたもので、大規模データにおいて、複数の集合間の論理演算を効率的に行う技術を提供することを目的とする。

　本発明は、論理演算対象の各集合を、メモリに配置可能なサイズの、共通の区分に分類し、区分毎にメモリ上で論理演算を行う。共通の区分は、各集合の全レコードを重複無く分類できるよう設定する。そして、区分毎の論理演算結果の直和を計算することにより、論理演算結果を得る。なお、共通の区分のサイズは、分類されたレコードがメモリに展開可能なように決定する。

　具体的には、複数の集合間の論理演算方法であって、前記集合を構成する各レコードを、前記集合毎に、それぞれ予め定めた区分に分類し、同一の前記区分に属するレコード間で、前記集合間の論理演算を行い、演算結果を得、前記区分毎の前記演算結果の直和を計算し、前記区分は、前記複数の集合に属する全レコードを一意に類別可能なものであることを特徴とする集合間の論理演算方法を、提供する。

　また、複数の集合間の論理演算を行う情報処理装置であって、前記集合を構成する各レコードを、前記集合毎に、それぞれ予め定めた区分に分類する分類部と、同一の前記区分に属するレコード間で、前記集合間の論理演算を行い、演算結果を得る論理演算部と、前記区分毎の前記演算結果の直和を計算する直和部と、を備え、前記区分は、前記複数の集合に属する全レコードを一意に類別可能なものであることを特徴とする集合間の情報処理装置を提供する。

　また、コンピュータを、複数の集合に属する全レコードを一意に類別可能な区分に、当該レコードを前記集合毎に分類する分類手段、同一の前記区分に属するレコード間で、予め定めた前記集合間の論理演算を行い、演算結果を得る論理演算手段、前記区分毎の前記演算結果の直和を計算する直和手段、として機能させるためのプログラムを提供する。

　本発明によれば、大規模データにおいて、複数の集合間の論理演算を効率的に行うことができる。

本発明の実施形態の情報処理装置のブロック図である。本発明の実施形態の順序集合例を説明するための説明図である。従来の論理演算処理を説明するための説明図である。従来の論理演算処理を説明するための説明図である。本発明の実施形態の演算処理の概要を説明するための説明図である。本発明の実施形態の演算部の機能ブロック図である。（ａ）は、本発明の実施形態の順序集合例を、（ｂ）は、本発明の実施形態の区分（バスケット）を、（ｃ）は、区分後の順序集合例を、それぞれ説明するための説明図である。本発明の実施形態の順序集合間の論理演算処理のフローチャートである。本発明の実施形態の順序集合間の論理演算手法を説明するための説明図である。

　以下、本発明を適用する実施形態について説明する。以下、本発明の実施形態を説明するための全図において、同一機能を有するものは同一符号を付し、その繰り返しの説明は省略する。

　図１は、本実施形態の情報処理装置１００のブロック図である。本図に示すように、本実施形態の情報処理装置１００は、ＣＰＵ１１０と、メモリ１２０と、記憶装置１３０と、入力装置１４０と、出力装置１５０と、を備える。また、ネットワークインタフェース（ＮＷＩＦ）１７０および外部記憶装置１６０をさらに備えてもよい。

　記憶装置１３０には、重複したレコードを排除した、複数の順序集合１３１が格納される。各順序集合１３１は、それぞれ、１つのデータベース３００に保持されるレコードを、所定の項目で検索し、検索結果を抽出したものである。なお、データベース３００は、外部記憶装置１６０、並びに、情報処理装置１００にネットワーク１７１などを介して接続される他の情報処理装置１８０および他の外部記憶装置１９０などに保持される。

　図２に、データベース３００および各順序集合１３１の例を示す。ここでは、一例として、３つの項目を有するデータベース３００から抽出した３つの順序集合１３１Ａ、１３１Ｂ、１３１Ｃを示す。以後、順序集合は、各々区別する必要がない場合は、１３１と呼ぶ。

　データベース３００は、本図に示すように、年齢（Ａｇｅ）、地域（Ａｒｅａ）、保有ポイント（Ｐｏｉｎｔ）の３つの項目を備え、少なくとも１つの項目値を有する、１以上のレコードから構成される。なお、データベース３００の項目は、これらに限られず、様々な項目型を取りえる。また、項目値も、数値、文字列、全文など検索の対象にできるものであればいずれでもかまわない。

　データベース３００を構成する各レコードの左横に付与した番号は、各レコードに一意に付与されるレコード番号（ｒｅｃＮｏ．）である。レコード番号は、表形式データとして表されるデータベース３００において、各レコードが収容されている位置を表す情報である。このレコード番号は、例えば、データベース３００の作成時に付与される。各レコードには、レコード番号を指定することにより、アクセスできる。レコード番号は、記憶域を消費しない番地である。

　なお、データベース３００は、１の記憶領域に保持されていなくてもよい。複数の記憶装置に分散して格納されていてもよい。例えば、上記データベース３００の例では、レコード番号が０から３までのレコードが、情報処理装置１００の記憶装置１３０に、同４から６のレコードが、外部記憶装置１６０に、同７から１０のレコードが情報処理装置１８０の記憶装置に格納されていてもよい。あるいは、年齢のデータベースが記憶装置１３０に、地域のデータベースが外部記憶装置１６０に、保有ポイントのデータベースが外部記憶装置１９０に格納されていてもよい。

　順序集合１３１は、このデータベース３００の、所定の項目をキーに、所定の条件を満たすレコードを検索し、その結果得られたレコードを特定する情報の集合である。本実施形態では、レコードを特定する情報の集合として、レコード番号を用いる。

　一般に検索結果はインデックスの仕組み上、図２に示すように、項目値が昇順または降順となるよう得られることが多い。このため、順序集合１３１に格納されるレコード番号は、ランダムな並びとなる。

　通常の集合は順序のないものであるため、要素の並び順、例えば、（１，２，３）も（３，２，１）も区別されない。本実施形態の集合も集合演算の結果としては順序を要求されないものの、それが生成される時点では順序を持つことが多い。本実施形態では、その場合でも演算が行えることを示すため、ここでは、要素の順序、（１，２，３）と（３，２，１）を区別して話を進める。このため、本実施形態では、データベース３００から抽出した上記集合は、順序も含めた集合であるため、順序集合（Ｏｒｄｅｒｅｄ　Ｓｅｔ）と呼ぶ。

　例えば、図２に示すように、順序集合１３１Ａは、データベース３００から、項目「年齢（Ａｇｅ）」の値が１０以上であるレコードを抽出し、そのレコード番号を格納したものである。本図に示すように、順序集合１３１Ａは、それぞれ、３，２，５，８，４，１０というレコード番号を、この順に保持する。

　また、順序集合１３１Ｂは、データベース３００から、項目「地域（Ａｒｅａ）」の値がＳｏｕｔｈまたはＷｅｓｔであるレコードを抽出し、そのレコード番号を格納したものである。順序集合１３１Ｂは、それぞれ、１０，２，８，９というレコード番号を、この順に保持する。

　また、順序集合１３１Ｃは、データベース３００から、「保有ポイント（Ｐｏｉｎｔ）」の値が１０以上であるレコードを抽出し、そのレコード番号を格納したものである。順序集合１３１Ｃは、それぞれ、７，１，４，３，０，８というレコード番号を、この順に保持する。

　なお、レコード番号以外に、データベース３００の各レコードを一意に特定するＩＤなどを付与し、レコード番号の代わりに当該ＩＤを、順序集合１３１に格納するよう構成してもよい。ただし、ＩＤは、レコード番号と異なり、記憶域が必要となる。

　本実施形態のＣＰＵ１１０は、予め記憶装置１３０に格納されたプログラムに従って、各順序集合１３１間の、論理演算を実行する演算部２１０（後述する図６参照）としての機能を実現する。演算部２１０は、順序集合１３１を、メモリ１２０にロードして上記論理演算を行う。なお、演算部２１０が論理演算を実行する際必要なデータ、論理演算実行中に生成されるデータ等は、メモリ１２０および／または記憶装置１３０に格納される。

　本実施形態の、演算部２１０が実現する論理演算手法の説明に先立ち、従来の情報処理装置による論理演算手法（従来手法）を説明する。ここでは、図２に示す順序集合１３１Ａ、１３１Ｂ、１３１Ｃを用いて、順序集合１３１Ｂおよび順序集合１３１Ｃの論理和（ＯＲ）と順序集合１３１Ａとの論理積（ＡＮＤ）を演算する場合を例にあげて説明する。

　以後、各順序集合１３１Ａ、１３１Ｂ、１３１Ｃを、それぞれ、順序集合Ａ、Ｂ、Ｃと末尾の英字のみで記載する。また、上記論理演算式内では、英字のみで記載する。例えば、上記論理演算は、Ａ×（Ｂ＋Ｃ）と記載する。他の集合についても、同様とする。

　ここで、順序集合Ａ、Ｂ、Ｃを構成する各レコードのサイズを１、本実施形態の情報処理装置１００において、論理演算を行う際、順序集合Ａ、Ｂ、Ｃのレコードを展開（ロード）可能なメモリ１２０のサイズを、６（各順序集合Ａ、Ｂ、Ｃの各２レコード分）とする。

　従来手法によれば、図３に示すように、レコード値がランダムに並ぶ各順序集合Ａ、Ｂ、Ｃを、先頭から機械的に分割して２レコードずつの分割順序集合１３２を生成する。そして、各分割順序集合１３２間で、それぞれ、上記論理演算を実行し、その結果の和を生成し、重複値を排除する重複値排除演算を行い、演算結果として出力する。このとき、論理演算は、各分割順序集合１３２の全ての組み合わせについて行う必要がある。

　例えば、図３に示すように、順序集合Ａは、２レコードずつ、３つの分割順序集合１３２（Ａａ，Ａｂ，Ａｃ）に分割される。また、順序集合Ｂは、２つの分割順序集合１３２（Ｂａ，Ｂｂ）に分割される。また、順序集合Ｃは、３つの分割順序集合１３２（Ｃａ、Ｃｂ，Ｃｃ）に分割される。

　従来手法では、図４に示すように、分割順序集合Ａａについて、Ａａ×（Ｂａ＋Ｃａ）と、Ａａ×（Ｂａ＋Ｃｂ）と、Ａａ×（Ｂa＋Ｃｃ）と、Ａａ×（Ｂｂ＋Ｃａ）と、Ａａ×（Ｂｂ＋Ｃｂ）と、Ａａ×（Ｂｂ＋Ｃｃ）の６回演算を行う。分割順序集合Ａｂ、Ａｃについても、それぞれＡａをＡｂ、Ａｃに変えて、同様に、それぞれ６回演算を行う。

　従って、以下に示す１８回の演算が必要となる。
１）Ａａ×（Ｂａ＋Ｃａ）＝（３，２）×（１，２，７，１０）＝（２）
２）Ａａ×（Ｂａ＋Ｃｂ）＝（３，２）×（２，３，４，１０）＝（２，３）
３）Ａａ×（Ｂａ＋Ｃｃ）＝（３，２）×（０，２，８，１０）＝（２）
４）Ａａ×（Ｂｂ＋Ｃａ）＝（３，２）×（１，７，８，９）＝（）
５）Ａａ×（Ｂｂ＋Ｃｂ）＝（３，２）×（３，４，８，９）＝（３）
６）Ａａ×（Ｂｂ＋Ｃｃ）＝（３，２）×（０，８，８，９）＝（）
７）Ａｂ×（Ｂａ＋Ｃａ）＝（５，８）×（１，２，７，１０）＝（）
８）Ａｂ×（Ｂａ＋Ｃｂ）＝（５，８）×（２，３，４，１０）＝（２）
９）Ａｂ×（Ｂａ＋Ｃｃ）＝（５，８）×（０，２，８，１０）＝（８）
１０）Ａｂ×（Ｂｂ＋Ｃａ）＝（５，８）×（１，７，８，９）＝（８）
１１）Ａｂ×（Ｂｂ＋Ｃｂ）＝（５，８）×（３，４，８，９）＝（８）
１２）Ａｂ×（Ｂｂ＋Ｃｃ）＝（５，８）×（０，８，８，９）＝（８）
１３）Ａｃ×（Ｂａ＋Ｃａ）＝（４，６）×（１，２，７，１０）＝（）
１４）Ａｃ×（Ｂａ＋Ｃｂ）＝（４，６）×（２，３，４，１０）＝（４）
１５）Ａｃ×（Ｂａ＋Ｃｃ）＝（４，６）×（０，２，８，１０）＝（）
１６）Ａｃ×（Ｂｂ＋Ｃａ）＝（４，６）×（１，７，８，９）＝（）
１７）Ａｃ×（Ｂｂ＋Ｃｂ）＝（４，６）×（３，４，８，９）＝（４）
１８）Ａｃ×（Ｂｂ＋Ｃｃ）＝（４，６）×（０，８，８，９）＝（）

　また、従来演算では、同じ分割順序集合１３２が繰り返し演算に使用される。例えば、上記の例では、分割順序集合Ａａは６回、分割順序集合Ａｂは６回、分割順序集合Ａｃは６回、分割順序集合Ｂａは９回、分割順序集合Ｂｂは９回、分割順序集合Ｃａは６回、分割順序集合Ｃｂは６回、分割順序集合Ｃｃは６回、それぞれ、演算に使用される。

　一般化すると、全順序集合数をＫ（Ｋは１以上の整数）、ｋ番目の順序集合のレコード数をＮｋ（Ｎｋは１以上の整数）、１順序集合あたりの、ｋ番目の順序集合のメモリ上に割り当て可能なレコード数をＭｋ（Ｍｋは１以上の整数）とすると、以下の式（１）で表されるＰ回、論理演算を行う必要がある。

このため、記憶装置１３０からメモリ１２０への読み出し、メモリ１２０から記憶装置１３０への書き込みといった、メモリへのアクセス回数が膨大なものとなる。

　上記１８回の演算において、読み出し回数は、それぞれの分割順序集合１３２のレコード数と演算回数の積である。従って、上記の例では、６×１８で１０８回となる。また、書き込み回数は、演算結果のレコード数の和である。従って、上記の例では、順に、１，２，１，０，１，０，０，１，１，１，１，１，０，１，０，０，１，０回の合計で、１２回である。このように、従来手法では、演算だけで、合計１２０回の読み出し、書き込み処理が行われる。

　さらに、従来手法によれば、得られた結果の統合が、直和ではない。すなわち、１８回の演算結果を合計し、集合（２，２，３，２，３，２，８，８，８，８，４，４）を得、この集合から重複する値を消去する重複除去処理を行い、演算結果として（２，３，４，８）を得る。

　次に、本実施形態の演算部２１０による、処理を説明する。本実施形態の演算部２１０による処理の概要を図５に示す。本図に示すように、本実施形態では、まず、各順序集合１３１を構成する各レコードを、共通の区分に分類（類別）する。以後、各レコードを類別する区分を、バスケットと呼ぶ。そして、バスケット毎に、論理演算を実行し、最後に、全バスケットの論理演算結果の直和を計算する。

　本実施形態では、従来同様、メモリ１２０に配置可能なサイズに各順序集合１３１のレコードを分割する。しかしながら、このとき、機械的にレコード数で分割するのではなく、レコード値に応じて、振り分けられるレコードが重複しないよう予め定められた１以上のバスケットに分類、類別する。

　これを実現するため、本実施形態の演算部２１０は、図６に示すように、複数の順序集合１３１に属する全レコードを、各バスケット４００に振り分け、分類する分類部２１１と、バスケット４００毎に、論理演算を行う論理演算部２１２と、各バスケット４００の論理演算結果の直和を計算する直和部２１３と、を備える。なお、バスケット４００は、記憶装置１３０上に設けられる。

　各バスケット４００には、予め定めた条件（振分条件）を満たすレコードのみが振り分けられる。各バスケット４００の振分条件は、上述のように、全順序集合１３１の全レコードを一意に振り分け（類別）可能なように設定される。すなわち、全順序集合１３１の全レコードを網羅するとともに、重複無く分類できるよう、設定される。

　振分条件には、例えば、レコード値の範囲、レコード値を予め定めた２以上の整数で除算した際の余り（剰余）、等を用いることができる。

　振分条件、バスケット４００のサイズおよび数は、予め定められる。この中で、バスケット４００のサイズおよび数は、全順序集合１３１のレコードの値、論理演算に用いるメモリ１２０のサイズに応じて設定される。例えば、バスケット４００のサイズは、当該バスケット４００に分類される全レコードの総サイズが、メモリ１２０のサイズを超えないよう決定される。

　論理演算において、一般的に用いられるビットマップを使用すると和も積も追加の作業変数（作業領域）を必要としない。ビットマップは大きい集合でも小さい集合でも使用領域のサイズは同じであり、ただビット１が多いか少ないかだけである。従って、バスケット４００のサイズは、使用可能なメモリ量をＭとし、集合の数をＮとすると、最大で、Ｍ／Ｎまでとることができる。

　例えば、振分条件がレコード値の範囲の場合は、範囲の幅を、メモリ１２０のサイズに応じて決定する。振分条件が、剰余の場合は、メモリ１２０のサイズに応じて、除数を決定する。

　なお、バスケット数は、多いと１回に行う演算の量が減少し、少ないと１回の演算の量が増加する。従って、結局、演算量はバスケット数とは関係ないが、バスケット４００の数が少ないほうがＩ／Ｏ切り替え回数が減少するため、一般には有利である。なお、最少のバスケット４００の数は、集合全体のサイズをＴとすると、Ｔを、バスケット４００のサイズＭ／Ｎで除して、Ｎ×Ｔ／Ｍ個となる。

　本実施形態の分類部２１１による、分類処理を、図７（ａ）に示すように、図２に示す３つの順序集合Ａ、Ｂ、Ｃを用い、具体例で説明する。ここで実行する論理演算は、従来手法説明時と同様に、Ａ×（Ｂ＋Ｃ）とする。

　ここでは、図７（ｂ）に示すように、各バスケット４００の振分条件は、レコード値の範囲とする。すなわち、レコード値が、振分条件で指定されたレコード値の範囲に合致するレコードが、当該バスケット４００に振分られる。

　ここでは、一例として、３つのバスケット４０１、４０２、４０３を用意する。第一のバスケット４０１の振分条件は、レコードの値が範囲［０..２］にあるもの、すなわち、レコード値が（０，１，２）であるものとし、第二のバスケット４０２の振分条件は、同［３..６］、すなわち、同（３，４，５，６）とし、第三のバスケット４０３の振分条件は、同［７..１０］、すなわち、同（７，８，９，１０）とする。

　図７（ｂ）に示すように、本実施形態の分類部２１１は、順序集合Ａ、Ｂ、Ｃ毎に、レコード番号順に、各レコードを、各バスケット４０１、４０２、４０３に分類する。順序集合Ａについては、第一のバスケット４０１［０..２］には、レコード番号１の、レコード値が２のレコード（以後、単にレコード２と呼ぶ。）が、第二のバスケット４０２［３..６］には、レコード番号０のレコード３、レコード番号２のレコード５およびレコード番号５のレコード４が、第三のバスケット４０３［７..１０］には、レコード番号３のレコード８およびレコード番号５のレコード１０が、それぞれ分類される。

　順序集合Ｂおよび順序集合Ｃも同様に、図７（ｂ）に示すように、それぞれのバスケット４０１、４０２、４０３に、各レコードが分類される。

　分類後の、各順序集合１３１の部分順序集合１３３を図７（ｃ）に示す。本図に示すように、順序集合Ａは、第一のバスケット４０１に分類される部分順序集合１３３（Ａ４０１）と、第二のバスケット４０２に分類される部分順序集合１３３（Ａ４０２）と、第三のバスケット４０３に分類される部分順序集合１３３（Ａ４０３）とに分割（区分）される。同様に、順序集合Ｂは、部分順序集合１３３（Ｂ４０１）、部分順序集合１３３（Ｂ４０３）に、順序集合Ｃは、部分順序集合１３３（Ｃ４０１）、部分順序集合１３３（Ｃ４０２）、部分順序集合１３３（Ｃ４０３）に分割される。

　本実施形態の論理演算部２１２は、バスケット毎に論理演算を行う。すなわち、図７（ｂ）の例では、第一のバスケット４０１、第二のバスケット４０２、第三のバスケット４０４内のレコード間で論理演算を行う。ここでは、以下に示す、３回の演算を行う。
１）Ａ４０１×（Ｂ４０１＋Ｃ４０１）＝（２）×（２，１，０）＝（２）
２）Ａ４０２×（Ｂ４０２＋Ｃ４０２）＝（３，５，４）×（３，４）＝（３，４）
３）Ａ４０３×（Ｂ４０３＋Ｃ４０３）＝（８，１０）×（７，８，９，１０）
　　　　　　　　　　　　　　　　　　＝（８，１０）

　本実施形態では、上述のように、各バスケット４００（４０１、４０２、４０３）のカテゴリは、重複していない。このため、１のバスケット４００内の論理演算の結果は、他のバスケット４００のそれと常に分離独立である。このため、本実施形態の直和部２１は、各バスケット４００（４０１、４０２、４０３）の論理演算結果の直和を計算し、演算結果を得る。上記の例では、（（２）＋（３，４）＋（８，１０））を計算し、演算結果（２，３，４，８，１０）を得る。

　なお、本実施形態では、バスケット４００に振り分ける際、各レコードを記憶装置１３０からメモリ１２０へ読み出し、いずれのバスケット４００に振り分けるか判別し、記憶装置１３０のバスケット領域に書き込む。このため、レコード数回、記憶領域１３０からメモリ１２０への読み出し、および、メモリ１２０から記憶装置１３０への書き込みが必要となる。上記の例では、それぞれ１６回、計３２回必要となる。

　しかしながら、上記演算例で、各部分順序集合が、論理演算に使用される回数は、全順序集合のサイズに「比例的」なのは明らかで、式（１）に示される従来の技術の多項式オーダーとは根本的に異なり、それぞれ１回である。また、論理演算の総回数は、上述のように、３回である。この３回の演算において、読出し回数は、それぞれの部分順序集合のレコード数と論理演算回数の積であり、１６回、書き込み回数は、演算結果のレコード数の和であり、順に、１、２、２回の合計で、５回である。従って、論理演算中の読み出し、書き込み回数は、２１回である。

　従って、本実施形態の手法によれば、図２に示す順序集合Ａ、Ｂ，Ｃ間で、論理演算Ａ×（Ｂ＋Ｃ）を実行する場合、振分時の３２回と論理演算時の２１回の合計で、５３回の読み出し、書き込み処理で済む。従来手法が、同条件で１２０回であったことと比較すると飛躍的にメモリへのアクセス回数が低減する。

　さらに、本実施形態によれば、各部分順序集合１３３間で論理演算を実行後、結果集合の統合時に、大きなメモリを消費し時間もかかる重複値排除演算を行う必要が無く、直和を計算するだけで結果を作成できるため、効率的である。

　図８に、本実施形態の演算部２１０による、順序集合１３１間の論理演算処理の流れを説明する。まず、分類部２１１が、各順序集合１３１内のレコードを、先頭から順に、それぞれスキャンして分類し、各バスケット４００に振り分ける（ステップＳ１１０１）。次に、演算部２１２が、バスケット４００単位で、レコードをメモリ１２０にロードし、論理演算を行う（ステップＳ１１０２）。論理演算結果は、記憶装置１３０などに格納する。最後に、直和部２１３が、論理演算結果をメモリ１２０にロードし、その直和を計算する（ステップＳ１１０３）。

　以上説明したように、本実施形態の情報処理装置１００は、複数の順序集合１３１間の論理演算を行う情報処理装置１００であって、前記順序集合１３１を構成する各レコードを、前記順序集合１３１毎に、それぞれ予め定めた区分(バスケット）４００に分類する分類部２１１と、各順序集合１３１の、同一の前記区分（バスケット）４００に属するレコード間で、前記論理演算を行い、演算結果を得る論理演算部２１２と、各前記区分（バスケット）４００の前記演算結果の直和を計算する直和部２１３と、を備え、前記区分（バスケット）４００は、前記複数の順序集合１３１に属する全レコードを一意に類別可能なものであることを特徴とする。

　このように、本実施形態によれば、予め、各順序集合１３１のレコードを、互いに重複しない区分に分類しておき、区分間で論理演算を行う。このとき、区分のサイズは、メモリ１２０に展開可能なサイズとする。

　このため、本実施形態によれば、バスケット４００への書き出し処理、論理演算時のバスケット４００からの読み込み処理は追加となるが、各演算処理は、メモリ１２０上に１回ロードするだけで実行できる。演算回数も、バスケット４００の数で済む。このため、従来のように、分割単位毎に、全ての組み合わせで演算を行う必要がない。このように、本実施形態によれば、演算回数を減らすことができる。さらに、演算回数が減ることにより、演算毎の、メモリ１２０へのアクセス回数も低減する。また、最終結果を得る際の重複除去演算も不要となる。

　従って、本実施形態によれば、大規模データから作成された、メモリ１２０上に展開できないほど大きな順序集合１３１に対する論理演算を、高速に、効率的に実行できる。

　なお、上記実施形態では、各順序集合１３１を、全てバスケット４００に類別しているが、これに限られない。例えば、所定サイズ以下（所定のレコード数以下）の順序集合１３１は、類別せず、そのまま演算するよう構成してもよい。

　上記の例では、例えば、順序集合ＡおよびＣのみ、類別し、順序集合Ｂは類別せずに、論理演算を行う。この場合、第一のバスケット４０１において、Ａ×（Ｂ＋Ｃ）として、２×（（１０，２，８，９）＋（１，０））を計算し、演算結果として（２）を得る。また、第二のバスケット４０２では、（３，５，４）×（（１０，２，８，９）＋（４，３））を計算し、演算結果として、（３，４）を得る。第三のバスケット４０３では、（８，１０）×（（１０，２，８，９）＋（７，８））を計算し、演算結果として、（８，１０）を得る。

　なお、上記実施形態において、各論理演算は、図９に示すように、メモリ１２０上でビットマップに展開して演算するのが効果的である。すなわち、本図に示すように、論理演算対象の部分順序集合１３３を、それぞれ、ビットマップ１３４に展開し、本図に示すように、演算を行う。

　また、上記実施形態では、論理積（ＡＮＤ）と論理和（ＯＲ）のみを用いる場合を例にあげて説明したが、論理演算は、これに限られない。例えば、否定（ＮＯＴ）も用いてもよい。ＮＯＴ演算は、ビットマップを反転することで容易に実現できる。例えば、順序集合Ａ＝（４，２，０，３）なら、バスケット４００の範囲からこれらを取り除き、～Ａ＝（１，５，６，７）を得る。なお、「～」は、否定（ＮＯＴ）を表す。これを用いて、各種の集合演算を処理できることは明らかである。

　また、各バスケット４００は、ネットワーク１７１などで接続される、異なる情報処理装置上に構築されてもよい。この場合、バスケット４００が構築される各情報処理装置は、論理演算部２１２を備え、当該バスケット４００内のデータの論理演算を行う。

　また、上記実施形態では、実際にバスケット４００と呼ばれる記憶領域を設け、各レコードを振り分けているが、これに限られない。分類部２１１が、論理演算時に、各順序集合１３１を走査し、論理演算対象のバスケット４００に振り分けられるべきレコードを抽出するよう構成してもよい。この場合、分類部２１１は、バスケット４００の数だけ、順序集合１３１を走査する。

　１００：情報処理装置、１１０：ＣＰＵ、１２０：メモリ、１３０：記憶装置、１３１：順序集合、１３２：分割順序集合、１３３：部分順序集合、１３４：ビットマップ、１４０：入力装置、１５０：出力装置、１６０：外部記憶装置、１７０：ネットワークインタフェース、１７１：ネットワーク、１８０：情報処理装置、１９０：外部記憶装置、２１０：演算部、２１１：分類部、２１２：演算部、２１２：論理演算部、２１３：直和部、３００：データベース、４００：バスケット、４０１：第一のバスケット、４０２：第二のバスケット、４０３：第三のバスケット、Ａ４０１：部分順序集合、Ａ４０２：部分順序集合、Ａ４０３：部分順序集合、Ｂ４０１：部分順序集合、Ｂ４０２：部分順序集合、Ｂ４０３：部分順序集合、Ｃ４０１：部分順序集合、Ｃ４０２：部分順序集合、Ｃ４０３：部分順序集合

Claims

　複数の集合間の論理演算方法であって、
　前記集合を構成する各レコードを、前記集合毎に、それぞれ予め定めた区分に分類し、
　同一の前記区分に属するレコード間で、前記集合間の論理演算を行い、演算結果を得、
　前記区分毎の前記演算結果の直和を計算し、
　前記区分は、前記複数の集合に属する全レコードを一意に類別可能なものであること
　を特徴とする集合間の論理演算方法。
　請求項１記載の論理演算方法であって、
　前記区分のサイズは、前記論理演算を行う際、展開するメモリのサイズに応じて決定されること
　を特徴とする論理演算方法。
　請求項２記載の論理演算方法であって、
　前記区分のサイズは、当該区分に分類される全レコードの総サイズが、前記メモリのサイズを超えないよう決定されること
　を特徴とする論理演算方法。
　請求項１から３いずれか１項記載の論理演算方法であって、
　前記区分は、前記レコードの値の範囲で定められること
　を特徴とする論理演算方法。
　請求項１から３いずれか１項記載の論理演算方法であって、
　前記区分は、予め定めた２以上の整数の剰余で定められること
　を特徴とする論理演算方法。
　複数の集合間の論理演算を行う情報処理装置であって、
　前記集合を構成する各レコードを、前記集合毎に、それぞれ予め定めた区分に分類する分類部と、
　同一の前記区分に属するレコード間で、前記集合間の論理演算を行い、演算結果を得る論理演算部と、
　前記区分毎の前記演算結果の直和を計算する直和部と、を備え、
　前記区分は、前記複数の集合に属する全レコードを一意に類別可能なものであること
　を特徴とする集合間の情報処理装置。
　コンピュータを、
　複数の集合に属する全レコードを一意に類別可能な区分に、当該レコードを前記集合毎に分類する分類手段、
　同一の前記区分に属するレコード間で、予め定めた前記集合間の論理演算を行い、演算結果を得る論理演算手段、
　前記区分毎の前記演算結果の直和を計算する直和手段、として機能させるためのプログラム。