如果你打算開一家咖啡館，你一定想知道：“附近最近的一家咖啡館在哪？”了解這些信息有助于應(yīng)對商業(yè)競爭。

這種現(xiàn)象是計算機科學(xué)中廣泛研究的問題，稱為“最近鄰搜索”。它的問題是，給定數(shù)據(jù)集和新的數(shù)據(jù)點，數(shù)據(jù)集中哪個數(shù)據(jù)離新數(shù)據(jù)點最近？這個問題出現(xiàn)的場景非常豐富，可以是基因搜索、圖像查詢，或者音樂推薦。

但是最近鄰問題并不像咖啡館那么容易解決。過去幾十年，很多計算機科學(xué)家都在致力于尋找更好的解決辦法。與此同時，他們還要解決隨之而來的復(fù)雜情況，例如不同數(shù)據(jù)集對“相近”有著不同的定義。

現(xiàn)在，一個五人小組提出了開創(chuàng)性的解決辦法，他們在兩篇論文中（一篇已于4月發(fā)表，另一篇還未出爐）提出了解決復(fù)雜數(shù)據(jù)最近鄰問題的通用方法。

麻省理工學(xué)院的計算機科學(xué)家、最近鄰搜索領(lǐng)域的重要任務(wù)Piotr Indyk表示：“這是首個用單一算法捕捉大量空間的結(jié)果?！?/p>

不同的距離

我們已經(jīng)習(xí)慣了用一種方法定義距離，常常會忽視其他方式。通常，我們用“歐幾里得距離”測量距離，即在兩點之間測量直線的距離。但在有些情況下，這樣的測量方式就說不通了。例如在街道網(wǎng)格中，就需要用到“曼哈頓距離”了，直線距離5英里的目的地，可能需要走3英里之后轉(zhuǎn)90°，再繼續(xù)走4英里才能到達。

另外，還可以用非地理的術(shù)語表示距離。比如Facebook上的兩名用戶、兩部電影、兩組基因之間的距離怎么計算？在這些問題上，“距離”表示的是兩個物體之間的相似程度。

有關(guān)距離的測量尺度有很多，例如兩組基因，生物學(xué)家會用“編輯距離（edit distance）”來比較二者。這樣一來，兩組基因序列之間的距離就是從一組基因轉(zhuǎn)換到另一組所需要添加、刪除、插入、替換的數(shù)字。

編輯距離和歐幾里得距離是兩種完全不同的距離測量方法，二者是不能相互替代的。但是這樣的情況對研究最近鄰算法的科學(xué)家們來說很棘手，能有效計算一種距離的算法在另一種情況下就無法工作了。

在夾縫中求生存

為了找到最近鄰，通常所用的方法是將數(shù)據(jù)分成好幾份。假設(shè)你的數(shù)據(jù)就像在牧場中吃草的奶牛，給分散在草場中的牛群畫不同的圓圈，現(xiàn)在進來了一頭新奶牛，問它會落在哪個圓圈里？可以肯定的是，這頭新奶牛的最近鄰一定也在這個圈里。

然后重復(fù)這一過程，不斷進行細分。最終會得到一個只包含兩頭牛的區(qū)域，這樣就找到了最近鄰。

現(xiàn)在，算法能夠完成這一過程，好的算法還會將這一任務(wù)完成得又快又好。這里“好”的標準可以理解成，算法不會得出最近鄰與新數(shù)據(jù)不在一個圈子里的結(jié)果。

近些年來，科學(xué)家們提出了多種分割數(shù)據(jù)的算法。對于低維數(shù)據(jù)（即每個數(shù)據(jù)點僅由少量的值定義，例如牧場中牛的位置），算法在解決最近鄰問題時會生成Voronoi圖。

對于高維數(shù)據(jù)（每個數(shù)據(jù)點可能有成百上千個值），Voronoi圖要計算起來就十分費力了。所以科學(xué)家們用“局部敏感哈希（LSH）算法”對數(shù)據(jù)進行分割，這種算法于1998年由Indyk和Rajeev Motwani共同提出。LSH算法是隨機對數(shù)據(jù)進行分類的，這使得它速度很快，但精確度較低。算法最終并不是找到確切的最近鄰點，而是告訴你最近鄰與已有數(shù)據(jù)的確切距離。（可以想象成在電影推薦時，推薦結(jié)果并不是最佳的，而是那些還不錯的。）

