Timezone: »

A learning framework for nearest neighbor search
Lawrence Cayton · Sanjoy Dasgupta

Mon Dec 03 10:30 AM -- 10:40 AM (PST) @ None #None

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.

Author Information

Lawrence Cayton (Max Planck Institute for Biological Cybernetics)
Sanjoy Dasgupta (UC San Diego)

More from the Same Authors