基于邻居聚类的近似最近邻搜索

赵 增，李明勇，胡航飞

（1东华大学 计算机科学与技术学院，上海 201620；2上海市计算机软件评测重点实验室，上海 200235）

0 引 言

数十年来，最近邻居搜索（NNS）一直是一个热门话题，它在数据挖掘，机器学习和人工智能的许多应用中发挥着重要作用。当前，可用的数据集涵盖了广泛的应用程序和数据类型，包括图像、音频、视频、文本、合成和深度学习数据。SIFT、CIFAR等图像数据集是将局部图像区域压缩到高维度空间中的单个点，这些外部点使用64到512个外部维度。

计算高维向量之间的欧几里得距离是NNS的基本要求。由于维数灾难，NNS本质上很昂贵。具有n个数据点并在n维空间Rd中查询q的数据集D，N N S的目的是找到最接近q的点o*∈D。其中，o*称为q的最近邻居。定义如式（1）：

通常，最接近查询点q的K个点是从数据集中返回的，称为K-最近邻居搜索（K-NNS）。查找kNN集的简单方法是计算查询q与数据集D中每个点之间的距离，并选择距离最小的点。当处理稀疏数据时，可以通过高级索引结构（例如，反向索引）有效地计算NNS。但是，对于具有密集特征的数据，查找NNS的成本为O（n）。当数据集很大时，耗时严重。对于高维NNS，由于难以找到准确的结果，大多转向NNS的近似版本，即近似k最近邻搜索（K-ANNS），在近二十年中已被广泛使用。

近来，基于图的方法引起了人们的极大关注。例如NSG［1］、HNSW［2］、EFANNA［3］和FANNG［4］等方法。基于图的方法离线构造kNN图，可以将其视为高维空间中的大型网络图。使用基于图的方法所面临的挑战是精确kNN图的高构造复杂性，尤其是涉及大型数据集时，计算复杂性将成倍增加。……