整数列圧縮アルゴリズムの最前線 - ny23の日記
ちょうど二年ぐらい前，機械学習で疎ベクトルの圧縮に情報検索でよく使われる整数列の圧縮技術を使うことを検討したことがあった（オンライン学習でキャッシュを実装してみた - ny23の日記）．そのときは，オンラインで圧縮し Disk に保存，圧縮したベクトルは陽にメモリに置かず読む（OS に任せる）という実装で，（Disk IO のオーバーヘッドが大きく）圧縮さえすれば何を使っても大差なしという身も蓋もない結論になった（結局2行で書ける最も単純な Variable byte code を採用）． それ以降は整数列圧縮アルゴリズムに関する知識も NewPFD ぐらいで止まっていたのだけど，つい先日，現時点で最速の圧縮アルゴリズムの提案＋ここ数年の主な整数列圧縮アルゴリズム（Simple-8b (J. Software Pract. Exper. 2010), VSEncoding (CIKM 20
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
MapReduce と四身の拳 - ny23の日記
最近大規模データを処理するのに MapReduce とかがよく使われるのだけど，クラウドなど分散環境を使う人は基礎的なアルゴリズムを書く訓練もした方がいい．そもそも並列・分散系の環境は，最高速のアルゴリズムでも時間がかかる処理を，さらに速くするために使うべきものであって，基礎的なアルゴリズムの高速な実装ができない人が，実装をサボるために使うべきものではない．基礎的なアルゴリズムの差は MapReduce を使っても残る．特にデータが巨大になり，かかる時間が伸びれば延びるほど，基礎的なアルゴリズムの速度差が致命的になる（10分かかる処理が20分かかっても気にならないかもしれないが，1週間かかる処理が2週間もかかったら致命的; 1000台あるマシンを2000台に増やす方法を考える前に，ベースのプログラムの処理速度を2倍にすべし）． こんな例を出すと，年がバレるが，日曜プログラマが1000台のマ
大規模データで単語の数を数える - ny23の日記
大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
