馬恒釗，李建中，2

（1 哈爾濱工業(yè)大學 海量數(shù)據(jù)計算研究中心，哈爾濱 150001；2 中科院深圳理工大學，廣東 深圳 518107）

0 引言

近年來，大數(shù)據(jù)概念已經(jīng)在研究界和應用界越來越熱門，這也表明大數(shù)據(jù)時代已然來臨。許多應用已經(jīng)開始日常處理起TB 級數(shù)據(jù)，比如廣為人知的TeraSort 應用。而在一些場景、比如科學數(shù)據(jù)中，甚至開始面對PB、以及EB 級數(shù)據(jù)，諸如大型綜合巡天望遠鏡（Large Synoptic Survey Telescope，LSST）每天生成的數(shù)據(jù)量就達到1.25 PB。下面做一個簡單的計算。設想要通過SSD 固態(tài)硬盤來讀取數(shù)據(jù)，目前SSD 的最大讀帶寬約為6 GB/s，于是，僅讀取1 PB 數(shù)據(jù)就需要34.7 h，讀取1 EB 數(shù)據(jù)甚至需要超過4 年時間。這表明，在處理大數(shù)據(jù)時，串行線性算法的運行時間也有可能是不可接受的。如何高效地處理這樣天文級數(shù)量的數(shù)據(jù)，成為理論研究界和應用界共同的挑戰(zhàn)。應用界提出的解決辦法一般是并行化，比如淘寶應對雙十一的海量事務處理請求所用的就是阿里云等并行處理平臺。但是從理論界看來，并行化有以下一些問題：

（1）有些問題是無法高效并行化的。

（2）并行化并不能降低問題的復雜度。

（3）并行化帶來了通信復雜度和通信瓶頸等問題。

（4）這也是最重要的一項，并行化有可擴展性和加速比的問題，即當所使用的處理器數(shù)量達到一定閾值時，再增加處理器將無法降低總運行時間，甚至還有可能會增加總運行時間。因此，理論界解決大數(shù)據(jù)問題所提出的方案是設計亞線性算法，即時間復雜度為（logn）或者（n）的算法，其中0，1。只有設計亞線性算法，才能從根本上降低算法的時間復雜度，減小處理大數(shù)據(jù)所需要的時間。

根據(jù)文獻［5］提出的理論，亞線性算法分為2類。其一為純亞線性算法，即可以直接通過亞線性算法解決的問題；其二為偽亞線性算法，即經(jīng)過一個多項式時間的預處理后，再通過亞線性算法可以解決的問題。前者包括判定數(shù)組是否為ε-far 單調(diào)問題，具體算法參見文獻［6］。后者則包括眾所周知的無序數(shù)組查找問題，即在無序數(shù)組上查找元素，可以通過花費（）時間進行排序，再通過（1）時間的二分查找予以解決。亞線性算法已經(jīng)有接近二十年的研究歷史，最初的研究內(nèi)容集中于屬性測試，后來又拓展至圖算法、計算幾何、代數(shù)計算等領(lǐng)域。參見綜述文獻［11］。這些問題在許多領(lǐng)域都有廣泛的應用，比如生物信息、物聯(lián)網(wǎng)、軌跡分析、機器學習、推薦系統(tǒng)等。然而對于近似最近鄰領(lǐng)域，其亞線性算法的研究卻還未臻充分。本文對該問題的亞線性算法的研究現(xiàn)狀做了綜述。

1 全k-最近鄰問題算法概述

全k-最近鄰問題簡記作All-kNN。關(guān)于此問題的工作最早可以追溯到1983 年，且近年來也一直有關(guān)于此問題的研究工作出現(xiàn)。此問題備受各方關(guān)注的原因，是因為許多應用都以AllkNN 問題作為重要的子程序，比如分類、凝聚式聚類、圖像檢索、推薦系統(tǒng)以及離群點檢測等。在許多類似的應用中，計算All-kNN 都是主要的瓶頸。

由于該問題的重要性，歷史上研究者們提出了許多算法試圖高效地解決All-kNN 問題，這些算法可以分為以下3 類：

（1）第一類算法。使用各種不同的技巧來降低算法的實際運行時間，然而這些算法的最壞時間復雜度仍為（）不變。據(jù)研究分析可知，這些算法大致有3 種算法設計技巧。分述如下。

①第一種，基于樹型的空間索引。如樹和Voronoi 圖等。

②第二種，基于空間填充曲線，包括希爾伯特曲線和Z-order 曲線等?？臻g填充曲線是一類在高維數(shù)據(jù)上建立一維索引的方法，基于空間填充曲線構(gòu)建的索引具有一種重要特性，即在空間上相近的點更容易被分配到相近的索引項中。據(jù)文獻［19，29-30］中的結(jié)果，此性質(zhì)有助于降低計算All-kNN時需要計算距離的次數(shù)。

