久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学 最短路プロジェクト 共同研究 報告 2008年 2月 久保幹雄　東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学

プロジェクト概要 Hi! L1 L2 RAM HD,Flash クエリ高速化 前処理による 対話型のための モデルの拡張 ﾒﾓﾘ階層による高速化 Hi!

本年度の成果 メモリ階層の考慮による高速化 実装＋実験 前処理による高速化： 階層メッシュ疎化法：特許，実装，数値実験，論文投稿 2次元ビットベクトル法：アルゴリズムを改良，実装 経由点通過法：実装，改善，実装，予備実験 様々なモデルの拡張に対する検討 時刻依存 確率的 動的 高速道路の時間帯別料金の考慮

前処理とクエリの分離（１） ２０００万点の 最短路 ネットワーク ダイクストラ法１回 （数十秒） 旧来の方式 注：我が国のナビの最短路は最適でないヒューリスティクス

前処理とクエリの分離（２） 前処理（preprocessing） ２０００万点の ネットワーク 補助データ ダイクストラ法たくさん （数時間；並列で数分） クエリ（query） 補助データ 最短路 ２０００万点の ネットワーク 高速探索 （数ミリ秒）

前処理による高速化（１） ２次元ビットベクトル法 階層メッシュ疎化法 最初に開発したアルゴリズム メモリアクセス小 前処理が遅い アルゴリズムの改良＋実装（報告書に添付） 階層メッシュ疎化法 汎用の高速化法（他の解法と融合可） （国際）特許申請 実装（報告書に添付） 実験＋論文投稿 6

前処理による高速化（２） 経由点通過法（transit node routing） Bast-Funke-Sanders-Schultesが開発 最速のクエリ時間 Scientific American SciAM 50 awards受賞 （EUのグループなので）特許申請しない方針 =>自由に使える！ 実装（報告書に添付） アルゴリズムの改善 未発表論文のバグの修正 「前処理の前処理」による高速化 並列による高速化（2CPUで1.8倍，4CPUで3.1倍） 7

経由点通過法のアイディア アクセス点

経由点の集合 （すべてのセルからのアクセス点） Washington DC　9559点 =>経由点150程度抽出

経由点グラフ 総点数nに対して√nの点数から成るグラフ =>全点間の最短路を事前に計算

経由点通過法の最短路クエリ min [ 始点sからアクセス点A(s)への最短距離+ アクセス点 A(s)からアクセス点A(t)への最短距離+ アクセス点 A(t)から終点tへの最短距離 ] 経由点間の最短距離行列 t s

経由点の高速計算 +2 +1 -1 -2 アクセス点 Sweep line（赤）を またぐ端点への 最短路を解き， 左から右への最短路 -1 -2 アクセス点 Sweep line（赤）を またぐ端点への 最短路を解き， 左から右への最短路 上の点のみ残す この操作をすべての Sweep line（縦，横） に対して行う 左 右 Sweep line 12

計算例 左の点集合と右の点集合 の間の最短路上の点が 経由点

経由点 にならなかった点 セルを細かい 順に計算し， 候補を限定する 左 右 14

左 右 15

予備実験によると，計算時間が1割から5割程度の減少 右 左 予備実験によると，計算時間が1割から5割程度の減少 16

前処理の前処理（2-coreの計算） 次数（点に接続する枝数） が0，1の点の除去 次数 2 の点の短絡除去 9559点から7048点に縮小

2core（New York）の例 264346点 365050枝 次数ヒストグラム 143945点 240687枝 [0, 41169, 40354, 124535, 56998, 1124, 157, 8, 1] 143945点 240687枝 次数ヒストグラム [0, 0, 0, 95607, 47282, 917, 134, 4, 1] 予備実験によると，計算時間が2割から8割程度の減少

メモリの階層構造 Intel Core 2 : E6600 2.4GHz の例 L1 キャッシュ： x 4 1 [ns] x 100 m : 10-3 n : 10-9 p : 10-12 fast レジスタ アクセスコストの例 250[ps] L1 キャッシュ： 命令 32KB, データ 32KB x 4 TLB addr 1 [ns] L2 キャッシュ: 4MB x 100 100 [ns] RAM x 100000 10 [ms] slow Disk(HDD)

始点と終点、それに現在の位置から次に訪れるメッシュを先読みして、メモリから L2 キャッシュに移動してブロッキングする

構造体か配列か？ メモリアクセスのオーバヘッドの減少 ＆ハードウェアプリフェッチの効果

モデルの拡張に対する検討 ＝＞アルゴリズムは完成，未実装 課題：前処理による高速化とどのように合わせるのか？ 22 時刻依存の移動時間をもつ最短路 不確実性をもつ移動時間をもつ最短路 多目的を有する最短路 制約付き最短路 ＝＞アルゴリズムは完成，未実装 　課題：前処理による高速化とどのように合わせるのか？ 22

領域分割による前処理 New Yorkの15分割 領域の縁の点 まどの最短路 　　　　＋ 縁の点間の最短路 　　　　＝ 経由点通過法と 同様の高速化

分割の方法 施設配置問題へのアプローチ（点の座標情報を利用し，重心に施設を配置することによるクラスタリング） k-means法，Weiszfeld法（2000万点だと遅い） グラフ分割問題へのアプローチ（異なる領域間に跨る枝数（カット）を最小にするようにグラフをk-分割） METISソルバー；早い（？）けど，飛び地ができる． =>座標とグラフ情報を利用した大規模問題に対する新解法