人生几何?

2021ICMR-(删除非中心点)Efficient Neare

2021-09-08  本文已影响0人  Caucher

编者的总结

  1. 本文提出的是一个预处理的方法,用于在KNN搜索中削减数据集规模,使得构建/运行其他KNN算法时内存占用变少。
  2. 由于预处理后数据集变少了,那么其他算法的压缩比就可以放宽一些,精度自然而然也就提升起来了。

编者的思考

  1. 本文提的算法的代价有点过高,作为一个预处理算法,有N2的复杂度,这是比较夸张的。虽然索引算法的构建和查询的内存占用少了,但是这个预处理占的资源也比较高了。
  2. 核心亮点就是挖出了hubness这一度量,但是对于更为general的benchmark,即数据集数据分布和查询集数据分布未必一致吻合时,是什么情况,还有待考究。

1 INTRODUCTION

3 WHICH VECTORS ARE UNNECESSARY?

什么是不重要的向量呢?如果给定数据集和查询集,那些数据集中不属于任何query的KNN的向量,就是不重要的向量。
本文的方法就是要删去一些不重要的向量,处理完数据集之后,任何ANN搜索算法都可以用于新的小数据集。

3.1 Hubness

首先定义中心度(hubness).节点的中心度,是指该节点包含在多少其他节点(数据集中)的KNN。形式化定义如下:


image.png
image.png

3.2 Exploratory Experiment with Deep1M

我们把查询集的KNN的所有向量构成一个集合,数据集中另一部分向量构成一个集合,分别来算中心度分布,得到如下图:


image.png

4 PROPOSED METHOD

4.1 Reduction of Anti-Hubs

有上面的发现,一种最简单的想法就是每个节点都算一下中心度,取前T个最大的保留就好了。

4.2 Approximation

上述方法复杂度太高,至少应该把距离计算的复杂度降下来。
作者的方法也非常简单:分治。
数据集首先做K-means,在每个聚类里面分别运行4.1的方法,再合并起来。

5 EXPERIMENTS

4个GPU, 3.6 GHz Intel Xeon CPU (24 cores, 96 threads) and 192 GiB内存。
python多线程写的。 k设为16.


image.png

5.5 Comparison with Other𝑁ReductionMethods

5.6 Comparison with Other \gamma Reduction Methods

5.8 Validation of Approximation Process

上一篇 下一篇

猜你喜欢

热点阅读