A memory efficient reachability data structure through bit vector compression

Sebastiaan J. van Schaik and Oege de Moor. 2011. A memory efficient reachability data structure through bit vector compression. In Proceedings of the 2011 international conference on Management of data (SIGMOD '11). ACM, New York, NY, USA, 913-924. DOI=10.1145/1989323.1989419 http://doi.acm.org/10.1145/1989323.1989419

• 問題
  • 到達可能性クエリ，in-memory．
• 基礎: interval lists
  • transitive closure を計算する・保存する
  • んだけど，transitive closure を，区間みたいにして持つ．頂点10から頂点20は全部いける〜みたいな．
  • 頂点をトポソ順で並べておくとこれが実はかなりうまくいく（ヒューリスティクス）
• 提案手法: bit vector compression
  • 区間で圧縮する代わりに， 01 の列を bit-vector として圧縮して保持
  • bit-vector: WAH
    • 31 bit ごとにブロック → 頭に一様かフラグ＋一様ならその数がつづくブロックの数 / そうでないならそのまま中身
  • PWAH
• 実験
  • interval lists に比べて数倍空間が良い
  • 前処理は interval lists と一緒で凄い早い（他の手法と比べて）
  • interval が各頂点にどのぐらいの数保持されるのかが知りたいなぁ（平均・分布）

interval lists は実装簡単だし，WAH にするのもそこまでじゃないし，で実験して比較すれば楽しいだろうし，演習 3 候補として良いかも． やってもらうと上記の点もわかるし．

ただ最近は reachability も on-disk 考えた議論をしている気がする (EDBT'12 等) ので，そのへんの手法と比べて性能がどうなのかというのを見極めないとワロスという可能性も．読まないと．