文献

J-GLOBAL ID：201802276682431359   整理番号：18A1613412

高次元データに関する近似最近傍探索を加速するための下界の利用【JST・京大機械翻訳】

Exploiting lower bounds to accelerate approximate nearest neighbor search on high-dimensional data

著者 (3件)： Liu Yingfan (Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong) ,  Wei Hao (Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong) ,  Cheng Hong (Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong)
資料名： Information Sciences  (Information Sciences)
巻： 465  ページ： 484-504  発行年： 2018年 
JST資料番号： D0636A  ISSN： 0020-0255  CODEN： ISIJBC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 高次元空間における近似最近傍(ANN)探索は多くの応用における基本的な操作である。過去数十年の間,多くのインデクシング方法が,逆インデックスベースの方法,ツリー構造,局所性敏感なハッシングベースの方法,および近接グラフを含むANN検索を解決するために提案された。本論文では,既存のインデクシング法によるANN探索を高速化するための下限技術を探索した。従来の下限は効率と信頼性の間の満足なトレードオフに達することができないので,著者らは既存の下限の概念を調べて,より低い結合の概念を拡張する,進行下限(PLB)と統計下限(SLB)の2つの新しいタイプを定義した。さらに,PLBの良好な例,すなわち漸進的部分距離(PPD)を提案した。最初の試みとして,SLBのアイデアを提案し,SLBの良好な例として非対称量子化器距離(AQD)を実証した。注目すべきことに,AQDは以前の研究での距離の推定としてのみ扱われたが,本論文ではより低い結合の機能性を発見した。実際のデータ集合に関する広範な実験に従って,著者らの下限は既存のインデクシング法のANN探索を明らかに加速でき,著者らの下限はそれらの強い剪定力のために有意なマージンによって既存の下限より優れていることを実証した。特に,AQDは,最先端のインデクシング法HNSW(MalkovとYashunin,2016)1.9倍を,高い想起0.95に対して1.9倍にする。他のインデクシング法と同様に,AQDのスピードアップは,HNSWより多くの候補にアクセスする必要があるので,より高い。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  信頼性 ,  高速化 ,  *高次元 ,  非対称性 ,  ハッシング ,  ツリー構造 ,  *近傍探索法 ,  量子化器 ,  局所性
準シソーラス用語： 機能性 ,  *下界 ,  高次元データ , 【Automatic Indexing@JST】

著者キーワード (4件)： 近似最近傍探索 ,  高次元データ ,  進行下限 ,  統計的下界

分類 (2件)： 人工知能  (JE08000Z) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： 高次元データ ,  近似 ,  近傍探索 ,  加速 ,  下界