Fast Exact Max-Kernel Search
This addresses a ubiquitous problem in kernel-based methods for researchers and practitioners, offering significant performance improvements.
The paper tackles the problem of max-kernel search, which is more general than similarity search in metric spaces, by presenting an efficient algorithm that achieves up to 4 orders of magnitude speedup in some cases.
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.