A Learning Framework for Nearest Neighbor Search
Lawrence Cayton, Sanjoy Dasgupta · 2008
Can we leverage learning techniques to build a fast nearest-neighbor (ANN) re-trieval data structure? We present a general learning framework for the NN prob-lem in which sample queries are used to learn the parameters of a data structure that minimize the retrieval time and/or the miss rate. We explore the potential of this novel framework through two popular NN data structures: KD-trees and the rectilinear structures employed by locality sensitive hashing. We derive a gener-alization theory for these data structure classes and present simple learning algo-rithms for both. Experimental results reveal that learning often improves on the already strong performance of these data structures. 1