Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search

摘要：

　　Approximate nearest neighbor algorithms are used to speed up nearest neighbor search in a wide array of applications.However,current indexing methods feature several hyperparameters that need to be tuned to reach an acceptable accuracy–speed trade-off.A grid search in the parameter space is often impractically slow due to a time-consuming index-building procedure.Therefore,we propose an algorithm for automatically tuning the hyperparameters of indexing methods based on randomized space-partitioning trees.In particular,we present results using randomized k-d trees,random projection trees and randomized PCA trees.The tuning algorithm adds minimal overhead to the indexbuilding process but is able to find the optimal hyperparameters accurately.We demonstrate that the algorithm is significantly faster than existing approaches,and that the indexing methods used are competitive with the state-of-the-art methods in query time while being faster to build.

关键词： Nearest neighbor search Approximate nearest neighbors Randomized space-partitioning trees Indexing methods Autotuning

作者: Elias J(a)(a)saari Ville Hyv(o)nen Teemu Roos

作者单位: Kvasir Ltd.,Cambridge,England Department of Computer Science,University of Helsinki,Helsinki,Finland;Helsinki Institute for Inform

会议类型: 国际会议

会议名称: The 23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining (第23届亚太知识发现和数据挖掘国际会议(PAKDD2019)

会议地点: 澳门

会议语种:英文

页码: 590-602

在线出版日期: 2019-04-14（万方平台首次上网日期，不代表论文的发表时间）