SIGMOD'13 に論文採択

論文が国際学会 SIGMOD'13 (ACM SIGMOD International Conference on Management of Data) に採択されました．SIGMOD はデータベース分野のトップ会議です．日本からの論文は知る限り 5 年ぶりだと思います．修士の間の研究で，この厳しい戦いを勝ち抜き論文採択に至ることができ，本当に嬉しいです．

論文は "Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで，研究室同期の岩田と NII の吉田さんとの共同研究です．

内容について

扱っている問題は前回の EDBT 論文と同じく，大規模ネットワーク上の最短路クエリです．グラフに対し，ある程度の前計算データを蓄えておく事により，2 点間の最短路を瞬時に答えます．最短路クエリの手法は DB 界隈等でよく研究されており，厳密手法（一切の誤差を許さない）だけでも去年に 3 本論文が出ています．

今回の論文も，最短路クエリの新しい厳密手法のアルゴリズムを提案しています．大幅な性能向上に成功し，既存手法に比べ 100 倍大規模なネットワークを同じような前処理時間・クエリ時間で扱うことができます．数億辺のネットワークを，数時間で前処理し，2 点間の距離を数マイクロ秒で答えることができます．

しかし，ベースになっているアイディアは実は非常にシンプルで，前処理は枝狩りつき BFS を全頂点から行うだけであり，クエリ処理では merge-join のようなことをするだけです．前処理のアルゴリズムは，枝刈りのために作り中のデータ構造に自らクエリを発行するという面白いアルゴリズムになっています．前処理アルゴリズムは 100 行ぐらい，クエリ処理アルゴリズムは 10 行ぐらいで実装できます．ただし，重み無しの場合，前処理・クエリ共にビット並列のテクニックを適用することができ，それにより更に高速化することもできます．

興味深いことに，提案手法は，現実世界のネットワークの性質を自動的に活用します．例えば，非常に中心的な頂点 (ハブ) が存在するということや，次数の低い頂点たちは外側で木のような形状の fringe を構成しているということです．前者はランドマークを用いる既存手法たち，後者は木分解を用いる既存手法たちが活用してきた性質であり，提案手法はその両方を活用しているということが高い性能を裏付けているのだと思います．これらは，直感的な説明のみならず，定理としてある程度証明しています．

共著者について

2 人とも，研究室配属されたり研究を始めたりする遥か前，B1 の頃から知る友人・先輩です．そして，自分を含め，全員，プログラミングコンテストのかなりの元ガチ勢です（例えば 3 人とも ICPC の世界大会出場者）．

岩田は，僕と一緒にコンテストをやりまくり，そのままコンテスト好きをこじらせて同じアルゴリズム研究の研究室に入った同期です．プログラミングコンテストチャレンジブックを一緒に書いた相手でもあります．彼はかなりのアイディアマンだと思います．彼の一言はしばしば本当に貴重な一言で，その一言から研究が始まるということは少なくなく，この件も例外ではありません．

吉田さんは，僕が B1 でコンテストをやり始めた頃に日本で最も強い ICPC のチームを率いていた先輩です．アジア地区大会で日本からのチームとして初めて優勝したのも吉田さんのチームです．その後，STOC（理論系アルゴリズムのトップ学会）に学生のうちから論文を通していたりと，研究の世界でも活躍しており，最も尊敬している先輩の一人です．コンテストでも研究でも多くのことを教えてもらい，今回もベテランとしてのアドバイスも多く頂きました．

本当に素晴らしい共著者に恵まれたと思っています．彼らが居なければこの論文は確実に存在し得なかったと思います．そればかりか，二人とも研究のみならず自分に大きな影響を与え続けてきた人たちであり，そんな彼らと一緒にこのような良い研究ができたというのはとても嬉しく思います．

また，共著者のみならず，感謝したい人は数えきれない程に多いです．挙げていきますときりがないので，個別にお礼が言えればと思っております．

論文採択について

B4 で研究室配属されて以来，SIGMOD は自分の 1 つの目標でした．STOC・FOCS を頂点とするようないわゆる「アルゴリズム」の研究コミュニティの関心は理論的すぎて自分にはあまり合わないということに気づいた頃，大規模なネットワークに対するグラフアルゴリズムの論文を SIGMOD で発見し，それ以来ずっとこのような実用的なグラフアルゴリズムというテーマでやってきていました．

最近はトップ会議を狙うばかりに去年度は論文が 1 本も通らずでしたが，ついに良いところに論文が通ってホッとしています．この論文はこれが一発目ですぐ通りましたが，他は，VLDB に落とされたり，SIGMOD も実は 2 本送っていましたがこの 1 本だけが採択になりました．トップ会議に論文を通すということがどれだけ難しいことか，というのを強く実感しています．この論文も，既存手法に圧倒的な性能差を示していながら，査読者のコメントはかなり厳しかったです．それでも，建設的な査読者が多く，運も味方して採択に至ったと思います．

一発屋として終わらないためにも，今後も続けて頑張っていきたいと思います．実は既に，この研究をベースとした研究が研究室で 3 本走っています．今後も乞うご期待．