Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Hub Labeling による高速経路探索

Hub Labeling による高速経路探索

More Decks by NearMeの技術発表資料です

Transcript

  1. 2. Hub Labeling の概要と利点 • Hub Labeling とは? →最短経路クエリを⾼速に処理するための事前計算ベースの  アルゴリズム

    - 各頂点に対して、「ラベル」という情報を保持 - ラベルには、ある共通の「中継点(hub)」とその距離を記録 - クエリ時は、出発点と到着点のラベルを⽐較し、共通の hub を通 る経路の中で最短のものを選ぶ
  2. 2. Hub Labeling の概要と利点 • Hub Labeling の利点 - クエリ時間が⾮常に短い

    - ハブ情報に経路中継情報を持たせると、経路を復元できる - 道路ネットワークのような疎なグラフが得意 • Hub Labeling の⽋点 - 前処理が重い - 動的グラフへの適⽤が困難
  3. 3. Hub Labeling の仕組み A B C D E F

    G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
  4. 3. Hub Labeling の仕組み A B C D E F

    G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
  5. 3. Hub Labeling の仕組み A B C D E F

    G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
  6. 3. Hub Labeling の仕組み • Hub 数は性能に直結! - 各ノードのラベルに含まれるハブ数が少ないほど、クエリは⾼速 -

    上⼿く設計すれば、数千万ノードでもノードあたりの平均ハブ数 は数⼗程度に • 上⼿く設計するには? - Contraction Hierarchies - Pruned Highway Labeling
  7. 4. 実装と⽐較 • データ - 東京駅を中⼼とした、⼀辺が 10 km の正⽅形内の道路情報 -

    道路を無向辺、交差点を頂点 - 頂点数が 27247 、辺の数が 73624 • ⽐較⽅法 - ランダムな頂点対 1000 組の最短距離を取得 これくらい→
  8. 参考⽂献 • Route Planning in Transportation Networks ◦ https://arxiv.org/pdf/1504.05140 •

    A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks ◦ https://www.microsoft.com/en-us/research/wp-content/ uploads/2010/12/HL-TR.pdf