近邻问题的亚线性算法研究现状综述

马恒钊，李建中，2

（1 哈尔滨工业大学 海量数据计算研究中心，哈尔滨 150001；2 中科院深圳理工大学，广东 深圳 518107）

0 引言

近年来，大数据概念已经在研究界和应用界越来越热门，这也表明大数据时代已然来临。许多应用已经开始日常处理起TB 级数据，比如广为人知的TeraSort 应用。而在一些场景、比如科学数据中，甚至开始面对PB、以及EB 级数据，诸如大型综合巡天望远镜（Large Synoptic Survey Telescope，LSST）每天生成的数据量就达到1.25 PB。下面做一个简单的计算。设想要通过SSD 固态硬盘来读取数据，目前SSD 的最大读带宽约为6 GB/s，于是，仅读取1 PB 数据就需要34.7 h，读取1 EB 数据甚至需要超过4 年时间。这表明，在处理大数据时，串行线性算法的运行时间也有可能是不可接受的。如何高效地处理这样天文级数量的数据，成为理论研究界和应用界共同的挑战。应用界提出的解决办法一般是并行化，比如淘宝应对双十一的海量事务处理请求所用的就是阿里云等并行处理平台。但是从理论界看来，并行化有以下一些问题：

（1）有些问题是无法高效并行化的。

（2）并行化并不能降低问题的复杂度。

（3）并行化带来了通信复杂度和通信瓶颈等问题。

（4）这也是最重要的一项，并行化有可扩展性和加速比的问题，即当所使用的处理器数量达到一定阈值时，再增加处理器将无法降低总运行时间，甚至还有可能会增加总运行时间。因此，理论界解决大数据问题所提出的方案是设计亚线性算法，即时间复杂度为（logn）或者（n）的算法，其中0，1。只有设计亚线性算法，才能从根本上降低算法的时间复杂度，减小处理大数据所需要的时间。

根据文献［5］提出的理论，亚线性算法分为2类。其一为纯亚线性算法，即可以直接通过亚线性算法解决的问题；其二为伪亚线性算法，即经过一个多项式时间的预处理后，再通过亚线性算法可以解决的问题。前者包括判定数组是否为ε-far 单调问题，具体算法参见文献［6］。后者则包括众所周知的无序数组查找问题，即在无序数组上查找元素，可以通过花费（）时间进行排序，再通过（1）时间的二分查找予以解决。亚线性算法已经有接近二十年的研究历史，最初的研究内容集中于属性测试，后来又拓展至图算法、计算几何、代数计算等领域。参见综述文献［11］。这些问题在许多领域都有广泛的应用，比如生物信息、物联网、轨迹分析、机器学习、推荐系统等。然而对于近似最近邻领域，其亚线性算法的研究却还未臻充分。本文对该问题的亚线性算法的研究现状做了综述。

1 全k-最近邻问题算法概述

全k-最近邻问题简记作All-kNN。关于此问题的工作最早可以追溯到1983 年，且近年来也一直有关于此问题的研究工作出现。此问题备受各方关注的原因，是因为许多应用都以AllkNN 问题作为重要的子程序，比如分类、凝聚式聚类、图像检索、推荐系统以及离群点检测等。在许多类似的应用中，计算All-kNN 都是主要的瓶颈。

由于该问题的重要性，历史上研究者们提出了许多算法试图高效地解决All-kNN 问题，这些算法可以分为以下3 类：

（1）第一类算法。使用各种不同的技巧来降低算法的实际运行时间，然而这些算法的最坏时间复杂度仍为（）不变。据研究分析可知，这些算法大致有3 种算法设计技巧。分述如下。

①第一种，基于树型的空间索引。如树和Voronoi 图等。

②第二种，基于空间填充曲线，包括希尔伯特曲线和Z-order 曲线等。空间填充曲线是一类在高维数据上建立一维索引的方法，基于空间填充曲线构建的索引具有一种重要特性，即在空间上相近的点更容易被分配到相近的索引项中。据文献［19，29-30］中的结果，此性质有助于降低计算All-kNN时需要计算距离的次数。

