Blog
はじめまして。7/1 に入社しました新入社員の秋葉です。参加していた SIGMOD Programming Contest 2016 の結果が先週末にアナウンスされ、アドバイザーとして参加していたチームが優勝となりました。コンテストと我々のアプローチを簡単にご紹介したいと思います。
SIGMOD Programming Contest とは？
SIGMOD Programming Contest は学会 SIGMOD の併設プログラミングコンテストです。SIGMOD は VLDB と並ぶデータベース分野の最も有名な ACM 系の国際学会です。コンテストの題材も学会のテーマに沿っており、大規模データの処理の高速化を競うものが殆どです。特に、近年に論文が複数出ているようなホットなトピックが選ばれるようです。
ちなみに、参加者は学生に限定されています。チームの人数に制限はありません。チームは教員を一人アドバイザーにすることができます。前職では国立情報学研究所の特任助教でしたので、学生時代の出身研究室の後輩同輩である生田くん、林くん、矢野くん、岩田さんのチームにアドバイザーとして参加しました。特に、実装は生田くんと林くんが全て頑張ってくれました。
100 チーム以上が参加し、5 チームがファイナリストとして選出され、サンフランシスコで開催されていた SIGMOD 2016 にて結果がアナウンスされました。
今年のコンテストの問題は？
今年のコンテストの問題は、動的グラフ上のいわゆる最短経路クエリ（より正確には距離クエリ）です。入力として、まず最初に大規模なグラフが与えられます。少し前処理の時間ももらえます。次に、以下の 2 種類のクエリが与えられます。
* 距離の質問：2 頂点が指定されるので、その間の距離を答える
* グラフの変更：辺の追加や削除が指定される
細かいルールは省きましたが概ねこれだけです。とてもシンプルな問題です。グラフは小さいものから大きい物まであり、大きいものは数百万頂点・数千万辺の規模でした。
問題の難しさ
一部の方はご存知の通り、実は最短経路クエリに対する索引付け手法は僕のこれまでの専門のど真ん中でした。「ズルい！」という声すら聞こえてきそうです。それでは、果たして本当に簡単に優勝できたのでしょうか？
残念ながら、枝刈りラベリング法などの僕らが作ってきたこれまでの手法は、実は今回はほぼ全く使う事ができませんでした。その理由は、過酷な問題設定にあります。今回の問題設定では、グラフが動的であり、しかも更新の頻度が高すぎるため、ガッツリとした索引データ構造を作ってしまうと、構築・更新のコストのせいで逆に損をしてしまう状況でした。しかも、実はグラフがソーシャルグラフだったり交通グラフだったりと性質もバラバラでした。
他チームのアプローチ
先に他のチームのアプローチから紹介します。予想通り、過酷すぎる問題設定故に、索引データ構造を保持するようなアルゴリズム的に興味深い手法を採用しているチームは無かったようです。枝刈りやキャッシュヒット率向上のためのちょっとした処理をグラフに加えるぐらいで、基本的には両側幅優先探索をひたすら高速化していたようです。
我々のチームのアプローチ
我々も両側幅優先探索の効率化に尽力しました。しかし、我々のチームは他のチームと異なり、今回の問題設定に適した軽量の索引データ構造を組み込み利用しました。ここが一番面白いかと思うので、この点について重点的に紹介します。
利用した手法は k-All-Path Cover (k-APC) です。k-APC は VLDB’14 で発表されベストペーパー賞を受賞しています。これを使うと、オーバーレイグラフと呼ばれる、元のグラフを「荒くした」グラフのようなものを作ることができます。遠い頂点対の処理をする際、始点終点の近くは元のグラフを探索し、それ以外の大部分はオーバーレイグラフの上だけを探索する、というようにすることができ、処理する頂点数・枝数を減らすことができます。
実際には VLDB’14 で発表された k-APC をそのまま今回の問題設定に使うことはできませんでした。しかし、我々は実はちょうど k-APC の後続研究をしており、その技術をそのまま利用することができました。（ちなみにこの研究は論文投稿中です。）
ただし、k-APC は交通グラフのような平均距離の長いグラフでは効果があるものの、ソーシャルグラフのようなグラフでは効果がありませんでした。そこで、最初にグラフの性質を判定し、k-APC を利用するか否かの判断をするようにしました。
感想など
実は、SIGMOD Programming Contest では、2 年前にもグラフ解析の高速化がテーマとなっています。その時にも今回に近いメンバーで参戦したのですが、残念ながら勝つことができませんでした。今回はアルゴリズム的にも面白いアプローチで奇策が功を奏し勝つことができて本当に良かったです。頑張ってくれたメンバー達に心からお礼を言いたいです。
記事の写真は全て筑波大学の塩川先生よりご提供頂きました。ありがとうございます。
Tag
