EDBT'12 に論文採択

卒論とその続きで昨年夏学期にやっていた研究に関する論文が EDBT'12 (15th International Conference on Extending Database Technology) に採択されました.会議は 3 月末にドイツです.

論文は "Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core" というタイトルで, MIT の Christian Sommer さんと NII の河原林先生との共著になっています.

Christian Sommer さんは,MIT でグラフの最短路に関連するトピックをひたすらやられているアルゴリズム系の人です. セオリーからプラクティスまで,幅広い知識と経験を持っていて,今回も様々なアイディアやアドバイスを頂きました.

河原林先生は,アルゴリズム系の人なら知らない人は居ない,今世界で最も勢いのあるセオリー系の先生の一人です.(例えば,トップカンファレンスを見ると河原林先生が入っている論文が 3, 4 本あるのが普通.)

内容は,グラフ上の最短路クエリのアルゴリズムとデータ構造です.最短路クエリとは,前計算(DB 系の人にはインデクシングと言うとわかりやすいらしい)をしておくことで,グラフ上の 2 点間の最短距離に関するクエリに高速に答える,というジャンルです.

まず,セオリーの話から始まり,木幅の小さいグラフにおいて新たなトレードオフを実現する手法を 2 つ提案しています.次に,そういった手法を,ソーシャルネットワークや Web グラフなどの複雑ネットワークに応用します.そういったネットワークには Core-Fringe 構造という性質が知られており,全体としては木幅が小さいわけでないものの,Fringe 部分を木幅が小さいとみなし木分解を適用します.そこからさらに手法が 2 つあって,既存の厳密手法のスケーラビリティを改善した手法と,さらにそれを応用し既存の近似手法と組み合わせ空間性能を改善する手法を提案しています.

データベース系は層が厚くて,EDBT は SIGMOD, VLDB, ICDE 等に次ぐ準トップカンファレンスかと思いますが,それでも受理率は 22.5% ということで,それなりの競争があったようです.それなりの競争がある会議への論文投稿は初めてで,受理されて本当に良かったです.

昔のプログラム等を見ると日本の方の気配をあまり感じないのですが,今年は @maropu 先生も行かれるという話で,ドイツでは孤独でなさそうで良かったです.楽しみ.