張楚涵，張家僑, 馮劍琳

(中山大學數(shù)據(jù)科學與計算機學院，廣東 廣州 510006)

最近鄰檢索是數(shù)據(jù)庫研究的重要問題之一，即查找在數(shù)據(jù)庫D中與查詢對象距離最近的數(shù)據(jù)對象。在數(shù)據(jù)庫中進行圖片相似性搜索、文本相似性搜索、地理空間位置比較等查詢，本質(zhì)上都是要解決最近鄰檢索問題。

PostgreSQL作為業(yè)界內(nèi)第一個吸納KNN(K-nearest neighbor，K最近鄰)技術的數(shù)據(jù)庫系統(tǒng)[1]，為用戶提供了KNN-Gist索引來解決最近鄰檢索問題，但KNN-Gist索引僅適用于如地理信息等低維數(shù)據(jù)。例如，基于KNN-Gist索引實現(xiàn)的圖片相似性檢索的插件ImgSmlr[2]，也只能利用低維的圖片簽名，通過圖片的全局特征進行相似性檢索，無法直接利用高維特征向量進行相似性檢索，當需要避免圖片尺度變化對圖片相似性檢索的影響時，ImgSmlr無法勝任基于尺度不變特征變換(SIFT)的檢索[3]。此外，PostgreSQL還擁有開源的字符串相似性檢索插件pg_trgm[4]，它通過測定字母數(shù)字文本基于三元模型匹配的相似性進行檢索，適用于較小規(guī)模文本、字符串等數(shù)據(jù)。一般情況下，圖片、視頻、文本等信息的特征向量的維度較高，目前，PostgreSQL中還沒有針對高維數(shù)據(jù)的最近鄰檢索的擴展。因此，我們希望為PostgreSQL數(shù)據(jù)庫系統(tǒng)設計并實現(xiàn)一個高效的、支持大規(guī)模、高維度數(shù)據(jù)的最近鄰檢索插件。該插件可以作為一個最近鄰檢索模塊，與圖片、文本或視頻等復雜數(shù)據(jù)對象的特征提取模塊組合，在數(shù)據(jù)庫中實現(xiàn)基于高維特征向量的圖片、文本相似性檢索。

現(xiàn)有的可以精確找到查詢對象的最近鄰的數(shù)據(jù)結(jié)構，如KNN-Gist所使用的樹結(jié)構的檢索性能會隨著數(shù)據(jù)對象維度的升高而急劇下降。在向量維度大于10之后，其性能甚至會低于暴力地線性檢索[5]。 而在很多實際應用場景中，往往不需要檢索查詢對象絕對精確的最近鄰。這使得我們可以一定程度上通過降低檢索精度來提高檢索速度，將最近鄰檢索問題轉(zhuǎn)化為近似最近鄰檢索問題再求解：若查詢對象q與其精確最近鄰o*的距離為r*，那么，c-近似最近鄰檢索就是要找出q的近似最近鄰o，使得q與o的距離小于r*的c倍，其中c為近似比例，且c>1。

位置敏感哈希(Locality-Sensitive Hashing，簡稱LSH)機制[6]及其變體[7-10]是目前解決高維空間中近似最近鄰檢索問題最有效的手段。位置敏感哈希的基本思想是：如果兩個高維特征向量的距離較小，那么，它們就會以較大的概率被哈希到同一個桶中。位置敏感哈希的一個新變體，QALSH機制[11-12]，是目前業(yè)界領先的、有理論保證的高維空間近似最近鄰檢索方法。

與KNN-Gist索引基于樹結(jié)構的最近鄰檢索機制不同，QALSH機制通過解決一系列給定查詢半徑的近似最近鄰檢索問題來求解查詢對象的近似最近鄰：可以發(fā)現(xiàn)，c-近似最近鄰問題的檢索半徑依賴于r*，而r*無法事先確定，因此，近似最近鄰檢索問題無法直接求解。需要將c-近似最近鄰問題轉(zhuǎn)化為一系列檢索半徑r確定的(依次取值1,c1,c2,c3,)近似最近鄰檢索問題，(r,c)-近似最近鄰檢索：對于給定的檢索半徑r和查詢對象q返回一個數(shù)據(jù)對象使得q到該數(shù)據(jù)對象的距離小于或等于cr。

