@article{oai:kansai-u.repo.nii.ac.jp:00011061,
 author = {蒲原, 智也 and 上島, 紳一},
 issue = {2},
 journal = {情報処理学会論文誌：データベース},
 month = {Jun},
 note = {本稿では,道路網をエッジ重み付きグラフととらえ,ネットワークボロノイ図を用いてグラフを分割し,構成した空間索引木とそれを用いた最短経路探査法を提案する.空間索引木の生成にはまず,道路網を表すグラフに対して,ネットワークボロノイ分割を行うことで,全体領域を部分領域に分割する.この分割によって得られた部分領域ごとに,経路探査のための前処理を実行して空間索引を求めておくことによって,経路探査の計算コストを大幅に減らすことができる.各部分領域は,領域内・隣接領域間の最短経路,領域の大きさの指標などの 3種類の空間索引を持つ.さらに,部分領域をランダムに選択して隣接領域単位で統合することによって,より広い部分領域を得る.この操作を繰り返すことによって領域の包含関係を持ち,平衡木の性質を持つ空間索引木を漸次的に生成する.次に,提案木構造を用いて,領域の統合を用いた再帰的な経路探査アルゴリズムと領域の大きさの指標を用いた経路探査アルゴリズムを与え,その有効性について議論する.提案手法の有効性を確認するため,国土地理院数値地図の道路網データに実際に適用する.まず空間索引木の生成時の評価として,母点の選択確率の木構造への影響,生成時間・サイズなどについて調べる.次に経路探査時の評価として,2つの提案アルゴリズムの定量的な評価を A*探査アルゴリズムと関連研究の階層型経路ビューモデルと比較しながら行う.提案手法により,ディジタル道路情報を利用して,空間索引木を構成でき,2点間の経路探査やエッジに沿った距離に基づく範囲問合せなどの時間を圧縮できる.
\nIn this paper the authors propose a new spatial index tree and discuss its application to shortest path problems. In view of road maps as graphs with edge costs, a given graph is partitioned by use of Network Voronoi Diagram, to generate subregions of the target space. Preprocessing spatial indices in each subregion, computation cost in shortest path search is largely reduced by use of the indices. Spatial indices are (1) shortest paths in each subregion,(2) shortest paths between adjacent subregions, and (3) the maximum/minimum path lengths of each subregion. Furthermore, wider subregions are generated by integration of those adjacent subregions that are randomly selected. By repeating partitionings and integrations, spatial index tree is successively generated in a bottom-up fashion. The tree is a balanced tree that has inclusion relations among subregions, in the sense that higher-level nodes cover the regions of lower-level nodes. Then, two shortest path search algorithms are proposed by use of the spatial index tree. One is a reflexive search algorithm using subregions integration, and the other is a search algorithm based on distance estimation using spatial indices. In order to verify efficiency of the proposed approach, numerical simulations are provided for digital road map data issued from Geographical Survey Institute. One is for investigation of (1) effects of probability in random selection of generators on the structure of spatial index tree, (2) generation costs and file size for the spatial index tree, and the other is for evaluation of search time costs of two proposed shortest path search algorithms, in comparison with A* search algorithm and the existent hierarchcal path view model. The approach can be applied to various search algorithm to reduce search time costs, including distance range queries, k-nearest neighbor search.},
 pages = {10--28},
 title = {道路網応用のための空間索引木の提案と最短経路探査への応用},
 volume = {2},
 year = {2009}
}