於 WWW論文読み会（webkai） 東京大学 岡崎直観（辻井研究室）.  以下のURLに置いてあります ◦

Presentation on theme: "於 WWW論文読み会（webkai） 東京大学 岡崎直観（辻井研究室）.  以下のURLに置いてあります ◦"— Presentation transcript:

1 於 WWW論文読み会（webkai） 東京大学 岡崎直観（辻井研究室）

2  以下のURLに置いてあります ◦ http://www.chokkan.org/www2009/ http://www.chokkan.org/www2009/

3 H. Yan, S. Ding, and T. Suel. (NYU & Yahoo! Research) Inverted index compression and query processing with optimized document ordering, WWW2009, pp. 401-410.

4  転置リスト（inverted list; posting list） ◦ “直観”: [[56, 1, [34]], [198, 2, [14,23]], [1034, 1, [43]]]  d-gapによる転置インデックスの圧縮 ◦ 文書IDの最割り当て  アイディア: 文書IDをうまく並べ替えて，転置リスト中の文書ID を互いに近い値にしたい  うまい方法: 文書のURLのアルファベット順に文書IDを再割当  ↑「直観」という語はwww.chokkan.orgドメインで頻出するwww.chokkan.org  “直観”: [[56, 1, [34]], [57, 2, [14,23]], [60, 1, [43]]] ◦ 文書IDの差分（d-gap）で転置リストを表現  “直観”: [[55, 1, [34]], [0, 2, [14,23]], [2, 1, [43]]]  d-gapは小さい値を取るので，圧縮しやすくなる 文書ID頻度出現位置 d-gapは0か ら始まる

5  Var-Byte Coding ◦ 表現形式: fddddddd（f: 連結フラグ; d: 値）  fが1なら後に続く8bitの数値と連結する ◦ 142 = (10001110) b → 10000001 00001110 ◦ 2 = (10) b → 00000010 ◦ デコードは速いけど，圧縮率が低い  Rice Coding ◦ 表現形式: 1 q 0rrrr…（q個の1の後0，続いてm bitのr）  q = int(n / 2 m ), r = n % 2 m  m = 4のとき，  142 → (q = 8, r = 14) → 1111111101110  2 → (q = 0, r = 2) → 00010  Var-Byte Codingよりはデコードが遅いけど，圧縮率が良い

6  Simple9 (S9) ◦ 表現形式: ssssdddd dddddddd dddddddd dddddddd  4 bitのステータスコードで，dの箇所に何個の数字が詰まってい るかを表す（以下の９通り）  0000: 28個の数（1bit），0001: 14個の数（2bit），  0010: 9個の数（3bit），0011: 7個の数（4bit），  0100: 5個の数（5bit），0101: 4個の数（7bit），  0110: 3個の数（9bit），0111: ２個の数（14bit），  1000: 1個の数（28bit） ◦ (142 2 17)をS9で表現すると  01100100 01110000 00001000 00100010 ◦ ステータスコードの部分をビットマスクで取り出し，テーブ ルジャンプでデータを読み取れば，高速にデコードできる ◦ S16という拡張は，16通りのデータ表現で圧縮率を向上

7  PForDelta ◦ 数値をN個ずつエンコードする（例えばN = 128）  それらの数値の90%を格納できるビット長bを決める  2 b 以上の数値は，例外として別に格納する ◦ (23, 41, 8, 12, 30, 68, 18, 45, 21, 9, …)を格納する  90%以上が2 5 = 32未満とし，m = 5と決定  |1 23 3 8 12 30 1 18 2 21 9 …|… 45 68 41| ◦ 高速化のテクニック  異なるb毎にハードコーディングしておく  キャッシュに載るようにブロック毎にデコードする  Interpolative Coding ◦ 面白いけど省略 先頭の例外位置これらの数字は5bitで格納 例外は4バイトで表現 （逆順に並べる）

8  PForDelta (PFD) を速度，圧縮率の面で改良する  転置リストに含まれる頻度数値の圧縮方法を提案 ◦ move-to-front codingにインスパイアされた  文書IDを並べ替えることの効果を調べる ◦ TREC GOV2でインデックスのサイズを50%削減  様々な圧縮方法の速度，圧縮率を調べる ◦ 転置リスト毎に圧縮方法を適応的に決める方法を示す  TREC GOV2とは ◦ 2004年にクロールされた.govドメインの2520万件の ウェブページと，10万件のクエリ例

