  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.
