Timezone: »
The long-standing problem of efficient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 fingerprinting to bioinformatics to movie recommendations. As the dimensionality of the dataset increases, exact NN search becomes computationally prohibitive; (1+eps)-distance-approximate NN search can provide large speedups but risks losing the meaning of NN search present in the ranks (ordering) of the distances. This paper presents a simple, practical algorithm allowing the user to, for the first time, directly control the true accuracy of NN search (in terms of ranks) while still achieving the large speedups over exact NN. Experiments with high-dimensional datasets show that it often achieves faster and more accurate results than the best-known distance-approximate method, with much more stable behavior.
Author Information
Parikshit Ram (IBM Research AI)
Dongryeol Lee (Independent Researcher)
Hua Ouyang
Alexander Gray (Skytree Inc. and Georgia Tech)
More from the Same Authors
-
2021 : FLoRA: Single-shot Hyper-parameter Optimization for Federated Learning »
Yi Zhou · Parikshit Ram · Theodoros Salonidis · Nathalie Baracaldo · Horst Samulowitz · Heiko Ludwig -
2021 : Sign-MAML: Efficient Model-Agnostic Meta-Learning by SignSGD »
Chen Fan · Parikshit Ram · Sijia Liu -
2023 Poster: Model Sparsity Can Simplify Machine Unlearning »
jinghan jia · Jiancheng Liu · Parikshit Ram · Yuguang Yao · Gaowen Liu · Yang Liu · PRANAY SHARMA · Sijia Liu -
2023 Workshop: Associative Memory & Hopfield Networks in 2023 »
Parikshit Ram · Hilde Kuehne · Daniel Lee · Cengiz Pehlevan · Mohammed Zaki · Lenka Zdeborová -
2022 Poster: Advancing Model Pruning via Bi-level Optimization »
Yihua Zhang · Yuguang Yao · Parikshit Ram · Pu Zhao · Tianlong Chen · Mingyi Hong · Yanzhi Wang · Sijia Liu -
2021 : Contributed Talk 6: FLoRA: Single-shot Hyper-parameter Optimization for Federated Learning »
Yi Zhou · Parikshit Ram · Theodoros Salonidis · Nathalie Baracaldo · Horst Samulowitz · Heiko Ludwig -
2021 Poster: Pipeline Combinators for Gradual AutoML »
Guillaume Baudart · Martin Hirzel · Kiran Kate · Parikshit Ram · Avi Shinnar · Jason Tsay -
2020 Expo Demonstration: Beyond AutoML: AI Automation & Scaling »
Lisa Amini · Nitin Gupta · Parikshit Ram · Kiran Kate · Bhanukiran Vinzamuri · Nathalie Baracaldo · Martin Korytak · Daniel K Weidele · Dakuo Wang -
2013 Poster: Which Space Partitioning Tree to Use for Search? »
Parikshit Ram · Alexander Gray -
2012 Poster: Minimax Multi-Task Learning and a Generalized Loss-Compositional Paradigm for MTL »
Nishant A Mehta · Dongryeol Lee · Alexander Gray -
2009 Workshop: Large-Scale Machine Learning: Parallelism and Massive Datasets »
Alexander Gray · Arthur Gretton · Alexander Smola · Joseph E Gonzalez · Carlos Guestrin -
2009 Poster: Submanifold density estimation »
Arkadas Ozakin · Alexander Gray -
2009 Poster: Linear-time Algorithms for Pairwise Statistical Problems »
Parikshit Ram · Dongryeol Lee · William B March · Alexander Gray -
2009 Spotlight: Linear-time Algorithms for Pairwise Statistical Problems »
Parikshit Ram · Dongryeol Lee · William B March · Alexander Gray -
2008 Poster: QUIC-SVD: Fast SVD Using Cosine Trees »
Michael Holmes · Alexander Gray · Charles Isbell -
2008 Demonstration: MLPACK: Scalable Machine Learning Software »
Alexander Gray -
2008 Poster: Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method »
Dongryeol Lee · Alexander Gray -
2007 Poster: Multi-Stage Monte Carlo Approximation for Fast Generalized Data Summations »
Michael Holmes · Alexander Gray · Charles Isbell