QALSH機制針對外存設計，能夠更好地與數(shù)據(jù)庫系統(tǒng)相結(jié)合。并且，QALSH機制查詢引導的分桶策略和虛擬再哈希技術，使得我們可以在大數(shù)據(jù)集上進行任意檢索半徑r的(r,c)-近似最近鄰檢索。

本文所描述的近似最近鄰檢索插件AKNN-Qalsh就是基于QALSH機制設計并實現(xiàn)的。QALSH機制的檢索性能基本不受數(shù)據(jù)維度的影響，這一性質(zhì)使得AKNN-Qalsh為PostgreSQL提供了高效的針對高維空間的最近鄰檢索功能具有如下特點：

1) 支持大規(guī)模、高維數(shù)據(jù)對象的最近鄰檢索

2) 通用性：可以與圖像、文本、視頻等各種多媒體數(shù)據(jù)的特征提取模塊相結(jié)合，解決多種數(shù)據(jù)對象的最近鄰檢索問題；

3) 檢索速度快：檢索速度遠低于線性檢索；

4) 檢索精度高：檢索精度在用戶可接受范圍內(nèi)，且接近線性檢索結(jié)果，有理論保證；

5) 檢索效率穩(wěn)定：其檢索效率受數(shù)據(jù)維度影響極??；

6) 使用方便：用戶通過直接調(diào)用相應的函數(shù)方法即可在數(shù)據(jù)庫中實現(xiàn)數(shù)據(jù)預處理或近似最近鄰檢索。

1 AKNN-Qalsh的設計與實現(xiàn)

圖1給出了利用AKNN-Qalsh插件進行近似最近鄰檢索的流程，包含預處理和查詢兩個階段：在預處理階段需要在PostgreSQL中構建關系表；在查詢階段，根據(jù)關系表中的信息檢索查詢對象的近似最近鄰。

1.1 數(shù)據(jù)表

在PostgreSQL數(shù)據(jù)庫中，數(shù)據(jù)集中的數(shù)據(jù)對象和查詢對象分別存放在圖2所示的data表和query表中，表中每一行由對象的id和其向量坐標(coordinate)構成。另外，需要在data表的id列上建立Hash索引，使得檢索時能夠在data表中能夠快速地根據(jù)id值取得對應的向量坐標。

1.2 預處理階段

1.2.1 參數(shù)表 QALSH機制需要預先根據(jù)數(shù)據(jù)集中數(shù)據(jù)對象的個數(shù)n、用戶規(guī)定的近似比例c等參數(shù)，確定最近鄰檢索所需的哈希表個數(shù)m以及碰撞閾值l等參數(shù)，這些參數(shù)均需要保存在param表中以記錄該數(shù)據(jù)集的信息。

圖1 AKNN-Qalsh插件整體概述Fig.1 Overview of AKNN-Qalsh

圖2 AKNN-Qalsh插件中的關系表Fig.2Tables of AKNN-Qalsh

表1 param表字段Table 1 Fields of paramTable

為了保證QALSH機制在檢索階段對哈希表的范圍查詢可以高效地完成，需要為每一個哈希表的哈希值的列利用B+樹進行索引。PostgreSQL系統(tǒng)提供的B-Tree索引結(jié)構是根據(jù)B+樹的一種變體，Blink-樹來實現(xiàn)的[13]，恰好可以滿足這一需求。因此，我們直接利用PostgreSQL提供的B-Tree索引為哈希表建立索引，使得AKNN-Qalsh與PostgreSQL系統(tǒng)更好地耦合。

