AKNN-Qalsh: PostgreSQL系統(tǒng)高維空間近似最近鄰檢索插件*

張楚涵，張家僑, 馮劍琳

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

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

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

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

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

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

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

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

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

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

3) 檢索速度快：檢索速度遠(yuǎn)低于線(xiàn)性檢索；

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

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

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

1 AKNN-Qalsh的設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

1.2 預(yù)處理階段

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

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

圖2 AKNN-Qalsh插件中的關(guān)系表Fig.2Tables of AKNN-Qalsh

表1 param表字段Table 1 Fields of paramTable

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

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

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

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

1.3 查詢(xún)階段

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

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

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

1.4 增、刪、改功能

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

1.5 用戶(hù)接口

前文描述了AKNN-Qalsh插件在運(yùn)行時(shí)生成的數(shù)據(jù)庫(kù)表的結(jié)構(gòu)、預(yù)處理部分和查詢(xún)部分的實(shí)現(xiàn)、以及增刪改三個(gè)基本操作的實(shí)現(xiàn)。我們希望用戶(hù)在使用AKNN-Qalsh插件時(shí)，不需要理解或記憶這些實(shí)現(xiàn)細(xì)節(jié)。因此，我們?yōu)橛脩?hù)提供了方便的用戶(hù)接口如表2所示。

表2 用戶(hù)接口Table 2 The interface functions of AKNN-Qalsh

2 實(shí) 驗(yàn)

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五個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的信息以及其對(duì)應(yīng)的查詢(xún)集信息如表3所示，n記錄了數(shù)據(jù)集中數(shù)據(jù)對(duì)象的個(gè)數(shù)，d表示數(shù)據(jù)對(duì)象的維度，查詢(xún)集中查詢(xún)對(duì)象的個(gè)數(shù)為qn。

2.2 性能評(píng)測(cè)指標(biāo)

本文以運(yùn)行時(shí)間和平均總體比率作為對(duì)比實(shí)驗(yàn)的評(píng)估度量，來(lái)評(píng)估該近似最近鄰檢索擴(kuò)展程序的性能。兩種度量方式的定義如下。

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

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

2.3 對(duì)比實(shí)驗(yàn)

由于目前PostgreSQL中還沒(méi)有針對(duì)高維空間的近似最近鄰檢索方法，我們將本文所述的近似最近鄰檢索擴(kuò)展程序與最基本的線(xiàn)性檢索進(jìn)行比較。線(xiàn)性檢索計(jì)算查詢(xún)對(duì)象與每個(gè)數(shù)據(jù)對(duì)象之間的距離，從而找到精確的最近鄰，在實(shí)驗(yàn)中簡(jiǎn)記為L(zhǎng)inear。

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

圖4 AKNN-Qalsh插件與線(xiàn)性檢索的檢索時(shí)間比較Fig.4 The search time of Linear and AKNN-Qalsh

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

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

3 結(jié) 論

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