上世紀90年代末，計算機科學(xué)家們提出的LSH算法以特殊的距離尺度對最近鄰問題給出大致的解決方案。這些LSH算法都非常具體，無法通用。

“你可以為歐幾里得距離或曼哈頓距離設(shè)計非常高效的算法。但是我們沒有一種技術(shù)能在多種距離上通用，”Indyk說道。

受制于這種困境，科學(xué)家們想了一種應(yīng)變方法：通過嵌入，在沒有好的算法的距離標準之上“覆蓋”一種距離尺度。但是這樣的結(jié)果往往不準確，有的時候嵌入根本無法完成。所以他們?nèi)孕枰氤鲆环N合適的通用方法。

驚人的結(jié)果

在這項新研究開始之際，科學(xué)家們回過頭思考當初具體的最近鄰算法追求的目標是什么。他們提出了一個更寬泛的問題：對距離尺度來說，阻礙一款好的最近鄰算法出現(xiàn)的原因是什么？

他們想原因可能與在尋找最近鄰時復(fù)雜的“擴展圖（expander graph）”有關(guān)。擴展圖是一群由線條連接起來的點。這些圖都有它們自己的距離尺度，圖中兩點之間的距離是你從一點到另一點所經(jīng)過的最少線段?？梢詫⑵湎胂蟪缮缃痪W(wǎng)絡(luò)中的各種人脈關(guān)系。

擴展圖有兩個明顯矛盾的特點：它聯(lián)系廣泛，所以如果想切斷與某一點的聯(lián)系，就要切斷之間的線段。但同時，大多數(shù)點都和其他的點相連。所以，最終有些點會越來越遠。

這樣的特征造成的結(jié)果是，在擴展圖上可以很快地進行最近鄰搜索，而將數(shù)據(jù)點分割的過程可以看成將最近的兩點分開。

“任何分割擴展圖的方法都會切斷很多線，分開很多相近的點，”論文作者之一Waingarten說道。

從左至右：Alexandr Andoni、Ilya Razenshteyn、Erik Waingarten

2016年夏天，Andoni、Nikolov、Razenshteyn和Waingarten認為，是不可能存在對最近鄰算法有效的擴展圖的。但他們真正想證明的是，好的最近鄰算法同樣也不存在于其他距離尺度中。

他們證明的方法是在這些距離尺度中嵌入擴展尺度。這樣一來，他們可以確定這些尺度有類似擴展圖的無法工作的特征。

這四位科學(xué)家找到普林斯頓大學(xué)的Assaf Naor，他是一名數(shù)學(xué)家，同時也是計算機科學(xué)家，此前的研究非常適合回答有關(guān)擴展圖的問題。他們詢問了有關(guān)擴展圖嵌入到其他距離類型中的問題，但答案并非所期望的那樣，Assaf給出了完全相反的回答。

Naor證明，擴展圖并不能嵌入到多種距離尺度中，研究者將這一論斷作為基礎(chǔ)，接著這個邏輯鏈條開始思考：如果擴展圖不能嵌入到其他尺度，那么一個好的數(shù)據(jù)分割方法一定存在（因為他們證明擴展圖的特征是阻礙良好數(shù)據(jù)分割的障礙）。因此，良好最近鄰算法可能存在。

他們將發(fā)現(xiàn)結(jié)果寫在第一篇論文中，而第二篇論文本月也即將發(fā)表。Waingarten表示：“第一篇論文證明了確實存在一種方法能良好地進行數(shù)據(jù)分割，但沒有給出如何快速完成的方案。在第二篇論文中會詳細解釋。”

同時，這項新研究第一次用通用的方法對高維數(shù)據(jù)進行最近鄰搜索?！叭魏纬叨瓤臻g都可以用該算法實現(xiàn)最近鄰搜索，”Waingarten說。