A learning framework for nearest neighbor search

Part of Advances in Neural Information Processing Systems 20 (NIPS 2007)

Bibtex »Metadata »Paper »

Authors

Lawrence Cayton, Sanjoy Dasgupta

Abstract

<p>Can we leverage learning techniques to build a fast nearest-neighbor (NN) retrieval data structure? We present a general learning framework for the NN problem 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 generalization theory for these data structure classes and present simple learning algorithms for both. Experimental results reveal that learning often improves on the already strong performance of these data structures.</p>