Fast Exact Max-Kernel Search
By Ryan R. Curtin, Alexander G. Gray, Parikshit Ram. 2012
52 citations recorded by the source corpus.
The wide applicability of kernels makes the problem of max-kernel search ubiquitous and more general than the usual similarity search in metric spaces. We focus on solving this problem efficiently. We begin by characterizing the inherent hardness of the max-kernel search problem with a novel notion of directional concentration. Following that, we present a method to use an $O(n \log n)$ algorithm to index any set of objects (points in $\Real^\dims$ or abstract objects) directly in the Hilbert space without any explicit feature representations of the objects in this space. We present the first provably $O(\log n)$ algorithm for exact max-kernel search using this index. Empirical results for a variety of data sets as well as abstract objects demonstrate up to 4 orders of magnitude speedup in some cases. Extensions for approximate max-kernel search are also presented.
Subfields: Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Optimization & Training
Citations in the corpus
- Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “Later, the same method was generalized for general max kernel search [5], where the runtime guarantees, like other space partitioning methods, are heavily dependent on the dimensionality and the expansion constants.”
- Learning and Inference via Maximum Inner Product Search (2016, unknown): “These were recently generalized to max kernel search (Curtin et al., 2013).”
- To Index or Not to Index: Optimizing Exact Maximum Inner Product Search (2017, methodology): “[8] extends this method using cover trees [5], but Teflioudi et al.”
- On Symmetric and Asymmetric LSHs for Inner Product Search (2014, unknown): “M L ] 2 4 O ct 2 01 4”