在使用者日常搜尋過程中，一個經常出現的問題即大多數傳回的網站結果擁有完全相同或者幾乎一樣的資訊。而應用了相似性搜尋的相似引擎即可為使用者傳回最恰當、最合适的結果，同時隐藏或者丢棄那些重複的資料。
但是，目前相似性搜尋領域需要克服的難題即它的規模和運作速度。雷鋒網近日了解到，facebook的人工智能研究團隊就稱已在該問題上取得了重要進展。facebook在新釋出的論文《billion-scale
similarity search with gpus》中表示，可在gpu 上實作十億規模級的相似性搜尋，并且已開源該方法。
在處理圖像或視訊等複雜資料時會涉及專用資料庫系統，而相似性搜尋（similarity search）則可以在專用資料庫系統中找尋應用。但問題是，這些複雜資料通常用高維特征表示，而且需要特定的索引結構。
是以，facebook的研究人員就通過更好地利用 gpu的優勢解決了這個問題 。盡管 gpu 擅長資料并行任務，但之前的方法要麼會在并行性不高的算法（如 k-min selection）上遭遇瓶頸，要麼不能有效利用記憶體的層次結構。
為此雷鋒網了解到，他們提出一種可用于k-selection的新設計，使其能以高達性能理論峰值55%
的速度進行運算，并實作了比之前最佳的 gpu 方法快 8.5 倍的最近鄰搜尋。他們為以積量化（product
quantization）為基礎的暴力計算、近似和壓縮域搜尋提出優化設計，進而将其應用到不同的相似性搜尋場景中。在所有這些場景中，該方法比之前的方法的最佳表現還要好，它可在
35 分鐘内從 yfcc100m 資料集的 9500 萬張圖像上建構一個高準确度的 k-nn 圖，也可以在 12 個小時内在 4 個
maxwell titan x gpu 上建構一個連接配接了 10 億個向量的圖。
現在facebook已将該方法（faiss）開源，使大家能進行比較和重複利用。
概括的說，該論文的主要突破有：
給出一個可在gpu上運作的k-selection算法。它可在快速寄存奇儲器中運作，并且其靈活性能使它能與其他核心一起使用。對此我們給出了複雜性分析； 在gpu上實作的為精确和近似的k最近鄰搜尋的近最優算法布局; 通過一系列實驗表明，在單一或多gpu配置中運作的中到大規模的最近鄰搜尋任務上，我們的方法大幅度優于先前技術。
圖檔選自論文（圖檔6）：從 yfcc100m 資料集的 9500 萬張圖像上建構的高準确度 k-nn 圖。第一張和最後一張圖檔為給定圖檔，算法通過計算得出兩張圖檔之間最“和諧”的演變路徑。
開源庫faiss簡介
faiss
是用于有效的相似性搜尋（similarity search）和稠密矢量聚類（clustering of dense
vectors）的庫。它包含了可在任何大小向量集合裡進行搜尋的算法，向量集合的大小甚至可達到ram容納不下的地步。另外，它還包含了用于評估和參數調優的支援代碼。faiss
用 c ++編寫，有 python / numpy 的完整包裝。其中最有用的一些算法則在 gpu 上實作。
包含幾種相似性搜尋的方法。它假定示例可以被表示為向量，并可以通過整數識别。除此之外，這些向量可以與 l2
位距或點積進行比較。與一個查詢向量（query vector）相似的向量是具有最低 l2 位距或最高點積的查詢向量。faiss
還支援餘弦相似性（cosine similarity），因為它屬于标準化向量上的點積。
大多數方法，例如基于二進制向量和緊湊量化代碼的方法，僅使用向量的壓縮表征，并不需要保留原始向量。這通常會降低搜尋的準确性，但這些方法可在單個伺服器上的主存儲器中擴充到數十億個向量。
該
gpu 實作可接受來自 cpu 或 gpu 記憶體的輸入。在一個帶有 gpu 的伺服器上，其 gpu 索引可以被用作其 cpu
索引的插入替換（比如用 gpuindexflatl2 替代 indexflatl2），而且來自或發往 gpu 記憶體的副本可以被自動處理。
faiss的建構
該庫基本上通過 c++ 實作。它帶有可選擇的 gpu （該gpu通過cuda支援）以及一個可選的 python 接口。編譯采用的是makefile。詳細資訊可參見install：
<a href="https://github.com/facebookresearch/faiss/blob/master/install" target="_blank">https://github.com/facebookresearch/faiss/blob/master/install</a>
faiss的工作原理
faiss 是圍繞存儲一個向量集的索引類型（index type）建構的，并且索引類型提供了一個利用 l2 和/或點積向量比較的函數，以使該函數能夠在向量集中進行搜尋。有些索引類型是簡單的基線，如精确搜尋。大多數可用的索引結構都對應以下幾點權衡：
搜尋時間 搜尋品質 每個索引向量使用的記憶體大小 訓練時間 無監督訓練對外部資料的需求
擷取faiss 完整版文檔
完整文檔（包括一個指南）可以參閱 github 的 wiki 頁： http://github.com/facebookresearch/faiss/wiki doxygen 文檔提供了每個類的資訊： 重制本研究論文的結果，可以參考基準 readme
相似性搜尋延伸閱讀
對相似性搜尋不甚了解的同學，可以參看以下由雷鋒網(公衆号：雷鋒網)整理的相似性搜尋的延伸閱讀。
相似性搜尋的分類：
最鄰近搜尋（nearest neighbor search）和範圍查詢（range queries）是相似搜尋的重要子分類，研究人員已針對這兩種分類開發出多種解決方案。
相似性搜尋中存在的問題也是搜尋複雜對象時的固有問題。複雜對象會導緻大多數技術對大範圍集合的抓取能力等問題。而在相似性搜尋時，大部分情況下對象都是複雜的。
相似性搜尋的工作原理：
相似性搜尋工具可用于識别哪些候選要素與要比對的一個或多個輸入要素最相似（或最相異）。相似性的基礎是數值屬性（感興趣屬性）的指定清單。如果指定了一個以上的要比對的輸入要素，相似性将基于每個感興趣屬性的平均值。輸出要素類（輸出要素）将包含要比對的輸入要素以及找到的所有比對的候選要素，這些要素以相似程度排序（由最相似或最不相似參數指定）。傳回的比對數基于結果數參數的值。
相似性搜尋的應用
相似性搜尋在很多場景下都可以發揮它的優勢，比如：
人力資源經理可能想要證明其公司薪資水準的合理性。找出在城市規模、生活成本和便利設施方面相似的城市後，她便可以檢視這些城市的薪資水準，進而确定它們是否與本公司的薪資水準一緻。 犯罪分析師希望搜尋資料庫以檢視某罪行是否屬于較重犯罪形式或有重罪趨勢。 課外健身計劃在 a 城極其成功。計劃提倡者期望找到與其計劃推廣的候選城市具有相似特征的其他城市。 執法機構用此方法揭露毒品種植地或生産地。辨別具有相似特征的地方可能有助于制定未來的搜尋目标。 大型零售商不僅擁有數個成功店鋪，也有少數業績不佳的店鋪。找到一些具有相似人口特征和環境特征（交通便利性、知名度以及商業互補性等等）的地方有助于辨別新店的最佳位置。
本文作者：夏睿