近鄰問題的亞線性算法研究現(xiàn)狀綜述

馬恒釗，李建中，2

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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