WWW'14 に論文採択
論文が国際学会 WWW'14 (23rd International World Wide Web Conference) に採択されました！ WWW はその名の通りウェブに関するトップ学会で，比較的新しいものの最近ではかなりの人気を誇る学会だと思います．
WWW の最近の人気は，例えば Microsoft Academic Search の学会ランキングで伺うことができます．最近 5 年に限定すると，なんとコンピュータ科学の全分野合わせても 2 位*1，最近 10 年にしても 3 位ということで，かなり順位が高いです．その分もちろん競争も激しく，採択率は 84/650 = 12.9% だそうです． 所属する河原林グラフ ERATO からもかなりの本数が提出されたようですが，知る限り残ったのは僕の論文だけのようです．
論文タイトルは "Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling" というもので，またもや研究室同期の岩田と NII の吉田さんとの共著になっています．
内容について
論文タイトルからわかるとおり，これまた SIGMOD'13，CIKM'13，ALENEX'14 と出してきた最短路クエリの論文の続きの新編です．今回も対象は大規模なソーシャルネットワークやウェブグラフです．そして，論文タイトルの冒頭になっているとおり，今回は Dynamic と Historical というのが新しい点です．この論文の貢献は主に 2 つあります．
貢献 1: Dynamic Update
今までの最短路クエリではグラフは静的であることを仮定し，グラフの変更を反映するには前計算をしなおす必要がありました．しかし，今回提案する動的更新アルゴリズムを組み込むと，なんとグラフの変更を即座に反映することができるようになります． ちなみに 1 本の枝に対する処理は数ミリ秒で終わります．
ただし，対応しているグラフの変更は今の所残念ながら辺の追加のみです．しかし，現実のネットワークでは辺の追加の方が削除よりも遥かに多いため，実用的にはそれでもかなり価値があるという事を主張しています．今までは再構築をするまで反映されなかった変更が，追加だけとはいえ即座に追加されるのは有用であると思います．
貢献 2: Historical Queries
さらに，データ構造にもう少し情報を入れることにより，最新の状態での距離だけでなく，「昔，時間 t の頃の距離はいくつだったか？」や「距離が変化したのはいつか？」というような質問に答えることができるということを提案しています．
これを使うと，辺に時間の入った大規模なグラフデータにおいて，距離を使った指標がどのように時間経過と共に変化していくかを観察できるようになります．下図はその例です．
(Fig.3 は平均距離と有効直径の変化，Fig.4 は近接中心性の変化，Fig.5 は temporal hop plot です．）
論文採択について
今回の論文も，実は最初に VLDB に投稿して落とされていて，その次で WWW に投稿しました．
この論文に限らず，VLDB では，正直毎回かなり納得の行かない査読コメントと共に落とされています．かなり頭に来たので，今回は DB 分野はもういいかなということで思い切って WWW に投稿するという判断をしました．これは，どうやら正解だったようです．同等の競争率のはずですが，かなり高い評価と共に論文は採択されました．
とはいえもちろん，VLDB に出した原稿をただ WWW に再提出して採択されたわけではなく，かなり念入りに修正をしています．特に，WWW の査読でウケるように，「何ができるか」に重点を起き，上で示した例などを追加しました．また，VLDB で納得してもらえなかった点の議論の防御を強めました．
特に今回は，「更新で削除が対応していない」という点がかなりきつい防御ポイントで，VLDB で落とされたのもその点の影響も大きかったと思います． 「WWW に 5 年で 6 本」で有名な松尾先生も仰っている通り，論文を通すためには失点を少なくすることが重要であり，こういう大きな突っ込まれ得るポイントがあると，例え面白くても「論文を通す」という観点からは結構厳しいです．そのような部分を今回は議論で押し切ることができたというのは少し自信につながり嬉しいです．
*1:1 位は納得の CVPR ですね． その次という順位は結構すごいように思います．このランク付けがどれだけ意味のあるものかという議論の余地は当然ありますが，少なくともこの指標ではこの順位だということに一定の意味はあると思います．
ALENEX'14 に論文採択
国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです．
今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'13 論文から続く最短路クエリの手法 Pruned Landmark Labeling (PLL) のシリーズ 3 作目です（SIGMOD'13, CIKM'13 *1, そして今回 ALENEX'14）．
内容
今回の論文の題材は，道路ネットワークにおける最短路クエリのアルゴリズムです．前回の PFI セミナーの後半で扱っていたトピックです．
SIGMOD で発表した最初の PLL の論文では，対象とするネットワークをソーシャルネットワークやウェブグラフのようないわゆる「複雑ネットワーク」とし，それらのネットワークの特徴を活用していました．道路ネットワークは，それらのネットワークに対し性質が随分異なる（例えば，とても次数の高いハブのような頂点が存在しない）ので，そのままでは道路ネットワークで高い性能を出すことができませんでした．
そこで，この論文では，道路ネットワークに特化した手法として "Pruned Highway Labeling" を提案しています．この手法は，以下の点が新しいと思います．
- まず，データの持ち方が進化しています．詳細は省略しますが，今までは純粋に頂点から頂点への距離を保存していたところを，頂点からパスへの距離をうまく保存するようにすることにより，ネットワークに高速道路のような中心的なパスが存在することを活用できるようにしています．
特徴
この手法は，以下のような点で面白いと思っています．
- 高速道路の活用：複雑ネットワークでは「中心的な頂点（＝ハブ）」を活用していたのに対し，道路ネットワークでは「中心的なパス（＝高速道路）」を活用します．最近の道路ネットワークの手法は，高速道路をそこまで陽に活用できていませんでした．
- Thorup の Distance Oracle との類似性：以前の PFI セミナーで紹介した通り，理論コミュニティで純粋な理論的計算量を勝負している手法と，実際に実装された際の性能を勝負している手法は，今までかけ離れていました．しかし，今回の手法は，パスにより平面を分割しパスへの距離を保存してゆくという点で，理論コミュニティでの有名な平面グラフの最短路クエリ手法と似たアプローチになっています．
また，今回の論文で，ついに「複雑ネットワーク上の最短路クエリ」「DAG 上の到達可能性クエリ」「交通ネットワーク上の最短路クエリ」という大規模グラフ上のクエリの中で最もよく研究されてきたと言える 3 種類のクエリの研究の歴史に PLL の名前を刻むことができました．今まで，かなりバラバラな手法がそれぞれに独立に開発されてきていたのに対し，ある程度統一的な手法でそれぞれで良い性能が出るというのは，今までに無かったことだと思います．
*1:ちなみにこのブログはまさに CIKM へ発表に来ているところで書いています
ICFP Programming Contest 2013 優勝！
WINNER: UNAGI--THE SYNTHESIS
Java, C#, PHP, Ruby and Haskell
are programming tools of choice for discriminating hackers
Takuya Akiba, Yoichi Iwata,
Kentaro Imajo, Toshiki Kataoka,
Naohiro Takahashi, Hiroaki Iwami
University of Tokyo, Google, Keio University and AtCoder
Japan
8 月に開催された ICFP Programming Contest 2013 の結果が ICFP 2013 で本日発表され，我々は念願の優勝をついに果たしました．これは嬉しい！（事前に知っていましたが，例によって発表まで秘密にするように言われていました．）
写真は現地の imos のツイートより拝借．
ICFP Programming Contest について
ICFP Programming Contest は「なんでもあり」が特徴の，他とは一線を画す特徴的なプログラミングコンテストです．ACM の関数型プログラミング言語の学会 ICFP (International Conference on Functional Programming) に伴って毎年開催されていまして (1) プログラミング言語自由 (2) 計算資源自由 (2) チーム人数制限なし (3) 72 時間勝負 (4) 問題の形式も毎年大きく変化，等の特徴があります．優勝者は「その年のプログラミング言語」を決めることとなっており「その年はその言語の文句は言えない」とか．
チームについて
今年は，以下のメンバーで出場しました．（アルファベット順）
- chokudai
- imos
- iwiwi
- sulume
- tos
- wata
チーム名は "Unagi: The Synthesis" です（何故か運営にいつも ":" を "--" に置換される）．一応僕はリーダー的な立場でした（＝呼びかけをしたのと雑用を多くしただけ）．
このチームは，2 年前に準優勝したチーム "Unagi: The Gathering" をベースとしています．その際，優勝者は 301 点だったのに対し準優勝の我々は 300 点でした．準優勝はとても嬉しくはありましたが，一方で 1 点差にとても悔しい思いをしました．
去年は色々あって（主に僕の都合が悪く）一旦チームが崩壊していましたが，そこから，今年出られるメンバーで再集結＆新たなメンバーを勧誘して結成したのが今年のチーム "Unagi: The Synthesis" です．今年も（今年は今まで以上に）勝ちに行くことを強く意識して結成しました．全員が他のプログラミングコンテスト (ICPC, TopCoder 等) のバックグラウンドを色濃く持つ一方で，能力のバランス（アイディア力，アルゴリズム実装力，システム実装力，関数型言語等）を考えながら構成しました．
問題と結果について
今年の問題は，Program Synthesis という研究トピックを題材にした，割と真面目な問題でした．一言で言うと，「向こうが秘密のプログラムを持っていて，入力を渡すと出力を返してくれるので，秘密のプログラムを当てる．どれだけ多くの問題を当てられるか」という問題です．詳細はこちら．
我々のソルバーは，特に特別な道具 (SAT/SMT ソルバー等) には頼らず，基本的に枝刈り探索＋ヒューリスティクスをひたすらチューニングしてきました．色々なバリエーションを作り，それを Amazon EC2 をふんだんに使って分散実行しました．
普段，ICFP Programming Contest はリバースエンジニアリングやショートコーディング等を伴うもっと奇抜な問題が多いのに対し，かなり純粋な問題だったところも，優勝につながった要因だと思います．また，（2 年前からひきずっている）チームの最大の欠点である，メンバーが使える・使いたいプログラミング言語がバラバラというのが余り問題にならなかったのも助かりました．
皆思い思いのプログラミング言語を使ったので，「今年のプログラミング言語」は「Java, C#, PHP, Ruby and Haskell」ということになりました．（多くてちょっとダサいですが，毎年大抵どの言語を指定するかは使った言語にかかわらず指定できるのに対し，今年はアンケートに書いたプログラミング言語がそのまま使われてしまいました．）今年のプログラミング言語たちをよろしくお願いします．
感想など
ICFP Programming Contest に 2 年前から本気で参加するようになったのは，3 年前に尊敬する先輩たちのチーム Pure Pure Code++ が優勝し，とてつもなくかっこ良く感じたというのがあります．この際の先輩方のチームも，ICPC や TopCoder 等で名高い方々で構成されたチームで，そういう方々がそういうコンテストだけでなく色々な要素での総合力勝負でも圧倒したところに憧れ，自分もそうなってみたいと思い真面目に参加するようになりました．憧れの優勝についに手が届き，とても嬉しいです．
もちろん，次の目標は連覇です．今回は比較的問われる能力が純粋だった（総合力勝負性が少し低かった）という点もあり，「また勝つ」ということへのモチベーションは失われていないと思います．簡単なことではないと思いますが，どちらにせよ（順位に関わらず）とても楽しいイベントでもありますので，来年も参加したいと思います．
参加中の風景など
期間中は集まってやってました．
全完した．
全完して解散してたのにボーナス問題のせいで再集結
最後は時間が足りなくなってきたので 4 問同時に見守る．
ちなみに，最終的な得点は 1696 点でした．2 位に 100 点程度差をつけての優勝ということです．
@imos (簡単な問題を)全完した
2013-09-27 12:21:55 via HootSuite to @imos
全完とはこういうことだったらしいです．
平面グラフと交通ネットワークのアルゴリズム
本日，PFI セミナーにて「平面グラフと交通ネットワークのアルゴリズム」というタイトルで話をさせてもらいました．スライドは以下になります．
- 「平面グラフでは色々な問題が効率的に解けると聞くけど一体何故？」
- 「道路ネットワークを処理するにはそういうアルゴリズムが使われているの？」
というような自分が昔持っていた疑問に答える，そんなつもりで準備をしました．そんな疑問を持っている方は，是非ご覧ください．
内容は以下のような感じです．
- 平面グラフのアルゴリズム（理論コミュニティ）
- 平面グラフとは何か
- 平面グラフのアルゴリズムテクニックとその応用例
- 双対グラフ
- 小さいセパレータの存在 (r-division)
- グラフ分割 (Deletion Decomposition)
- 交通ネットワークのアルゴリズム（応用コミュニティ）
- どのような課題が取り組まれているか
- 道路ネットワークは平面グラフなのか？
- 経路計画の手法 4 つ（CH, CRP, HL, PHL）
平面グラフのアルゴリズムの話は，日本語の資料は世の中にほとんど無いと思うので，わりかし珍しい話だとは思います．しかし，時間の制約もあってあまり踏み込んではないので，基礎的なグラフアルゴリズムさえわかっていればそこそこ理解できるような簡単な話になっています．そして，結構それでも（純粋な意味で）面白いと思います．
交通ネットワークの話は，応用寄りの方にも興味を持ってもらえるよう，2 系統の手法の話を 2 つずつしました．前者 2 つは，Bing Maps や OSRM 等で実際に採用されている，拡張性等の面で使いやすい手法です．そして，後者 2 つは，純粋に性能を追い求める手法になっています．
Ustream の録画もあります．
CIKM'13 に論文採択×2
執筆した論文が 2 本同時に国際学会 CIKM'13 (ACM International Conference on Information and Knowledge Management) に採択されました．CIKM は情報検索，データマイニング，データベースの３つの分野が合わさっている大きな会議です．Full paper での採択は競争が厳しく，去年の採択率は 13% だったのですが，今年はちょっと上がって 17% (=143/848) だったようです*1．今回の 2 本の論文は，1 本が Full paper としての採択になりましたが，もう片方は Short paper での採択になりました．
発表は，10 月末にサンフランシスコです．以下，2 本の論文を簡単に紹介します．
Linear-Time Enumeration of Maximal k-Edge-Connected Subgraphs in Large Networks by Random Contraction (Full paper)
研究室同期の岩田と NII の吉田さんとの共同研究です．極大 k 枝連結部分グラフを列挙するアルゴリズムです．言い方を変えると，頂点集合をサイズ k 未満のカットで分割します．
我々のアルゴリズムは，非常にシンプルな乱択アルゴリズムです．基本は，二頂点をランダムに縮約しながら，次数 k 未満の頂点を発見したらその頂点を切除する（元のグラフで対応する辺を除去する），これを何度か繰り返す，というだけです．これは，有名な Karger の最小カットアルゴリズムを，k 未満のカットを発見させることに特化させたものになります．ただ，最小カット問題では，ランダム縮約ベースのアルゴリズムは実用上は他の物より低速で，実際に使われることはありません．ランダム縮約が実際に実装され高い性能を出している点がこの論文の 1 つ面白い点になると思います．
実際には，そのアルゴリズムに，さらに少しのアルゴリズム的工夫と，高速な実装のための工夫をしています．理論的な解析がまた面白くて，まず Karger が行った解析と同様の解析でイテレーション回数を抑えられるのですが，その上で，グラフにちょっとした仮定を入れると，我々が加えたアルゴリズム的工夫が劇的にイテレーション回数を減らすということが証明できます．実験でのみならず，性能向上を理論的にもある程度説明できているのが面白いと思います．
極大 k 枝連結部分グラフは，興味深いことに，k-core というポピュラーな密部分グラフのモデルと深い関係があります．極大 k 枝連結部分グラフへの分割は，常に k-core への分割の細分になっています．k-core は多くの応用を持つため，極大 k 枝連結部分グラフの列挙も応用があると期待できます．
Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths (Short paper)
研究室の後輩の矢野君（主著者）と研究室同期の岩田と NII の吉田さんとの共同研究です．ついこの前に発表してきた SIGMOD'13 の最短路クエリの論文の続きで，SIGMOD'13 のエントリで最後に言及した後続研究の 1 つです．
到達可能性クエリは，与えられた有向グラフを前処理しておき，「2 点の間に有向パスがあるか否か」という質問に高速に答えるという問題です．最短路クエリ問題に含まれる問題ではありますが，ターゲットとするグラフの性質が異なることから，性能を出すことまで考えると自明な応用とは言い切れないものです．この論文ではまず，SIGMOD'13 論文の最短路クエリ手法 Pruned Landmark Labeling (PLL) について，到達可能性クエリのアルゴリズムとして性能を出すための少しの変更を議論しています．
さらに，到達可能性クエリでは最短路クエリと異なり距離を答えなくて良いという点を活用した，PLL の拡張である Pruned Path Labeling (PPL) という新しい手法を提案しています．基本的なアイディアとしては，「1 本のパスを決めたとして，各点 v から『パスのできるだけ上の頂点でどれに v から到達できるか』『パスのできるだけ下の頂点でどれからなら v に到達できるか』を知っておけば，そのパスを通るパスを持つ二点対については全て到達可能性が答えられるようになる」というものです．PLL ではラベルを付ける相手が頂点だったのに対し，PPL ではそれをパスに一般化しているということです．
こちらも，理論的解析も面白いです．SIGMOD 論文同様，PLL も PPL も木幅が制限されたグラフでの効率性は証明できます．しかし，PPL に限っては，さらに H-minor-free のグラフでの効率性も証明することができます．H-minor-freeness は木幅の制限より一般的な制限と言えるので，PPL は理論的にも PLL を改善しているということが言えます．
*1:ただ，分野によって競争の激しさが結構違うかもしれません．
TopCoder Open 2013 オンサイト決勝進出
上位 12 人が通過の Round 3A で 5 位を獲得し，TopCoder Open 2013 のアルゴリズム部門のオンサイト決勝進出を決めました．決勝は 11 月に Washington DC で開催されます．
TopCoder Open (TCO) のオンサイト決勝は最も好きなプログラミングコンテストのイベントで，今年も行きたいなあととても強く思っていたので，通過できて本当に嬉しいです．今まで他にも Google Code Jam，ACM-ICPC，Facebook Hacker Cup，VKCup 等様々なコンテストで世界大会に出場してきましたが，TCO は特別だと思います．他のコンテストは大抵期間も短くトンボ帰りでその間は拘束されているのに対し，期間が数日間あり，色々なトラックがあり他のトラックを楽しく観戦できる工夫がされていますし，拘束されないので自由に観光に行ったり海やプールで遊んだりもよくしていて，毎回とても楽しく期間を過ごしています．あと，貰えるグッズの数がとても多いのも嬉しいです．例えば去年は T シャツを 6 枚もらったりメカニカルキーボードを貰ったりしました．
マラソン部門では既に 3 人もの日本人参加者が決勝進出を決めていますし，今回 id:ir5 も 2 位で通過しています．アドミンの rng_58 も居ますし，今年も日本人いっぱい居て楽しそうです．まだマラソンもアルゴリズムももう 1 ラウンドずつ残っているので，もっと通過するといいですね．（特に，近年はマラソン通過者の割合が高く，マラソンの日に話し相手がどっと減って寂しいので，アルゴリズム部門でももっと抜けて欲しいです．）
今回で TCO は 2008, 2009, 2011, 2012 に続き 5 回目のオンサイト決勝進出になります．アルゴリズム部門はどうしても問題の運やちょっとしたミスが大きく響くので，なかなか安定して通過するのは難しいと言われており，例えば，ターゲット (レーティング≧3000）ですら毎回半分ぐらいは落ちている気がします．現に今回も，上のスクリーンショットの通り，Petr も ACRush も通過に失敗しています．そんな中で 6 年で 5 回通過しているというのは，実力の割に（といっても TopCoder に関しては最近は身に余るレーティングが付いていてわかりにくいですが……）よく通過しているなあと我ながら感じます．
そこで，僭越ながら自分なりに思う TCO オンサイト進出のコツを書かせてもらうと，TCO オンサイト進出のためには，難しい問題を焦らずじっくり確実に通すことが重要です．過去数年のオンライン最終ラウンドを見ても，そして今回を見ても，2 問通した人は殆ど通過しています．オンライン最終ラウンドは普段の SRM より難易度が高くしかも（なぜか）落としやすい問題が出題されます．さらに，どうしても通過圏内に入りたいという気持ちで攻める人や焦る人がとても多く，結果としてかなりの提出が落ちます．今回も，コーディングフェーズ終了直後の僕の順位は確か 30 位ぐらいでしたが，撃墜での得点なしに，システムテスト後最終的に 5 位になりました．他の人の高い得点の提出に惑わされず，焦らないで確信が持てる解法を選び，きちんと見直しやテストを行って 2 問出せれば，通る確率は高いです．（ただ，2 問解いただけでは通過できない回というのもたまにはあるので，そうなっても僕に文句は言わないでください……）
最近は，昔のような長い時間をプログラミングコンテストに割く生活からは遠く離れていて，「引退」や「世代交代」という言葉もしばしば脳裏をよぎります．実際にもうコンテストをやらなくなった同輩も居ますし，スピードを要するコンテストでは日々問題を解いている若い人たちになかなか思うように勝てなくなってきているのも事実です．しかし，こういう高い難易度での勝負であればまだ戦えるのだというのは，ちょっと嬉しく思います．今や，プログラミングコンテストは趣味の範囲で楽しくやっていければそれで良いと思ってはいますが，とはいえやはり勝つことは大きな喜びです．オンサイトでは今度こそトップ 3 入賞を狙いたいと思います．
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 本走っています．今後も乞うご期待．
