Blog
初めまして，新入社員の楠本です．今年の4月からPFIで働いています．
先週 SIGMOD 2014 (Special Interest Group on Management of Data) という学会に参加してきたのでその参加記を記したいと思います．
SIGMOD はデータベース分野でトップに位置づけられる会議の1つです．SIGMOD では併設で PODS という理論系データベースの会議も同時開催されています．
今年はアメリカ合衆国ユタ州のスノーバードというスキーリゾート地で開催されました．この時期は夏だったのでスキーはなかったのですが自然が雄大な場所でした．(↓写真)
今回は修士時代にやっていた研究の論文が受理されたので，発表(と他の発表の聴講)をするために参加しました．
会議について
SIGMOD/PODS は全部で6日間開催されており，以下のようなスケジュールで行われていました．
- 1日目：ワークショップ
- 2日目：PODS
- 3日目：SIGMOD / PODS
- 4日目：SIGMOD
- 5日目：SIGMOD
- 6日目：ワークショップ
ワークショップは参加費が高かったので2日目から5日目にかけて参加しました．
会議ではいくつものセッションが常に並列されていました．チュートリアルやデモセッションも含めると常に6並列で行われていたようです．
そうなると全部の発表を見るのはとても無理なのですが，その埋め合わせとして(？)夜に全ての研究についてのポスターセッションが開かれていて，興味のあるものはオーラルで聞いて，聞き逃したりしたものはポスターで聞くということが可能になっていました．
リサーチペーパーには418本の提出があり，そのうち107本が採択されました (採択率25%)．去年に比べると採択率が上がっています(去年は20%)．
採択された論文の本数を国別で見ると今年は圧倒的に US が多く，その次に大きく差を開けて中国が続くという風になっていました．日本からは 3 本の論文が採択されていました．
来年の SIGMOD はメルボルン，再来年はサンフランシスコで開催される予定だそうです．
今回発表した論文について
今回採択された論文は NII の前原さんと河原林先生との共著です．
SimRank というリンクベースで2つのオブジェクトの類似度を計算する指標があるのですが，それを効率よく計算するアルゴリズムを提案しました．(論文リンク)
個人的な話をさせて頂きますと，僕は元々修士の頃に JST/ERATO の河原林巨大グラフプロジェクト という研究プロジェクトでリサーチアシスタントをやっていたのですが，今回の件はそこでやっていた研究の1つになります．
(余談ですが，今回の論文のテーマであるところの SimRank を違う問題設定で計算する研究を同時期にやっていて，そちらは先日 KDD(Knowledge Discovery and Data Mining) に採択されました．)
それぞれの発表について
SIGMOD はデータベースの会議なのでデータベースがメインに扱われているのですが，僕は(上に書いたように元々実ネットワークを対象にした研究プロジェクトにいたこともあって)実ネットワーク上のアルゴリズムやデータ構造に興味があるのでそういう系のセッションに張り付いて聞いていました．
聞いた発表でいくつか印象に残ったものを雑多に紹介したいと思います．
Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
(Youze Tang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University; Yanchen Shi, Nanyang Technological University)
影響最大化(Influence Maximization )とは「ソーシャルネットワーク上でいかに口コミを色んな人に広めるか」という問題です．
厳密には，ネットワーク \(G=(V,E)\) が与えられるので，そのうちの頂点の部分集合 \(S \subseteq V\) を選んで，最初に \(S\) が口コミを広げた後，最終的に広まる口コミの影響を最大にするのが目的です．
口コミの広まり方には色々なものがありますが，Independent Cascade Model というモデルがよく使われている気がします．このモデルでは，口コミはターン制で広がり，ある人が口コミを拡散することになった後，別の人に広まるかどうかは確率的に独立に決まるという風になっています．確率はネットワークの枝ごとに設定されています．
(説明が雑ですいません．詳しくはググってください．)
扱うものは口コミでなくても影響を広めるものならなんでもよいです．
Independent Cascade Model では貪欲法を使って選ぶと最適解の近似解が得られることが劣モジュラ性により保証されるという話があるのですが，このとき計算速度に時間が掛かることが問題になっていました．
既存研究で，確率的アルゴリズムによって計算時間を大体線形時間にしたものがあって，理論的には高速なものの実用的には定数倍が大きくて使えないというものがありました．
この発表では，(おそらくその既存研究の手法を元に？)実用的にも高速で精度もよいアルゴリズムを提案していました．
ちなみにこの発表は「Social Networks I」というセッションに配置されていたのですが，他の発表も影響最大化に関するものだったので，実質的に影響最大化に関するセッションになっていました．個人的には，影響最大化は問題としては面白いけど実際に使う場合どうするんだろうなぁと疑問に思うところもあるのですが，人気分野になっているようです．
Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs
(Yubao Wu, Case Western Reserve University; Ruoming Jin, Kent State University; Xiang Zhang, Case Western Reserve University)
グラフ上の \(k\)-近傍探索問題を考えます．つまり，ネットワーク \(G=(V,E)\) があり，クエリとして頂点 \(u \in V\) が与えられるので，\(u\) に似た頂点のトップ \(k\) を出力する問題です．
ここでは2つの頂点が似ている指標としてランダムウォークベースの指標 (Hitting time のいくつかの変種や，CIKM’13で提案された Effective importance) を考えます．
この手の研究ではインデックスを最初に構築して，インデックスサイズとクエリ時間のトレードオフを考えるのが普通なのですが，この論文ではインデックスを作成せず，クエリされた頂点 \(u\) を中心に局所探索をしてトップ \(k\) を求めるという手法を取っています．
そのために，これらの類似度の指標には局所的な最大値が存在しないことを証明し，その上で，局所探索の過程で今見ている頂点の類似度の上下界を管理し，見る必要が無くなったところは見ないように枝刈りするということをしているようです．
Reachability Queries on Large Dynamic Graphs: A Total Order Approach
(Andy Diwen Zhu, Nanyang Technological University; Wenqing Lin, Nanyang Technological University; Sibo Wang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University)
到達可能性クエリという問題に関する研究です．これは，有向無閉路ネットワーク \(G=(V,E)\) があり，クエリとして 2 つの頂点 \(u, v\) が与えられるので，\(u\) から \(v\) に向かう有向パスが存在するかどうかを答える問題です．インデックス構築時間・インデックスサイズ・クエリ時間の3つの要素の良いトレードオフを実現するアルゴリズムを考えることが課題です．
既存研究でも到達可能性クエリはよく研究されていて，巨大なグラフを効率よく扱える手法が幾つかあったのですが，静的なネットワークを対象にしたものがほとんどでした．この研究では動的グラフ，つまりリアルタイムでグラフの枝や頂点が削除されうる状況で到達可能性クエリを扱っていました．
で，その手法が結構面白いと思ったのですが，既存の静的グラフ用のいくつかの有力な手法に共通する要素を1つのフレームワークとして抽象化し，そのフレームワーク上で動的グラフ用のアルゴリズムを考案するということをしていました．そして，そのフレームワークに沿った，より効率の良い手法(正確にはラベリング方法？)を提案し，動的グラフで効率よく到達可能性クエリを捌くことができると主張していました．
既存の有力な手法には東大今井研の秋葉さんや矢野くんの手法が含まれています．
複数の既存手法を1つのフレームワークにまとめてしまうというのは結構驚きな気がします．
Independent Range Sampling
(Xiaocheng Hu, Chinese University of Hong Kong; Miao Qiao, Chinese University of Hong Kong; Yufei Tao, Chinese University of Hong Kong)
こちらは PODS の発表です．データ構造の話になります．
考える問題は次のようなものです：1次元上に点の集合 \(P\) があります．クエリとして区間 \([x,y]\) と \(t\ge1\) が与えられるので，点集合 \(P \cap [x, y]\) の中から \(t\) 個の点を一様な確率でランダムサンプリングしたい．
計算モデルとしては RAM モデルを仮定し，できるだけビット並列のようなことをして計算量を減らすのが目的です．
この研究では，いくつかの異なるモデル (点がstaticかdynamicか / 外部メモリ無しか有りか) について割とタイトな計算時間の上下界を得ていました．
基礎的な問題に対して計算時間の改良を与えられているのは面白いなぁと思いました．(ちょっと改善ポイントが細かい？というのはあるかもしれませんが．)
ちなみにこのセッションでは著者の Yufei Tao が他にもう1本論文を通していたようで，2回連続で発表していました．発表がとてもエネルギッシュで聞いていて楽しかったです．
謝辞
今回の SIGMOD 参加はJST/ERATO 河原林巨大グラフプロジェクトよりご支援を頂きました．関係者の方々に深く感謝致します．今後ともよろしくお願い致します．