值得注意的是，這種直觀的哈希表結(jié)構在索引過程中將會暴露出缺陷。在實際應用場景下，數(shù)據(jù)集中數(shù)據(jù)對象的個數(shù)n值可能很大，直接對哈希表中的哈希值列建立B-Tree索引時得到的索引結(jié)構比較龐大，而龐大的索引結(jié)構將會導致非?？捎^的空間開銷。并且，由于事先并未對哈希表中的數(shù)據(jù)對象根據(jù)其哈希值進行排序便建立索引，在數(shù)據(jù)庫中，若對該列進行范圍查詢，則其索引指向的表元組是分散在堆文件不同頁面中的，連續(xù)性很差。也就是說，通過范圍查詢獲取滿足條件的元組時，會發(fā)生堆文件頁面的跳躍，引起隨機I/O，也就增加了索引查詢的時間開銷。另外，由于PostgreSQL中B-Tree索引結(jié)構的一個索引元組指向一個索引頁面或表元組。因此，一個葉子節(jié)點索引的數(shù)據(jù)對象非常有限。當利用B-Tree索引進行范圍查詢時，如果滿足條件的數(shù)據(jù)對象較多時，需要讀取的葉子節(jié)點也比較多，也會引起讀取索引時的I/O增加，增加索引掃描的時間開銷。為了解決上述的幾個問題，可以設計一種新的哈希表結(jié)構。

對于索引時頁面跳躍引起隨機I/O的問題，通過事先對哈希表中的數(shù)據(jù)對象按照其哈希值進行排序來解決。而針對B-Tree索引結(jié)構龐大的問題，在利用QALSH機制進行最近鄰檢索時，并不需要粒度(即每個葉子節(jié)點中的一個索引元組索引的數(shù)據(jù)對象個數(shù))為1的B-Tree索引結(jié)構。因此，可以通過調(diào)整B-Tree索引的粒度來控制B-Tree索引的大小?？紤]預先對哈希表中的數(shù)據(jù)對象進行聚簇，設定每個簇中含有的數(shù)據(jù)對象個數(shù)為h，我們稱其為簇的容量。每一個簇的代表哈希值為該簇中所有數(shù)據(jù)對象哈希值的最小值，再以簇為最小單位建立索引，索引的鍵即為簇的代表哈希值，索引的值即為簇中數(shù)據(jù)對象的id。

上述的聚簇策略，在降低樹結(jié)構的深度的同時，也解決了滿足范圍查詢條件的數(shù)據(jù)對象較多時，需要讀取較多個葉子節(jié)點的問題：如果某次范圍檢索中滿足條件的數(shù)據(jù)對象有2 000個，假設B-Tree索引的一個頁面中可以存放100個索引元組，新的哈希索引結(jié)構只需要讀取1個索引葉子頁面即可取到所有滿足條件的數(shù)據(jù)對象，而沒有經(jīng)過聚簇的哈希表結(jié)構則需要讀取20個索引葉子頁面。由此可見，新的哈希表結(jié)構可以減少索引結(jié)構的空間開銷，更重要的是，可以顯著提升索引效率。

1.3 查詢階段

圖3 KNN檢索中的半徑更新與虛擬再哈希Fig.3 Radius update and Virtual Rehashing

圖3為檢索過程中，以某一哈希表為例的半徑更新與虛擬再哈希的示例，其中陰影部分代表每輪檢索的查詢范圍。

AKNN-Qalsh插件在實現(xiàn)基于B-Tree索引的范圍查詢時，利用了PostgreSQL系統(tǒng)提供的一系列索引操作方法，如index_beginscan等，而不是簡單地通過其提供的SPI(server programming interface，即服務器編程接口)，直接利用SQL語句進行查詢。做到了與PostgreSQL系統(tǒng)的緊密結(jié)合，從而進一步提升了檢索效率。

1.4 增、刪、改功能

為了更加貼合數(shù)據(jù)庫擴展應用的需求，AKNN-Qalsh插件還支持增、刪、改三個數(shù)據(jù)庫基本操作。如實現(xiàn)向數(shù)據(jù)集和或查詢集中增加對象的操作，需要將新的對象添加到相應數(shù)據(jù)表、計算其哈希值并更新哈希表。還需要注意param表中的參數(shù)的變化，如數(shù)據(jù)對象個數(shù)n增加等。同樣地，刪除、修改操作與插入操作類似，都需要更新PostgreSQL中相應的關系表。

1.5 用戶接口

前文描述了AKNN-Qalsh插件在運行時生成的數(shù)據(jù)庫表的結(jié)構、預處理部分和查詢部分的實現(xiàn)、以及增刪改三個基本操作的實現(xiàn)。我們希望用戶在使用AKNN-Qalsh插件時，不需要理解或記憶這些實現(xiàn)細節(jié)。因此，我們?yōu)橛脩籼峁┝朔奖愕挠脩艚涌谌绫?所示。

