抄録
D-024
道路網上でのANN探索法
○HTOO HTOO・大沢　裕（埼玉大）・曽根原登（NII）
ANN検索とは，複数の検索点とある集約関数が指定され，条件を満たす検索対象点を最適な順に任意個求める探索法である．この検索は，最初ユークリッド距離に基づく検索として提案され，その後道路網上での距離による検索に拡張されてきた．その際に，まずユークリッド距離で候補を探し，その結果を道路網上の距離で検証するアプローチがとられる．本稿では，多数の目的地を設定できるA*アルゴリズムをこの検証に用いる方式を提案する．提案方式では，道路網上での演算で多くの処理時間を要する隣接リスト参照の重複をなくすことができ，大規模道路網に対して大幅な速度向上が図られる．実験により，本方式の有効性を検証する．