WEKO3
アイテム
空間ネットワークにおける近似逆最近傍探索手法の提案
https://ipsj.ixsq.nii.ac.jp/records/225826
https://ipsj.ixsq.nii.ac.jp/records/22582641fcaaa0-bf12-410b-8122-082c659c5d2a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MBL23107011.pdf (1.8 MB)
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-05-11 | |||||||||
| タイトル | ||||||||||
| タイトル | 空間ネットワークにおける近似逆最近傍探索手法の提案 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 基盤システム・アルゴリズム | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 岡山大学大学院環境生命自然科学研究科 | ||||||||||
| 著者所属 | ||||||||||
| 岡山大学学術研究院環境生命自然科学学域 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Graduate School of Environmental, Life, Natural Science and Technology, Okayama University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Faculty of Environmental, Life, Natural Science and Technology, Institute of Academic and Research, Okayama University | ||||||||||
| 著者名 |
池田, 裕一朗
× 池田, 裕一朗
× 後藤, 佑介
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 近年，GPS を利用した位置情報サービスに対する関心が高まっている．位置情報サービスにおいて，オブジェクト間の関係性を調べる方法である最近傍探索 (k-Nearest Neighbor Search: kNN) では，位置情報の問い合わせ元となるクエリが探索条件に応じて候補となる k 個のターゲットを探索する．また，最近傍探索の応用技術である逆最近傍探索 (Reverse kNN: RkNN) では，クエリに最も影響を受けている k 個のターゲットを取得する．本研究で用いる近似逆最近傍探索 (Reverse Approximate Nearest Neighbor: RANN) は，クエリからの影響に対する定義を逆最近傍探索より緩和した技術である．各オブジェクトは，最も影響を受けるクエリだけでなく，このクエリと同じくらい影響を受ける他のクエリに対しても同様に，RANN における探索候補のターゲットとなる．これまでの RANN 手法は，オブジェクト間をユークリッド距離で表現したユークリッド空間上におけるクエリのみを考慮していた．このため，オブジェクト間を道路網のネットワーク距離で表現した空間ネットワーク上のクエリに対して適用できなかった．また，RkNN と異なり，RANN は，空間ネットワーク上でクエリから一定範囲内にあるすべてのオブジェクトを探索する必要がある．従って，多くのオブジェクトが密な空間ネットワークを構築している場合，探索時間は長大化する．本研究では，空間ネットワークにおける近似逆最近傍探索手法を提案する．提案手法では，オブジェクト間のネットワーク距離に基づいてオブジェクトを探索し，ネットワークボロノイ図に基づく刈取り技術を用いて，各オブジェクトがクエリの RANN となるターゲットの候補であるかを検証する．計算機端末によるシミュレーション評価では，提案手法による探索時間は，実際の探索で利用可能な時間内であることを確認した．また，オブジェクト数が多いほど提案手法による刈取りが有効であることを確認した． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11851388 | |||||||||
| 書誌情報 |
研究報告モバイルコンピューティングと新社会システム（MBL） 巻 2023-MBL-107, 号 11, p. 1-8, 発行日 2023-05-11 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8817 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