表2 用戶接口Table 2 The interface functions of AKNN-Qalsh

2 實 驗

2.1 數(shù)據(jù)集

本文中將利用Mnist[注]http:∥yann.lecun.com/exdb/mnist、Sift和Gist[注]http:∥corpus-texmex.irisa.fr/、LabelMe[注]http:∥labelme.csail.mit.edu/Release3.0/、P53[注]http:∥archive.ics.uci.edu/ml/datasets/P53+Mutants五個數(shù)據(jù)集進行實驗，數(shù)據(jù)集的信息以及其對應的查詢集信息如表3所示，n記錄了數(shù)據(jù)集中數(shù)據(jù)對象的個數(shù)，d表示數(shù)據(jù)對象的維度，查詢集中查詢對象的個數(shù)為qn。

2.2 性能評測指標

本文以運行時間和平均總體比率作為對比實驗的評估度量，來評估該近似最近鄰檢索擴展程序的性能。兩種度量方式的定義如下。

2.2.1 運行時間(running time) 運行時間記為檢索一個查詢對象q的k個近似最近鄰所用的時間，對數(shù)據(jù)集和查詢集的預處理時間不計入在內(nèi)。本實驗中統(tǒng)計了檢索100個查詢對象的k近似最近鄰所用時間的平均值，并以此作為度量。

表3 數(shù)據(jù)集信息Table 3 The information of dataset

2.3 對比實驗

由于目前PostgreSQL中還沒有針對高維空間的近似最近鄰檢索方法，我們將本文所述的近似最近鄰檢索擴展程序與最基本的線性檢索進行比較。線性檢索計算查詢對象與每個數(shù)據(jù)對象之間的距離，從而找到精確的最近鄰，在實驗中簡記為Linear。

對于不同數(shù)據(jù)集，我們均將參數(shù)c設置為2.0，參數(shù)h統(tǒng)一設置為200。AKNN-Qalsh插件的檢索時間開銷與線性檢索的時間開銷、檢索精度比較如圖4、5所示。可以發(fā)現(xiàn)，AKNN-Qalsh插件的檢索速度遠高于線性檢索方法，且其近似檢索精度的損失在可接受范圍內(nèi)。面對大規(guī)模、高維度的數(shù)據(jù)集時，線性檢索的時間開銷非常大，利用線性檢索在Gist數(shù)據(jù)集中獲取一個查詢對象的Top-100個最近鄰需要近60 s的時間，而利用AKNN-Qalsh插件僅需要1 s。且其查詢結(jié)果的平均總體比率大約為1.07。說明AKNN-Qalsh插件可以在短時間內(nèi)獲取查詢對象的近似最近鄰結(jié)果，還保證了較高的精確度。

圖4 AKNN-Qalsh插件與線性檢索的檢索時間比較Fig.4 The search time of Linear and AKNN-Qalsh

圖5 AKNN-Qalsh插件與線性檢索的檢索精度比較Fig.5 The overall ratio of Linear and AKNN-Qalsh

其實，不同的h值會影響AKNN-Qalsh插件的檢索性能。當h值較小時，B-Tree索引的粒度相對較小時，B-Tree索引結(jié)構較龐大，最近鄰檢索的時間開銷將會很高；h值過大時，B-Tree的索引粒度過大，起不到索引效果，檢索精確度將降低。因此，我們需要為AKNN-Qalsh插件選擇恰當?shù)膆值。上述對比實驗中，針對不用的數(shù)據(jù)集，統(tǒng)一設定了簇的容量為200，是比較好的折中。

3 結(jié) 論

本文詳述了PostgreSQL系統(tǒng)近似最近鄰檢索插件AKNN-Qalsh的設計與實現(xiàn)。該插件借助PostgreSQL數(shù)據(jù)庫的B-Tree索引與Hash索引、以及統(tǒng)一的索引掃描接口，可以高效地支持近似最近鄰檢索。通過真實數(shù)據(jù)集上的密集實驗，我們展示了插件檢索準確率高、檢索速度快的特點。