道路ネットワーク上の経路探索クエリのための枝刈りツリーラベリングアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2016-09-16
• タイトル: 道路ネットワーク上の経路探索クエリのための枝刈りツリーラベリングアルゴリズム
• タイトル / 言語: en
• タイトル: Pruned Tree Labeling Algorithms for Shortest Path Queries in Road Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科応用情報科学専攻
• 著者所属: 東京大学大学院情報理工学系研究科数理情報学専攻
• 著者名: 小池, 敦; 定兼, 邦彦
• 著者名(英): Atsushi, Koike; Kunihiko, Sadakane
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，道路ネットワーク上の経路探索クエリについて，新しいアルゴリズムを提案する．提案手法は Hub Labeling や Pruned Highway Labeling と同様，ラベリング法に基づくものである．前処理において，入力グラフを複数の木に分解し，各ノードが hub ノード集合の代わりに木の ID の集合を保持することでラベルサイズを削減させる．本論文ではアルゴリズムを実装し，米国の道路ネットワークを用いて評価を行うことで，提案アルゴリズムの有効性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a new algorithm for shortest path queries in road networks. The algorithm utilizes a labeling method in common with Hub Labeling and Pruned Highway Labeling. At the preprocessing phase, an input graph is decomposed into trees and each node in the graph stores some tree IDs instead of node IDs in Hub Labeling, which reduces the size of precomputed data. In this paper, we implement the algorithm and evaluate it using a US road network.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-159, 号 7, p. 1-8, 発行日 2016-09-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会