文献

J-GLOBAL ID：201802231417301725   整理番号：18A0376311

効率的且つ正確な類似検索のための完全2分木付きピボット生成アルゴリズム

Pivot Generation Algorithm with a Complete Binary Tree for Efficient Exact Similarity Search

著者 (4件)： YAMAGISHI Yuki (University of Shizuoka) ,  AOYAMA Kazuo (NTT Communication Science Laboratories) ,  SAITO Kazumi (University of Shizuoka) ,  IKEDA Tetsuo (University of Shizuoka)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E101.D  号： 1  ページ： 142-151(J-STAGE)  発行年： 2018年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本稿では,大規模データセットにおける正確な類似検索を高速化するためのピボットセット生成アルゴリズムを紹介する。大規模なデータセットを処理するには,検索インデックスを効率的に構築し,オンラインで正確な類似検索を高速に実行することが重要である。筆者らの提案アルゴリズムは,階層的データ分割と高速ピボット最適化技術という2つの新しい手法を用いて,効率的なピボットを生成する。少数のピボットを有効に使用するために,前者は,2つの割り当てられたピボットのそれぞれからからのランク順に依存し,完全な2分木をもたらす同一サイズの2つのサブセットにデータセットを再帰的に分割する。後者は,ピボット空間にマップされたデータオブジェクトを巧みに操作することによって,低い計算コストでピボット最適化のために定義された目的関数を計算する。生成されたピボットは,クエリオブジェクトとデータオブジェクトとの間の距離に関する厳しい下限を提供するので,正確な類似検索アルゴリズムは,不必要な距離計算を効果的に回避する。提案アルゴリズムにより生成されたピボットを用いた探索アルゴリズムは,実際の大規模画像データセットの範囲問合せ問題に関して,距離計算を非常に高速に行うことができることを示す。(翻訳著者抄録)

シソーラス用語： *情報検索 ,  *二分木 ,  *集合 ,  *製造 ,  *発生 ,  *アルゴリズム ,  分割 ,  最適化手法 ,  等級づけ ,  計算機アルゴリズム ,  計算
準シソーラス用語： *類似検索 ,  *ピボットセット ,  データセット ,  *データ生成 ,  階層的分割 ,  検索アルゴリズム ,  距離計算

著者キーワード (3件)： similarity search ,  pivot generation ,  complete binary tree

分類 (2件)： 情報検索一般  (AC06010H) ,  情報処理一般  (JE15010U)

引用文献 (24件)：

• [1] G. Amato, A. Esuli, and F. Falchi, “A comparison of pivot selection techniques for permutation-based indexing,” Information Systems, vol.52, pp.176-188, Aug.-Sept. 2015. 10.1016/j.is.2015.01.010
• [2] A. Andoni, M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni, Nearest-neighbor methods in learning and vision: theory and practice, chapter 3: Locality-sensitive hashing using stable distributions, The MIT Press, Cambridge, Massachusetts, 2006.
• [3] S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A.Y. Wu, “An optimal algorithm for approximate nearest neighbor searching in fixed dimensions,” Journal of the ACM, vol.45, no.6, pp.891-923, Nov. 1998. 10.1145/293347.293348
• [4] M. Batko, P. Kohoutkova, and D. Novak, “CoPhIR image collection under the microscope,” In Proc. Int. Conf. Similarity Search and Applications, pp.47-54, IEEE, 2009. 10.1109/sisap.2009.25
• [5] P. Bolettieri, A. Esuli, F. Falchi, C. Lucchese, R. Perego, T. Piccioli, and F. Rabitti, CoPhIR: a test collection for content-based image retrieval, CoRR, abs/0905.4627v2, 2009.

タイトルに関連する用語 (3件)： 類似検索 ,  2分木 ,  アルゴリズム