③第三種，基于近鄰傳播的思想，即近鄰的近鄰仍很有可能是近鄰。NN-descent 算法是提出此思想的開創(chuàng)性工作，且仍是目前All-kNN 問題最好的算法之一。其他使用此思想的算法一般先以某種方法作為預處理，再使用近鄰傳播技巧來提高結(jié)果的精度。例如，文獻［32］中使用隨機分治方法作為預處理，而文獻［33］中使用局部敏感哈希方法作為預處理。

（2）第二類算法。是在并行環(huán)境下解決問題。文獻［34］理論上證明了All-kNN 問題存在并行最優(yōu)算法，該算法在CREW PRAM 模型上需要（）時間和（）個處理器。其他工作則致力于在不同的并行平臺上解決All-kNN 問題，比如MapReduce 平臺和GPU 環(huán)境。

上述算法的最壞時間復雜度上界都為（），第三類算法則不同，現(xiàn)已都被證明了具有更低的時間復雜度，且都是串行算法，與文獻［34］中給出的并行算法也不同。例如，Bentley給出了一種多維分治算法，可以在（（1））時間內(nèi)解決AllkNN 問題，其中是數(shù)據(jù)的維數(shù)。又如，文獻［17］中給出的算法需要（（））時間，其中是輸入數(shù)據(jù)點集中最遠的一對點和最近的一對點的距離之比。再者，文獻［39］中給出的算法聲明具有（kdnlogn）的時間復雜度上界。最后，研究發(fā)現(xiàn)了文獻［39］中算法的一個錯誤，在文獻［40］中給出了嚴格的證明，證明文獻［39］中的算法的下界為（），并提出了新的算法，真正具有（）時間上界。

2 近似最近鄰問題算法概述

近似最近鄰問題，簡記作ε-NN，是一個在理論研究和應用研究方面都很重要、且基礎(chǔ)性的問題，自19 世紀90 年代起就有許多相關(guān)的解決算法被提出，這些算法可以分為4 類，如下所述。

（1）第一類算法，試圖直接解決問題，且這些算法一般都設計了預處理數(shù)據(jù)結(jié)構(gòu)來支持算法的高效運行。Arya 等人研究提出了一種算法，需要1/ε·空間，1/ε·預處理時間以及1/ε·查詢時間。另有研究提出的算法需要（）空 間、（）預處理時間和（/）·查詢時間。Kleinberg 在文獻［14］中提出了2 個算法。其一是確定性算法且達到了（（））查詢時間，使用的數(shù)據(jù)結(jié)構(gòu)需要（（））空間和（（））預處理時間；其二是隨機化算法，預處理時間為（·），所需的空間降至為（·）但其查詢時間卻提升為（·）。

（3）第三類算法，試圖從另一個角度考慮ε-NN問題。算法利用了數(shù)據(jù)的一種內(nèi)生維度，而非原始數(shù)據(jù)所存在的歐氏空間的維度。文獻［17］給出了一個代表性的工作，該文獻中提出的算法的查詢時間復雜度上界為2（1），其中（）為輸入點集的內(nèi)生維度，是的直徑。

在上述3 類算法之外，Indyk 等人開創(chuàng)了第四類算法。這類算法的關(guān)鍵思想在于定義了一個近似近鄰問題，記作（，）-NN，然后將-NN 問題歸約到此問題。于是解決-NN 問題的過程就分為了2 部分，一是解決（，）-NN 問題，二是設計從-NN 到（，）-NN 的歸約。目前，有3 個現(xiàn)存工作設計了從-NN 到（，）-NN 的歸約算法。對此擬做闡釋分析如下。

（1）第一個歸約算法是文獻［18］中提出的，所構(gòu)造的數(shù)據(jù)結(jié)構(gòu)需要（·（））空間，其查詢時間為（）。

（3）第三個算法在預處理階段調(diào)用（，）-NN 算法來構(gòu)造數(shù)據(jù)結(jié)構(gòu)，其查詢時間為（log），此處的指數(shù)（1）來自于算法的常數(shù)成功概率的要求。這3 個現(xiàn)存算法的查詢時間都是比較高的，目前已在文獻［41］中提出了新的圖靈歸約算法，具體查詢時間為（1），低于所有上述現(xiàn)存算法。

3 近似k-最近鄰問題算法概述

