2026-06-06T13:20:00Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00225826 2025-01-19T12:40:06Z 1164:3865:11134:11252

空間ネットワークにおける近似逆最近傍探索手法の提案 池田, 裕一朗 後藤, 佑介 基盤システム・アルゴリズム 近年，GPS を利用した位置情報サービスに対する関心が高まっている．位置情報サービスにおいて，オブジェクト間の関係性を調べる方法である最近傍探索 (k-Nearest Neighbor Search: kNN) では，位置情報の問い合わせ元となるクエリが探索条件に応じて候補となる k 個のターゲットを探索する．また，最近傍探索の応用技術である逆最近傍探索 (Reverse kNN: RkNN) では，クエリに最も影響を受けている k 個のターゲットを取得する．本研究で用いる近似逆最近傍探索 (Reverse Approximate Nearest Neighbor: RANN) は，クエリからの影響に対する定義を逆最近傍探索より緩和した技術である．各オブジェクトは，最も影響を受けるクエリだけでなく，このクエリと同じくらい影響を受ける他のクエリに対しても同様に，RANN における探索候補のターゲットとなる．これまでの RANN 手法は，オブジェクト間をユークリッド距離で表現したユークリッド空間上におけるクエリのみを考慮していた．このため，オブジェクト間を道路網のネットワーク距離で表現した空間ネットワーク上のクエリに対して適用できなかった．また，RkNN と異なり，RANN は，空間ネットワーク上でクエリから一定範囲内にあるすべてのオブジェクトを探索する必要がある．従って，多くのオブジェクトが密な空間ネットワークを構築している場合，探索時間は長大化する．本研究では，空間ネットワークにおける近似逆最近傍探索手法を提案する．提案手法では，オブジェクト間のネットワーク距離に基づいてオブジェクトを探索し，ネットワークボロノイ図に基づく刈取り技術を用いて，各オブジェクトがクエリの RANN となるターゲットの候補であるかを検証する．計算機端末によるシミュレーション評価では，提案手法による探索時間は，実際の探索で利用可能な時間内であることを確認した．また，オブジェクト数が多いほど提案手法による刈取りが有効であることを確認した． technical report 情報処理学会 2023-05-11 application/pdf 研究報告モバイルコンピューティングと新社会システム（MBL） 11 2023-MBL-107 1 8 2188-8817 AA11851388 https://ipsj.ixsq.nii.ac.jp/record/225826/files/IPSJ-MBL23107011.pdf jpn