③第三种，基于近邻传播的思想，即近邻的近邻仍很有可能是近邻。NN-descent 算法是提出此思想的开创性工作，且仍是目前All-kNN 问题最好的算法之一。其他使用此思想的算法一般先以某种方法作为预处理，再使用近邻传播技巧来提高结果的精度。例如，文献［32］中使用随机分治方法作为预处理，而文献［33］中使用局部敏感哈希方法作为预处理。

（2）第二类算法。是在并行环境下解决问题。文献［34］理论上证明了All-kNN 问题存在并行最优算法，该算法在CREW PRAM 模型上需要（）时间和（）个处理器。其他工作则致力于在不同的并行平台上解决All-kNN 问题，比如MapReduce 平台和GPU 环境。

上述算法的最坏时间复杂度上界都为（），第三类算法则不同，现已都被证明了具有更低的时间复杂度，且都是串行算法，与文献［34］中给出的并行算法也不同。例如，Bentley给出了一种多维分治算法，可以在（（1））时间内解决AllkNN 问题，其中是数据的维数。又如，文献［17］中给出的算法需要（（））时间，其中是输入数据点集中最远的一对点和最近的一对点的距离之比。再者，文献［39］中给出的算法声明具有（kdnlogn）的时间复杂度上界。最后，研究发现了文献［39］中算法的一个错误，在文献［40］中给出了严格的证明，证明文献［39］中的算法的下界为（），并提出了新的算法，真正具有（）时间上界。

2 近似最近邻问题算法概述

近似最近邻问题，简记作ε-NN，是一个在理论研究和应用研究方面都很重要、且基础性的问题，自19 世纪90 年代起就有许多相关的解决算法被提出，这些算法可以分为4 类，如下所述。

（1）第一类算法，试图直接解决问题，且这些算法一般都设计了预处理数据结构来支持算法的高效运行。Arya 等人研究提出了一种算法，需要1/ε·空间，1/ε·预处理时间以及1/ε·查询时间。另有研究提出的算法需要（）空 间、（）预处理时间和（/）·查询时间。Kleinberg 在文献［14］中提出了2 个算法。其一是确定性算法且达到了（（））查询时间，使用的数据结构需要（（））空间和（（））预处理时间；其二是随机化算法，预处理时间为（·），所需的空间降至为（·）但其查询时间却提升为（·）。

（3）第三类算法，试图从另一个角度考虑ε-NN问题。算法利用了数据的一种内生维度，而非原始数据所存在的欧氏空间的维度。文献［17］给出了一个代表性的工作，该文献中提出的算法的查询时间复杂度上界为2（1），其中（）为输入点集的内生维度，是的直径。

在上述3 类算法之外，Indyk 等人开创了第四类算法。这类算法的关键思想在于定义了一个近似近邻问题，记作（，）-NN，然后将-NN 问题归约到此问题。于是解决-NN 问题的过程就分为了2 部分，一是解决（，）-NN 问题，二是设计从-NN 到（，）-NN 的归约。目前，有3 个现存工作设计了从-NN 到（，）-NN 的归约算法。对此拟做阐释分析如下。

（1）第一个归约算法是文献［18］中提出的，所构造的数据结构需要（·（））空间，其查询时间为（）。

（3）第三个算法在预处理阶段调用（，）-NN 算法来构造数据结构，其查询时间为（log），此处的指数（1）来自于算法的常数成功概率的要求。这3 个现存算法的查询时间都是比较高的，目前已在文献［41］中提出了新的图灵归约算法，具体查询时间为（1），低于所有上述现存算法。

3 近似k-最近邻问题算法概述

