Timezone: »
Poster
Which Space Partitioning Tree to Use for Search?
Parikshit Ram · Alexander Gray
Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
We consider the task of nearest-neighbor search with the class of binary-space-partitioning trees, which includes kd-trees, principal axis trees and random projection trees, and try to rigorously answer the question "which tree to use for nearest-neighbor search?'' To this end, we present the theoretical results which imply that trees with better vector quantization performance have better search performance guarantees. We also explore another factor affecting the search performance -- margins of the partitions in these trees. We demonstrate, both theoretically and empirically, that large margin partitions can improve the search performance of a space-partitioning tree.
Author Information
Parikshit Ram (IBM Research AI)
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 -
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 -
2009 Poster: Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions »
Parikshit Ram · Dongryeol Lee · Hua Ouyang · 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