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
11
Hub Labeling による高速経路探索
NearMeの技術発表資料です
PRO
June 06, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
Build an AI agent with Mastra
nearme_tech
PRO
0
22
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
16
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
57
AIエージェント for 予約フォーム
nearme_tech
PRO
2
120
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
45
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
19
GitHub Custom Actionのレシピ
nearme_tech
PRO
0
14
RustでDeepQNetworkを実装する
nearme_tech
PRO
1
20
より良い解に辿り着くカギ-近傍設定の重要性
nearme_tech
PRO
0
96
Featured
See All Featured
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
123
52k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Gamification - CAS2011
davidbonilla
81
5.3k
Mobile First: as difficult as doing things right
swwweet
223
9.6k
YesSQL, Process and Tooling at Scale
rocio
172
14k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
The Power of CSS Pseudo Elements
geoffreycrofte
76
5.8k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
45
9.6k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
15
890
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Unsuck your backbone
ammeep
671
58k
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