整数列圧縮アルゴリズムの最前線
ちょうど二年ぐらい前，機械学習で疎ベクトルの圧縮に情報検索でよく使われる整数列の圧縮技術を使うことを検討したことがあった（オンライン学習でキャッシュを実装してみた - ny23の日記）．そのときは，オンラインで圧縮し Disk に保存，圧縮したベクトルは陽にメモリに置かず読む（OS に任せる）という実装で，（Disk IO のオーバーヘッドが大きく）圧縮さえすれば何を使っても大差なしという身も蓋もない結論になった（結局2行で書ける最も単純な Variable byte code を採用）．
それ以降は整数列圧縮アルゴリズムに関する知識も NewPFD ぐらいで止まっていたのだけど，つい先日，現時点で最速の圧縮アルゴリズムの提案＋ここ数年の主な整数列圧縮アルゴリズム（Simple-8b (J. Software Pract. Exper. 2010), VSEncoding (CIKM 2010), varint-G8IU (CIKM 2011) など）＋ Google Snappy との大規模な比較を行なっている manuscript を見つけたのでメモしておく．
実装もひと通り公開されていて，非常に参考になる．作者のブログから．
実験結果では SIMD を差分計算・圧縮時の符号化・復号化に用いた提案手法が NewPFD の2倍以上高速な復号化を達成*1．SIMD すごい．扱うデータが大規模化してくると2倍以下の高速化でも大きな意味があるので，アルゴリズムにこの種の最適化が適用できるかどうかも重要になってくる*2．この手の最適化にはあまり明るくないのだけど，自分も分類器で素性の重みをラベルごとに計算する際，二値分類の場合のみループを手動で展開するという実装をすることでベクトル化の恩恵にあずかっている（1.5倍程度高速化）．
実装を眺めていてなにげに収穫だったのは，varint-G8IU (Google の Group Varint Encoding の改良版) が特許取得済っぽいことが分かったこと．論文の実験では何を使ってもいいのだけど，ソフトウェアを公開するようになってからは特許が絡んだアルゴリズムはなんとなく避けるようになっている．こういう情報，誰かまとめてくれないものかな．ちなみに，提案手法は特許を取得していないとのこと．
