頻出飽和集合とかのメモ2

その他

2つやったことの記録。ビットマップ化と振り分け処理の改良失敗。
振り分け処理の改造は、ハッシュ(Dictionary)を使っているところを、マージ(マージソートのマージ。併合)にしてみたけど遅くなった。もう少し改造してみるけど早くなりそうな気はしない…。
ビットマップ化は、アイテムが疎なら遅くなるって最初の入門PDFにも書いてあるけど、ビット黒魔術で遊びたかった。そして、遅くなっただけだったｗ

ビットマップ化はグラフの隣接行列表現

グラフ理論のグラフを表現する方法として、主に隣接行列と隣接リストの2つがある。隣接行列は頂点と頂点の間に辺があれば1、なければ0とした行列で表現する方法。メモリの都合上、密なグラフでは隣接行列がよく、疎なグラフでは隣接リストがよい。

レコード(トランザクション)とアイテムを頂点とした2部グラフ(前回のメモ参照)と考えたときに、それをあらわす隣接行列がビットマップ。

A {1,2,3,4}
B {1,2,3,5}
C {1,2,3,6}

とあれば、アイテムを各ビット位置であらわし、1 => 00 0001, 2 => 00 0010, ... ,6 => 10 0000とすると

  | 654321
A | 001111
B | 010111
C | 100111

となる。列が654321のアイテムで、行がABCのレコードの行列になる。64個以下のアイテムしかなければ、1レコードが64bitで表現できる。あとはANDを取るだけで共通アイテムが求められる。
ちなみに、ビットマップ化してないときは配列でレコードを持ち、さらにレコードの配列でデータベース全体を表現している。ごくごく普通。リンクリストを使って隣接リスト表現してたりはしません。
アイテムの種類が多く、グラフが疎なときには、隣接行列が大きくなってしまう。1000種類のアイテムがあれば、1レコード1000bitになって、配列でレコードを持つよりデカイかもしれない。なので、アイテムが64個以下のときだけビットマップ化して計算するようにしてみたけど、ビットマップ化してはすぐビットマップでの計算が終わり、またビットマップ化しては(以下ry の繰り返しで、むしろ遅くなりましたとさ。ビットマップ化する際の条件を厳しくしても遅いまま。密なデータなら効果的らしい。
頻出集合を求めるのも、頻出飽和集合を求めるのも、上のABCのレコードの行列を縦に見て横に見てってことの繰り返し。
MJが亡くなったと聞いてここで書く気が失せたので、またいずれ。