久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学

Presentation on theme: "久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 左 右 15

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

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

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

19 メモリの階層構造 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 10 [ms] slow Disk(HDD)

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

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

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

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

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