Compressed indexes for string searching in labeled graphs (WWW '15)

Paolo Ferragina, Francesco Piccinno and Rossano Venturini.

概要

ラベル付きグラフの索引を作り、それに対して検索するというのはソーシャルネットワークや知識グラフを効率良く処理する上で重要になりつつある。一方既存のグラフ索引手法はグラフの隣接関係だけしか扱っていない。この論文では各ノードに可変長文字列のラベルがついたグラフの索引手法を提案する。

Facebookのエンジニアによって開発されたUnicornというソーシャルグラフの索引プラットフォームがあるがこの論文ではそれをされに発展させる。例えば「あるユーザの２近傍にいるユーザ（友達か友達の友達で）で特定のprefixをもつものをリストアップする」といったクエリに応答したい。これはFacebookなどで友人などを探すときに良く起こりうるシチュエーションである。このようなクエリに対応するにあたって愚直に全てのユーザのprefixを見ていくというのは現実的でない。なぜなら第二近傍の頂点数は非常に大きくなることが多いからである。この論文では以下の問題を高速に処理するためのデータ構造とアルゴリズムを提案している。

隣接する頂点で指定されたprefixを持つものをリストアップ
２近傍の頂点で指定されたprefixを持つものをリストアップ
２近傍の頂点で指定されたprefixを持つもので各頂点にあらかじめ与えられているスコアが大きいk個をリストアップ

頂点番号を文字列の辞書順に並び替えてRange Queryをやる。スコアを考える場合はRange Maximum Queryを利用して高速化する。されにTop-Kを計算する上でヒューリスティクスをいれる。各クエリにおいて最大20-50倍高速化できるらしい。