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" を提案しています.この手法は,以下の点が新しいと思います.

  • まず,データの持ち方が進化しています.詳細は省略しますが,今までは純粋に頂点から頂点への距離を保存していたところを,頂点からパスへの距離をうまく保存するようにすることにより,ネットワークに高速道路のような中心的なパスが存在することを活用できるようにしています.
  • ラベルが頂点ベースからパスベースのものとなっていますが,枝刈り Dijkstraアルゴリズムをパス全体から一気に走らせるアルゴリズムにより,パス 1 本分のラベルを一気に効率的に計算できます.


特徴

この手法は,以下のような点で面白いと思っています.

  • 高速道路の活用:複雑ネットワークでは「中心的な頂点(=ハブ)」を活用していたのに対し,道路ネットワークでは「中心的なパス(=高速道路)」を活用します.最近の道路ネットワークの手法は,高速道路をそこまで陽に活用できていませんでした.
  • Thorup の Distance Oracle との類似性以前の PFI セミナーで紹介した通り,理論コミュニティで純粋な理論的計算量を勝負している手法と,実際に実装された際の性能を勝負している手法は,今までかけ離れていました.しかし,今回の手法は,パスにより平面を分割しパスへの距離を保存してゆくという点で,理論コミュニティでの有名な平面グラフの最短路クエリ手法と似たアプローチになっています.

また,今回の論文で,ついに「複雑ネットワーク上の最短路クエリ」「DAG 上の到達可能性クエリ」「交通ネットワーク上の最短路クエリ」という大規模グラフ上のクエリの中で最もよく研究されてきたと言える 3 種類のクエリの研究の歴史に PLL の名前を刻むことができました.今まで,かなりバラバラな手法がそれぞれに独立に開発されてきていたのに対し,ある程度統一的な手法でそれぞれで良い性能が出るというのは,今までに無かったことだと思います.

*1:ちなみにこのブログはまさに CIKM へ発表に来ているところで書いています