9  NewPFD ◦ 既存のPFDの問題点  オフセットの値が2 b に収まりきらないとき，2 b よりも小さい数を 例外扱いにして，オフセットのリストを連結しなければならない ◦ 改善法  例外を格納する配列，例外の位置を示す配列を分離させる  (23, 41, 8, 12, 30, 68, 18, 45, 21, 9, …)でm=5の場合  下位ビット数値配列: (21 9 8 12 30 4 18 13 21 9 …)  例外オフセット配列: (1 3 1 …)  上位ビット数値配列: (9 4 13)  OptPFD ◦ デコード速度と圧縮率はトレードオフの関係にある ◦ インデックスのサイズとデコード速度の比が最小になるよう にmを決める（詳細は省略） S16でエンコードする

10

11  単調増加ではないが… ◦ 文書IDをURL順で整列すれば， 似たような頻度が近くに出現  同じドメインのウェブページの単語 頻度分布は似る  先頭移動法 ◦ Move-To-Front (MTF） ◦ Burrows-Wheeler変換（ブロッ クソート）等と組み合わせて， データ圧縮に用いられる  Most-Likely-Next (MLN) ◦ Q個の数値に対してQ×Qの行列 を作り，i行j列が，数値iの後に (j+1)番目に出現しやすい数値を 格納しておく ◦ jのインデックス番号のみをエン コードする  これらの手法は同一，もしく は似たような頻度の数値が連 続するときに有効 # 値テーブル符号 0(1, 2, 3, 4, 5)() 15(5, 1, 2, 3, 4)(5)(5) 25 (5, 1) 35(5, 1, 2, 3, 4)(5, 1, 1) 43(3, 5, 1, 2, 4)(5, 1, 1, 4) 52(2, 3, 5, 1, 4)(5, 1, 1, 4, 4) 62(2, 3, 5, 1, 4)(5, 1, 1, 4, 4, 1) (5, 5, 5, 3, 2, 2)をMTF圧縮する例

12

13 J. Chen, L. Subramanian, J. Li. (NYU) RuralCafe: Web Search in the Rural Developing World, WWW2009, pp. 411-420

14  世界にはWebに繋がりづらい地域がたくさんある ◦ 100-1000人のユーザーが，128Kbpsの帯域を分け合っ ている大学や会社など  インドのBPO部門では，50-100人のスタッフが64Kbpsの インターネット回線を共有している ◦ 携帯電話におけるデータ転送よりもSMSのコストが安い ので，SMSベースで検索をやることがある ◦ 巡回インターネット・キオスク  アジア，アフリカ，ラテンアメリカの農村部において，バ スなどで巡回しているWiFiインターネット・キオスク ◦ 停電が頻発する地域もある

15  2009年9月10日 ◦ BBC News （動画有り）  http://news.bbc.co.uk/2/hi /africa/8248056.stm http://news.bbc.co.uk/2/hi /africa/8248056.stm ◦ ITMedia News  http://www.itmedia.co.jp/n ews/articles/0909/10/news 075.html http://www.itmedia.co.jp/n ews/articles/0909/10/news 075.html  伝書鳩 ◦ 4GBのメモリースティックを 装着した生後11ヶ月のハト が，80kmを1時間8分で飛ぶ ◦ コンピュータとメモリース ティック間のデータを転送す る時間を含めても，2時間6 分57秒だった ◦ その間，通信会社大手のテル コムのデータ転送は，4%し か完了しなかった

16  RuralCafeと呼ばれる検索環境を提案する ◦ シンプルな検索インタフェースを提供  従来の検索インタフェースは，断続的なインターネット接 続環境に十分とは言えない ◦ ローカルなキャッシュの検索をサポート ◦ よく用いられる検索フレーズをローカルに保存  ユーザーのクエリは不十分だったり曖昧であることが多い ◦ 断続的なインターネット接続環境の様々なケースに対応 ◦ 検索結果の先読みを行い，ローカルなキャッシュ上で検 索できるように準備する

17 検索ジョブの進行状況 を表示するペーン 「テキストのみ」「テキス トと画像」「全部」 曖昧（たくさんの短い検索結果が 返される），普通，深い（長めの 少ない検索結果が返される） クエリ拡張やクエリ訂正を行う ペーン 通常のクエリ，合成クエリ（OR 連結），エンティティ絞り込み検 索（電話番号など）

18 N-gramによるク エリ拡張・訂正 ローカル検索データ転送制御

19 S. Ding, J. He, H. Yan, T. Suel. (NYU & Yahoo! Research) Using Graphics Processors for High Performance IR Query Processing, WWW2009, pp. 421-430.

20  情報検索システムは数千のサーバーでクラスター化 ◦ １サーバーあたりの速度を向上させることも大切  本研究では，以下のタスクにおいてGPUの利用を考える ◦ 圧縮された転置リストのデコード ◦ 圧縮された転置リストをデコードしながらjoinを取る  GPUの利用環境 ◦ NVIDIA GeForce 8800 GTS (640MB; 32 threds) ◦ Compute Unified Device Architecture (CUDA)

21  Inclusive parallel prefix sum ◦ [a 0, a 1, …, a n-1 ] → [a 0, a 0 +a 1, …, a 0 +a 1 +…+a n-1 ]  Exclusive parallel prefix sum ◦ [a 0, a 1, …, a n-1 ] → [0, a 0, a 0 +a 1, …, a 0 +a 1 +…+a n-2 ]  普通に実装すると，並列化が難しい ◦ for (i =1;i <= n;++i) s[i] = s[i-1] + a[i-1] ◦ n回の加算演算でO(n)  CUDAによる実装は，以下の資料を参照 ◦ http://developer.download.nvidia.com/compute/cuda/sd k/website/projects/scan/doc/scan.pdf http://developer.download.nvidia.com/compute/cuda/sd k/website/projects/scan/doc/scan.pdf ◦ 2*(n-1)回の加算，(n-1)回のコピーで，O(n)  演算回数は増えているが，32個のスレッドを使うので高速

22

23

24  Rice符号でエンコードさ れたd-gap列から文書ID 列を復元 ◦ Rice符号をデコードしながら Parallel Prefix Sumを取る  文書ID列をd-gap列に変 換しRice符号エンコード ◦ 文書IDs: [143, 146, 164] ◦ d-gaps: [142, 2, 17] ◦ Rice符号 (m = 4 のとき)  q系列: 111111110010  r系列: 111000100001  文書 ID 列のデコード ◦ q 系列のデコード  まず， q 系列を 1-bit で構成された 数値列と見なして parallel prefix sum を計算  [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9]  元々の q 系列で 0 が埋められていた 箇所の数字を抜き出して配列に  [8, 8, 9] ◦ r 系列のデコード  4-bit で構成される数値列と見なし て parallel prefix sum を計算  [14, 16, 17] ◦ 最後にまとめる  [8*2 4 +14+1, 8*2 4 +16+2, 9*2 4 +17+3] = [143, 146, 164] 通常のrice符号とは異なり，qとrを 別々のビットストリームに格納

25  Rice符号 ◦ GPUよりもCPUの方が若干高速だった ◦ ただし，CPUはd-gapから文書IDの復元を行っていない のに対し，GPUでは同時に行っている  PForDelta ◦ CPUよりもGPUの方が高速だった

26  基本的なアイディア ◦ ２つの転置リストをマージするとき，分割要素を適当に決め て，転置リストをセグメントに分割する ◦ 分割されたセグメント同士でリストのマージを並列に行う  実際には，転置リストを２分割する処理を分割統治で 再帰的に行い，セグメントを細分化してマージする

27

28  スキップポインタを用いた集合和・積  GPUを用いた並列スコア計算 ◦ 今回の実験ではBM25を利用している  GPUを用いたtop-k文書選択  OR検索のサポート ◦ Term-At-A-Time (TAAT)で文書ID毎にスコアを計算  CPUとGPUを上手く組み合わせるスケジューリング