On the I/O Complexity of the k-Nearest Neighbors Problem
On the I/O Complexity of the k-Nearest Neighbors Problem
复制标题
DOI：
10.1145/3375395.3387649
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Mayank Goswami;R. Jacob;R. Pagh
中科院分区：
文献类型：
--
作者：
Mayank Goswami;R. Jacob;R. Pagh
我们考虑 k 最近邻 (k-NN) 问题的精确和近似版本的静态外部存储器索引，并在标准不可分性假设下显示新的下界：汉明空间中高维 k-NN 的多项式空间索引方案无法利用块传输：需要 í(k) 块读取来回答查询。对于 l∞ 度量，即使我们允许返回 c 近似最近邻，下界也成立，因为 c ∈ (1, 3)。对 c 1 的限制存在一个多项式空间数据结构，该结构返回 ⌈k/B⌉ I/O 中的 k 个 c 近似最近邻。为了显示这些下限，我们开发了两种新技术：首先，为了处理近似算法在决定返回哪个结果集方面有更大的自由度，我们开发了 Hellerstein 等人的 λ 集工作负载技术的宽松版本。这种技术使我们能够显示 d ≥ n 维中的下界。为了将下界扩展到 d = O(k log(n/k)) 维度，我们开发了一种可能具有独立意义的新的确定性降维技术。
We consider static, external memory indexes for exact and approximate versions of the k-nearest neighbor (k-NN) problem, and show new lower bounds under a standard indivisibility assumption: Polynomial space indexing schemes for high-dimensional k-NN in Hamming space cannot take advantage of block transfers: í(k) block reads are needed to to answer a query. For the l∞ metric the lower bound holds even if we allow c-appoximate nearest neighbors to be returned, for c ∈ (1, 3). The restriction to c 1 there exists a polynomial space data structure that returns k c-approximate nearest neighbors in ⌈k/B⌉ I/Os. To show these lower bounds we develop two new techniques: First, to handle that approximation algorithms have more freedom in deciding which result set to return we develop a relaxed version of the λ-set workload technique of Hellerstein et al. This technique allows us to show lower bounds that hold in d ≥ n dimensions. To extend the lower bounds down to d = O(k log(n/k)) dimensions, we develop a new deterministic dimension reduction technique that may be of independent interest.