Fast Exact Max-Kernel Search
Fast Exact Max-Kernel Search
复制标题
DOI：
10.1137/1.9781611972832.1
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Ryan R. Curtin;Alexander G. Gray;Parikshit Ram
中科院分区：
文献类型：
--
作者：
Ryan R. Curtin;Alexander G. Gray;Parikshit Ram
核的广泛适用性使得最大核搜索问题比度量空间中常见的相似度搜索问题更普遍。我们专注于有效地解决这个问题。我们首先用一个新的方向集中的概念来描述最大核搜索问题的固有硬度。接下来，我们提出了一种方法，使用$O(n \log n)$算法直接在Hilbert空间中索引任何对象集合（$\Real^\dims$中的点或抽象对象），而不需要该空间中对象的任何显式特征表示。我们提出了第一个可证明的$O(\log n)$算法，用于使用这个索引进行精确的最大核搜索。对于各种数据集以及抽象对象的经验结果表明，在某些情况下，加速可达4个数量级。给出了近似最大核搜索的扩展。
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.