ピボットベースの完全二分木による効率的類似性検索

YAMAGISHI Yuki; AOYAMA Kazuo; SAITO Kazumi; IKEDA Tetsuo

文献

J-GLOBAL ID：201702218509962453 整理番号：17A1619660

ピボットベースの完全二分木による効率的類似性検索

Efficient Similarity Search with a Pivot-Based Complete Binary Tree

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=17A1619660&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=17A1619660&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (4件)： , , ,
資料名：
巻： E100.D 号： 10 ページ： 2526-2536(J-STAGE) 発行年： 2017年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

本論文は,大規模かつ高次元のデータセットに対して,最適化したピボットに基づく完全二分木(CBT)をインデックスとして使用する,効率的な類似性検索法を提案した。一般的に,類似性検索方法は,オンラインでのインデックス構築とオンラインでの類似性検索自体の両方において高速な性能を必要とする。この要求を満たすために,筆者らは,範囲問合せに対して提案した方法においてインデックス構築および類似性検索アルゴリズムに新規な技術を導入した。インデックス構築アルゴリズムは,以下の2つの主な機能を再帰的に使用し,CBTインデックスをもたらした。1つは,定義した目的関数を効率的に最大化することによって各ノードで1つの有効なピボットを得るピボット生成関数である。もう1つは,ノードの1組のオブジェクトを,最適化したピボットに基づいて2つのほぼ等しいサイズのサブセットに分割するノード二分機能である。本類似性検索アルゴリズムは,不要なブランチを枝刈りし,各段階でオブジェクトをフィルタリングすることにより,所定の範囲内の候補オブジェクトを絞り込む3段階のプロセスを採用した。高次元の100万本の実画像データに対する実験結果は,提案した方法が,オフラインで妥当な計算コストで構築したCBTインデックスを使用して,最新の方法の1つの計算コストの約4分の1から約半分で,範囲問合せに対する正確な解を求めることを実証した。(翻訳著者抄録)

, , , , , , , ,
, , , ,

著者キーワード (5件)： , , , ,

その他の計算機利用技術

引用文献 (25件)：

[1] E. Chávez, G. Navarro, R. Baeza-Yates, and J.L. Marroquín, “Searching in metric spaces,” ACM Computing Surveys, vol.33, no.3, pp.273-321, Sept. 2001. 10.1145/502807.502808
[2] P. Zezula, G. Amato, V. Dohnal, and M. Batko, Similarity search: The metric space approach, Springer, New York, NY, 2006.
[3] H. Samet, Foundations of multidimensional and metric data structures, Morgan Kaufmann Publishers, San Francisco, CA, 2006.
[4] S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A.Y. Wu, “An optimal algorithm for approximate nearest neighbor searching fixed dimensions,” Journal of the ACM, vol.45, no.6, pp.891-923, Nov. 1998. 10.1145/293347.293348
[5] P. Indyk, Handbook of Discrete and Computational Geometry (second edition), chapter 39: Nearest neighbors in high-dimensional spaces, Chapman and Hall/CRC, 2004.

前のページに戻る