近似k-最近鄰問題，簡記作kANN 問題，是近似最近鄰問題的自然推廣，已在許多應用領(lǐng)域都有重要應用，比如數(shù)據(jù)可用性、數(shù)據(jù)庫查詢、以及圖算法等。對于kANN 問題有2 種近似標準，分別稱作距離標準和召回率標準。其中，距離標準要求近似結(jié)果集中的點到查詢點的最遠距離和精確結(jié)果集中的點到查詢點的最遠距離之比不超過給定閾值。召回率標準要求近似結(jié)果集和精確結(jié)果集的交集大小不小于給定閾值。下面將簡要討論現(xiàn)存工作是如何考慮上述2 個近似標準的。

關(guān)于kANN 問題的現(xiàn)存算法可以分為4 類。這里給出探討剖析如下。

（1）第一類算法，是基于樹的方法。這種方法的主要思想是將度量空間遞歸地劃分為子空間，并組織成樹結(jié)構(gòu)。K-D 樹是這種思想的代表性工作，但是這種方法只在低維空間中有效，當維度數(shù)升高時其性能會大幅下降。Vantage point 樹是另一種基于樹的方法，在方法性能上對K-D 樹有所提升。FLANN 方法是最近的工作且在高維空間中有更好的表現(xiàn)，但是卻有可能輸出非最優(yōu)的結(jié)果。據(jù)研究所知，現(xiàn)存的基于樹的方法對距離標準和近似標準都沒有理論保證。

（2）第二類算法，是基于置換的方法。方法的思想是挑選一個樞軸點的集合，并將每個數(shù)據(jù)元素表示成這些樞軸點的一個置換，這個置換是通過將樞軸點按照和數(shù)據(jù)元素的距離排序來得到的。在這種表示方法中，距離較近的數(shù)據(jù)元素的置換表示也相似。利用這種思想的方法包括MI-File和PPIndex。然而，據(jù)分析可知，這些方法也沒能給出對距離標準和召回率標準的理論保證。

（3）第三類算法，是基于局部敏感哈希（Locality Sensitive Hashing，LSH）的方法。LSH 最初由Indyk等人提出，并應用于解決1 時的kANN 問題。不久之后，Datar 等人提出了第一個實用的LSH函數(shù)，此后關(guān)于LSH 的理論和應用研究就大量出現(xiàn)。例如，Andoni 等人證明了基于LSH 的算法的最優(yōu)時空下界，并提出了符合下界的最優(yōu)的LSH 函數(shù)。在應用方面，Gao 等人提出了一種致力于彌合LSH 的理論和kANN 應用的算法?？梢詤⒖几攀鑫墨I［59］。基本的LSH 算法只能在1 的情況下滿足距離標準。一些較晚近的算法有更多的進展。比如C2LSH解決了距離標準下的kANN 問題，但是卻要求近似因子必須是整數(shù)的平方。SRS 算法也是針對距離標準下kANN 問題的算法，但是卻只有部分的理論保證，即只有算法在特定條件下結(jié)束時，返回的結(jié)果才能滿足距離標準。

（4）第四類算法，是基于圖的算法。在這類算法中用到的特殊的圖稱為近似圖，其中的邊是基于頂點之間的幾何關(guān)系定義的?？梢詤⒖几攀鑫墨I［63］。例如，Paredes 等人使用了kNN 圖，Ocsa等人使用的是相對鄰居圖（Relative Neighborhood Graph，RNG），Malkov 等人使用的是可導航的小世界圖（Navigable Small World Graph，NSW）。在這種基于圖的kANN 算法中經(jīng)常用到在近似圖上的導航過程，即選擇圖上的某一個頂點作為起始點，并按照某種特定的導航策略來向著目標頂點移動。據(jù)分析可知這種上述的這些方法都無法在理論上滿足距離標準和召回率標準。

總之，大部分現(xiàn)存算法在距離標準和召回率標準上都沒有理論近似保證。在現(xiàn)存工作中，召回率標準只被用于度量實驗結(jié)果的好壞程度，距離標準則只被少數(shù)算法部分地滿足。故在文獻［67］中提出了將2 個近似標準結(jié)合起來的新問題，并提出了針對該問題的算法，通過理論分析，證明了在輸入服從泊松點過和的情況下，算法返回的結(jié)果能夠至少滿足其中一個近似標準，并證明了算法的期望預處理時間復雜度為（），期望空間復雜度為（），期望查詢時間復雜度為（1）。

4 結(jié)束語

在本文中，研究回顧了近鄰問題中的全k-最近鄰問題、近似最近鄰問題及近似k-最近鄰問題，主要介紹了這些問題現(xiàn)有算法的時間復雜度。從中可以看出，這些問題的現(xiàn)有算法的時間復雜度都無法達到亞線性，因此在可接受的時間內(nèi)將無法在PB級大數(shù)據(jù)上求得計算結(jié)果。研究者應該更多關(guān)注于亞線性時間算法的設計與分析，從而能夠應對大數(shù)據(jù)時代的高效計算需求。