Query Processing

於 WWW論文読み会（webkai）
東京大学岡崎直観（辻井研究室）

以下のURLに置いてあります
◦ http://www.chokkan.org/www2009/
H. Yan, S. Ding, and T. Suel.
(NYU & Yahoo! Research)
Inverted index compression
and query processing with
optimized document ordering,
WWW2009, pp. 401-410.

転置リスト（inverted list; posting list）
◦ “直観”: [[56, 1, [34]], [198, 2, [14,23]], [1034, 1, [43]]]
文書ID

頻度
出現位置
d-gapによる転置インデックスの圧縮
◦ 文書IDの最割り当て
 アイディア: 文書IDをうまく並べ替えて，転置リスト中の文書ID
を互いに近い値にしたい
 うまい方法: 文書のURLのアルファベット順に文書IDを再割当
 ↑「直観」という語は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は小さい値を取るので，圧縮しやすくなる
d-gapは0か
ら始まる

Var-Byte Coding
◦ 表現形式: fddddddd（f: 連結フラグ; d: 値）
 fが1なら後に続く8bitの数値と連結する
◦ 142 = (10001110)b → 10000001 00001110
◦ 2 = (10)b → 00000010
◦ デコードは速いけど，圧縮率が低い

Rice Coding
◦ 表現形式: 1q0rrrr…（q個の1の後0，続いてm bitのr）
 q = int(n / 2m), r = n % 2m
 m = 4のとき，
 142 → (q = 8, r = 14) → 1111111101110
 2 → (q = 0, r = 2) → 00010
 Var-Byte Codingよりはデコードが遅いけど，圧縮率が良い

Simple9 (S9)
◦ 表現形式: ssssdddd dddddddd dddddddd dddddddd
 4 bitのステータスコードで，dの箇所に何個の数字が詰まってい
るかを表す（以下の９通り）





0000:
0010:
0100:
0110:
1000:
28個の数（1bit），0001: 14個の数（2bit），
9個の数（3bit），0011: 7個の数（4bit），
5個の数（5bit），0101: 4個の数（7bit），
3個の数（9bit），0111: ２個の数（14bit），
1個の数（28bit）
◦ (142 2 17)をS9で表現すると
 01100100 01110000 00001000 00100010
◦ ステータスコードの部分をビットマスクで取り出し，テーブ
ルジャンプでデータを読み取れば，高速にデコードできる
◦ S16という拡張は，16通りのデータ表現で圧縮率を向上

PForDelta
◦ 数値をN個ずつエンコードする（例えばN = 128）
 それらの数値の90%を格納できるビット長bを決める
 2b以上の数値は，例外として別に格納する
◦ (23, 41, 8, 12, 30, 68, 18, 45, 21, 9, …)を格納する
 90%以上が25 = 32未満とし，m = 5と決定
 |1 23 3 8 12 30 1 18 2 21 9 …|… 45 68 41|
先頭の例外位置
これらの数字は5bitで格納
◦ 高速化のテクニック
例外は4バイトで表現
（逆順に並べる）
 異なるb毎にハードコーディングしておく
 キャッシュに載るようにブロック毎にデコードする

Interpolative Coding
◦ 面白いけど省略


PForDelta (PFD) を速度，圧縮率の面で改良する
転置リストに含まれる頻度数値の圧縮方法を提案
◦ move-to-front codingにインスパイアされた

文書IDを並べ替えることの効果を調べる
◦ TREC GOV2でインデックスのサイズを50%削減

様々な圧縮方法の速度，圧縮率を調べる
◦ 転置リスト毎に圧縮方法を適応的に決める方法を示す

TREC GOV2とは
◦ 2004年にクロールされた.govドメインの2520万件の
ウェブページと，10万件のクエリ例

NewPFD
◦ 既存のPFDの問題点
 オフセットの値が2bに収まりきらないとき，2bよりも小さい数を
例外扱いにして，オフセットのリストを連結しなければならない
◦ 改善法
 例外を格納する配列，例外の位置を示す配列を分離させる
 (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 …)
S16でエンコードする
 上位ビット数値配列: (9 4 13)

OptPFD
◦ デコード速度と圧縮率はトレードオフの関係にある
◦ インデックスのサイズとデコード速度の比が最小になるよう
にmを決める（詳細は省略）

単調増加ではないが…

