D-012
道路網距離の簡易マテリアライズ化を用いた空間的Skyline検索の高速化

◎越澤和樹・Htoo Htoo・大沢　裕（埼玉大）

地理情報サービスにおいて、道路網上のノード間の最短距離の計算は重要である。道路網の分割および道路網距離のマテリアライズ化を行ったSimple Materialized Path View(SMPV)構造を利用することで、高速な距離計算が可能となる。本稿では、道路網において利用者の興味のあるオブジェクトに絞り込む検索である空間的Skyline検索に対し、SMPV構造を適用する。まずSMPV構造を用いた最近傍探索アルゴリズムを提案し、さらに最短経路探索であるShortest Path Finderと共に従来のアルゴリズムへ組み込むことで、高速化を実現する。