近似k-最近邻问题，简记作kANN 问题，是近似最近邻问题的自然推广，已在许多应用领域都有重要应用，比如数据可用性、数据库查询、以及图算法等。对于kANN 问题有2 种近似标准，分别称作距离标准和召回率标准。其中，距离标准要求近似结果集中的点到查询点的最远距离和精确结果集中的点到查询点的最远距离之比不超过给定阈值。召回率标准要求近似结果集和精确结果集的交集大小不小于给定阈值。下面将简要讨论现存工作是如何考虑上述2 个近似标准的。

关于kANN 问题的现存算法可以分为4 类。这里给出探讨剖析如下。

（1）第一类算法，是基于树的方法。这种方法的主要思想是将度量空间递归地划分为子空间，并组织成树结构。K-D 树是这种思想的代表性工作，但是这种方法只在低维空间中有效，当维度数升高时其性能会大幅下降。Vantage point 树是另一种基于树的方法，在方法性能上对K-D 树有所提升。FLANN 方法是最近的工作且在高维空间中有更好的表现，但是却有可能输出非最优的结果。据研究所知，现存的基于树的方法对距离标准和近似标准都没有理论保证。

（2）第二类算法，是基于置换的方法。方法的思想是挑选一个枢轴点的集合，并将每个数据元素表示成这些枢轴点的一个置换，这个置换是通过将枢轴点按照和数据元素的距离排序来得到的。在这种表示方法中，距离较近的数据元素的置换表示也相似。利用这种思想的方法包括MI-File和PPIndex。然而，据分析可知，这些方法也没能给出对距离标准和召回率标准的理论保证。

（3）第三类算法，是基于局部敏感哈希（Locality Sensitive Hashing，LSH）的方法。LSH 最初由Indyk等人提出，并应用于解决1 时的kANN 问题。不久之后，Datar 等人提出了第一个实用的LSH函数，此后关于LSH 的理论和应用研究就大量出现。例如，Andoni 等人证明了基于LSH 的算法的最优时空下界，并提出了符合下界的最优的LSH 函数。在应用方面，Gao 等人提出了一种致力于弥合LSH 的理论和kANN 应用的算法。可以参考概述文献［59］。基本的LSH 算法只能在1 的情况下满足距离标准。一些较晚近的算法有更多的进展。比如C2LSH解决了距离标准下的kANN 问题，但是却要求近似因子必须是整数的平方。SRS 算法也是针对距离标准下kANN 问题的算法，但是却只有部分的理论保证，即只有算法在特定条件下结束时，返回的结果才能满足距离标准。

（4）第四类算法，是基于图的算法。在这类算法中用到的特殊的图称为近似图，其中的边是基于顶点之间的几何关系定义的。可以参考概述文献［63］。例如，Paredes 等人使用了kNN 图，Ocsa等人使用的是相对邻居图（Relative Neighborhood Graph，RNG），Malkov 等人使用的是可导航的小世界图（Navigable Small World Graph，NSW）。在这种基于图的kANN 算法中经常用到在近似图上的导航过程，即选择图上的某一个顶点作为起始点，并按照某种特定的导航策略来向着目标顶点移动。据分析可知这种上述的这些方法都无法在理论上满足距离标准和召回率标准。

总之，大部分现存算法在距离标准和召回率标准上都没有理论近似保证。在现存工作中，召回率标准只被用于度量实验结果的好坏程度，距离标准则只被少数算法部分地满足。故在文献［67］中提出了将2 个近似标准结合起来的新问题，并提出了针对该问题的算法，通过理论分析，证明了在输入服从泊松点过和的情况下，算法返回的结果能够至少满足其中一个近似标准，并证明了算法的期望预处理时间复杂度为（），期望空间复杂度为（），期望查询时间复杂度为（1）。

4 结束语

在本文中，研究回顾了近邻问题中的全k-最近邻问题、近似最近邻问题及近似k-最近邻问题，主要介绍了这些问题现有算法的时间复杂度。从中可以看出，这些问题的现有算法的时间复杂度都无法达到亚线性，因此在可接受的时间内将无法在PB级大数据上求得计算结果。研究者应该更多关注于亚线性时间算法的设计与分析，从而能够应对大数据时代的高效计算需求。