複数の集約演算のための並列アルゴリズム

データマイニングやOLAPなどに代表されるデータ分析ツールでは、通常、デー タをそのまま用いるのではなく、集約演算を施すことで、ユーザのデータ解析 を容易にする。集約演算とは、データの持つ属性のうち、いくつかの属性に注 目し、これをグループ化することによって、グループ毎に個数、平均、合計、 最大値などを求める処理のことである。例えば、銀行の顧客データについて、 預金残高に注目し、預金残高に応じて、これをいつくかのグループに分割し、 グループ毎に人数を調べれば、預金残高の分布を知ることができる。また、年 齢別にグループ化し、各グループの預金残高の合計と人数から年齢別の平均預 金残高の分布を求めることができる。

TRLのデータマイニングシステム (System for Optimized Numeric Association Rules) では、このような分布から、数値属性を用 いた相関ルールを発見しているのである。ここで、このシステムが単一のマシンを用 いて、数百万件のデータを処理しようとすると、高速で処理されるデータの分 布からの最適領域の切り出しの時間に対して、データの分布の計算(すなわち 集約演算)にその何倍もの時間を費やしてしまうという問題が発生する。この ボトルネックを解消するためには、並列計算機を用いて、並列処理を行なう方 法が考えられる。従来から行なわれている集約演算の並列処理技術は、単一の 集約演算を如何に高速に計算するかを目的としている。データマイニングのよ うに、考えられる全てのルールについて、データの分布が求めなければならな いようなシステムでは、上記の単一集約演算の並列アルゴリズムを複数回繰り 返し、計算することが必要となる。しかし、単一演算を複数回繰り返すことは、 決して、効率が良いとは言えない。そこで、我々は、複数の集約演算を効率良 く計算するアルゴリズムを開発した。なお、詳細はここ を御覧下さい。