◦ 文書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)
()
1
5 (5, 1, 2, 3, 4)
(5)
2
5 (5, 1, 2, 3, 4)
(5, 1)
3
5 (5, 1, 2, 3, 4)
(5, 1, 1)
4
3 (3, 5, 1, 2, 4)
(5, 1, 1, 4)
5
2 (2, 3, 5, 1, 4)
(5, 1, 1, 4, 4)
6
2 (2, 3, 5, 1, 4)
(5, 1, 1, 4, 4, 1)
(5, 5, 5, 3, 2, 2)をMTF圧縮する例
J. Chen, L. Subramanian, J. Li.
(NYU)
RuralCafe: Web Search in the
Rural Developing World,
WWW2009, pp. 411-420

世界にはWebに繋がりづらい地域がたくさんある
◦ 100-1000人のユーザーが，128Kbpsの帯域を分け合っ
ている大学や会社など
 インドのBPO部門では，50-100人のスタッフが64Kbpsの
インターネット回線を共有している
◦ 携帯電話におけるデータ転送よりもSMSのコストが安い
ので，SMSベースで検索をやることがある
◦ 巡回インターネット・キオスク
 アジア，アフリカ，ラテンアメリカの農村部において，バ
スなどで巡回しているWiFiインターネット・キオスク
◦ 停電が頻発する地域もある

2009年9月10日
◦ BBC News （動画有り）
 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

伝書鳩
◦ 4GBのメモリースティックを
装着した生後11ヶ月のハト
が，80kmを1時間8分で飛ぶ
◦ コンピュータとメモリース
ティック間のデータを転送す
る時間を含めても，2時間6
分57秒だった
◦ その間，通信会社大手のテル
コムのデータ転送は，4%し
か完了しなかった

RuralCafeと呼ばれる検索環境を提案する
◦ シンプルな検索インタフェースを提供
 従来の検索インタフェースは，断続的なインターネット接
続環境に十分とは言えない
◦ ローカルなキャッシュの検索をサポート
◦ よく用いられる検索フレーズをローカルに保存
 ユーザーのクエリは不十分だったり曖昧であることが多い
◦ 断続的なインターネット接続環境の様々なケースに対応
◦ 検索結果の先読みを行い，ローカルなキャッシュ上で検
索できるように準備する
クエリ拡張やクエリ訂正を行う
ペーン
検索ジョブの進行状況
を表示するペーン
通常のクエリ，合成クエリ（OR
連結），エンティティ絞り込み検
索（電話番号など）
曖昧（たくさんの短い検索結果が
返される），普通，深い（長めの
少ない検索結果が返される）
「テキストのみ」「テキス
トと画像」「全部」
ローカル検索
N-gramによるク
エリ拡張・訂正
データ転送制御
S. Ding, J. He, H. Yan, T. Suel.
(NYU & Yahoo! Research)
Using Graphics Processors for
High Performance IR Query
Processing, WWW2009, pp.
421-430.

情報検索システムは数千のサーバーでクラスター化
◦ １サーバーあたりの速度を向上させることも大切

本研究では，以下のタスクにおいてGPUの利用を考える
◦ 圧縮された転置リストのデコード
◦ 圧縮された転置リストをデコードしながらjoinを取る

GPUの利用環境
◦ NVIDIA GeForce 8800 GTS (640MB; 32 threds)
◦ Compute Unified Device Architecture (CUDA)

Inclusive parallel prefix sum
◦ [a0, a1, …, an-1] → [a0, a0+a1, …, a0+a1+…+an-1]

Exclusive parallel prefix sum
◦ [a0, a1, …, an-1] → [0, a0, a0+a1, …, a0+a1+…+an-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
◦ 2*(n-1)回の加算，(n-1)回のコピーで，O(n)
 演算回数は増えているが，32個のスレッドを使うので高速

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
通常のrice符号とは異なり，qとrを
別々のビットストリームに格納

文書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*24+14+1, 8*24+16+2,
9*24+17+3] = [143, 146, 164]

Rice符号
◦ GPUよりもCPUの方が若干高速だった
◦ ただし，CPUはd-gapから文書IDの復元を行っていない
のに対し，GPUでは同時に行っている

PForDelta
◦ CPUよりもGPUの方が高速だった

基本的なアイディア
◦ ２つの転置リストをマージするとき，分割要素を適当に決め
て，転置リストをセグメントに分割する
◦ 分割されたセグメント同士でリストのマージを並列に行う

実際には，転置リストを２分割する処理を分割統治で
再帰的に行い，セグメントを細分化してマージする


スキップポインタを用いた集合和・積
GPUを用いた並列スコア計算
◦ 今回の実験ではBM25を利用している


GPUを用いたtop-k文書選択
OR検索のサポート
◦ Term-At-A-Time (TAAT)で文書ID毎にスコアを計算

CPUとGPUを上手く組み合わせるスケジューリング

Download Report