Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Hub Labeling による高速経路探索
Search
NearMeの技術発表資料です
PRO
June 06, 2025
0
51
Hub Labeling による高速経路探索
NearMeの技術発表資料です
PRO
June 06, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
12
Build an AI agent with Mastra
nearme_tech
PRO
0
67
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
26
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
69
AIエージェント for 予約フォーム
nearme_tech
PRO
2
140
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
48
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
22
GitHub Custom Actionのレシピ
nearme_tech
PRO
0
16
RustでDeepQNetworkを実装する
nearme_tech
PRO
1
23
Featured
See All Featured
Navigating Team Friction
lara
187
15k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.8k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Unsuck your backbone
ammeep
671
58k
Stop Working from a Prison Cell
hatefulcrawdad
270
20k
[RailsConf 2023] Rails as a piece of cake
palkan
55
5.6k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.5k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Fireside Chat
paigeccino
37
3.5k
Intergalactic Javascript Robots from Outer Space
tanoku
271
27k
The Art of Programming - Codeland 2020
erikaheidi
54
13k
Transcript
Hub Labeling による⾼速経路探索 2025-06-06 第123回NearMe技術勉強会 Shunma Serizawa
⽬次 1. 最短経路問題とは? 2. Hub Labeling の概要と利点 3. Hub Labeling
の仕組み 4. 実装と⽐較
1. 最短経路問題とは? • 最短経路問題とは? →ある場所から、他のある場所へ⾏くとき、最も移動距離 (時間) の 短いものを⾒つける • 有名なアルゴリズム
- ベルマンフォード法 - ダイクストラ法
2. Hub Labeling の概要と利点 • Hub Labeling とは? →最短経路クエリを⾼速に処理するための事前計算ベースの アルゴリズム
- 各頂点に対して、「ラベル」という情報を保持 - ラベルには、ある共通の「中継点(hub)」とその距離を記録 - クエリ時は、出発点と到着点のラベルを⽐較し、共通の hub を通 る経路の中で最短のものを選ぶ
2. Hub Labeling の概要と利点 • Hub Labeling の利点 - クエリ時間が⾮常に短い
- ハブ情報に経路中継情報を持たせると、経路を復元できる - 道路ネットワークのような疎なグラフが得意 • Hub Labeling の⽋点 - 前処理が重い - 動的グラフへの適⽤が困難
3. Hub Labeling の仕組み A B C D E F
G 1 2 2 3 2 2 1 3 2
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)
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)
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)
3. Hub Labeling の仕組み • Hub 数は性能に直結! - 各ノードのラベルに含まれるハブ数が少ないほど、クエリは⾼速 -
上⼿く設計すれば、数千万ノードでもノードあたりの平均ハブ数 は数⼗程度に • 上⼿く設計するには? - Contraction Hierarchies - Pruned Highway Labeling
4. 実装と⽐較 • データ - 東京駅を中⼼とした、⼀辺が 10 km の正⽅形内の道路情報 -
道路を無向辺、交差点を頂点 - 頂点数が 27247 、辺の数が 73624 • ⽐較⽅法 - ランダムな頂点対 1000 組の最短距離を取得 これくらい→
4. 実装と⽐較 前計算 クエリ Dijkstra - 50 ms Hub Labeling
3 時間くらい 0.5 ms
参考⽂献 • 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
Thank you