平面グラフと交通ネットワークのアルゴリズム
本日，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 本走っています．今後も乞うご期待．
TopCoder Open 2013 Round 3 進出 ＆ レーティング世界 4 位
昨夜の TopCoder Open 2013 Round 2A で 13 位を取り，Round 3 に進出しました．Round 3 には 2 回のサブラウンドがあり，どちらかで 12 位以上を獲得すれば世界大会進出です．
レーティングは 3297 に上昇． meret, tomek, Brunduk1 を一気に追いぬき，世界 4 位になりました． 自分の上には，現在，tourist, Petr, ACRush という人間卒業勢しか居ません（そして残念ながら彼らとは大差です）．
修士課程修了 ＆ 研究科長賞獲得
無事に修士課程を修了することができ，本日学位記を受け取りました．また，一緒に，情報理工学系研究科の研究科長賞を頂きました．
学位記授与式
学部の卒業式に相当する学位記授与式は，安田講堂が改修中のため，有明コロシアムで開催されました．僕らの学年は，東北地方太平洋沖地震の影響で学部の卒業式も中止になっておりまして，2 度も例外的措置を体験したことになります．
