高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
KOF 2008 の発表資料 - naoyaのはてなダイアリー
KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/081108huge_data.ppt 一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。 環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。 追記 SlideShare にアップロードしました。 081108huge_data.pptView SlideShare presentation or Upload your own. (tags: linux mysql) 追記: メモリはディスクの 150 倍について
「はてな流大規模データ処理」を見てきた - もぎゃろぐ
KOF2008：関西オープンソース2008というイベントに来ています。 はてなの伊藤さんの講演があったので、講演メモを公開。 ＃ボクがメモした内容であって、100%言ったとおりに書いてあるわけじゃないので、参考としてご覧ください。 (続き) アジェンダ 大規模なデータ OSのキャッシュ MySQLの運用 大規模データアプリケーションの開発 データの例 はてなブックマークのデータ量：五千万件くらいのデータ量 このデータに対して何百万人がアクセスしてくる状況でどういう作りにするか レコード数 1073万エントリー 3134万エントリー 4143万タグ データサイズ エントリー2.5GB 何の工夫もなく普通にアクセスすると...200秒待っても結果が帰ってこない 大規模データの難しいところ 開発サーバで開発者が作っている時は快適に動いていても、多数の人間がアク
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
