Information Retrieval – Addenda: Index Compression
Group VarInt In Chapter 6, we discussed the byte-aligned vByte method as an example of an index compression technique with high decoding performance. After we had written the chapter, Jeff Dean gave a keynote talk at WSDM 2009 in which he discussed a few compression algorithms used by Google, including the byte-aligned Group VarInt method. Group VarInt is named after VarInt (variable-size integer
第11回 転置索引の圧縮 | gihyo.jp
はじめに 第2回で、索引は多くの場合圧縮されていることに言及しました。また第7回では、索引構築時にどの部分で索引を圧縮すればよいかを疑似コードを用いて説明しました。今回は、転置索引の具体的な圧縮方法について説明していきます。 圧縮の目的 中規模から大規模な索引の場合、転置リストは非常に長くなり、検索時にはディスクからの大量のデータの読み取りが行われます。転置索引（を用いた検索エンジン）では、これによる検索処理時間の増加を防ぐために、転置リストを圧縮しディスクからの読み込み時間の短縮を図ります。 この場合、圧縮された転置リストをディスクから読み込みさらに復元処理を行う必要がありますが、通常は次のようになります。 これは、近年のCPUとディスクの速度差が大きいため、主にCPUにおける処理である復元処理が高速に行えることによるものです。よって、圧縮というと容量を節約の意図で使うことが多いと思いま
Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
Data-Intensive Text Processing with MapReduce ch4
http://hpc.isti.cnr.it/
