Fast Exact Max-kernel Search

Curtin Ryan R., Ram Parikshit, Gray Alexander G.. Arxiv 2012

[Paper]    
ARXIV

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(nlogn)$ algorithm to index any set of objects (points in ${\text{Real}}^{\text{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(logn)$ 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.

Similar Work

• Approximate Nearest Neighbors In Limited Space
• Derandomized Balanced Allocation
• Hashmod A Hashing Method For Scalable 3D Object Detection
• Beyond Locality-sensitive Hashing