基于多級索引的高維數(shù)據(jù)近似最近鄰搜索

楊鳳麗，李 娜，劉仁芬

(石家莊鐵道大學(xué)四方學(xué)院，河北 石家莊051132)

1 引言

當(dāng)前網(wǎng)絡(luò)平臺上的文本、視頻等多媒體數(shù)據(jù)量持續(xù)上升，例如雅虎網(wǎng)站的日交換信息量高達(dá)30億條，某相簿共享網(wǎng)站包含超過50億張的圖片，且每日仍保持較高的圖片上傳速率。這些數(shù)據(jù)包含很多具有科學(xué)價值與應(yīng)用價值的信息。在此背景下，網(wǎng)絡(luò)海量數(shù)據(jù)的安全維護(hù)極為重要。但是由于此類數(shù)據(jù)具有高維、異構(gòu)等特點，使數(shù)據(jù)的最近鄰查詢成為難點問題[1，2]。

關(guān)于高維數(shù)據(jù)近似最近鄰搜索，很多專家學(xué)者已經(jīng)得到了一些研究成果，例如劉恒等人[3]通過量化編碼實現(xiàn)高維數(shù)據(jù)近似最近鄰搜索，該算法搜索性能優(yōu)越，且時間成本低，但內(nèi)存消耗較大；劉晨赫等人[4]通過動態(tài)網(wǎng)格子空間實現(xiàn)高維數(shù)據(jù)近似最近鄰搜索，該算法復(fù)雜度較低，能有效避免有效數(shù)據(jù)丟失，但數(shù)據(jù)維數(shù)較高時的搜索性能仍不夠理想。

哈希搜索的精確、高效性，使其逐步發(fā)展為近似最近鄰查詢問題的有效方法之一，對于高維數(shù)據(jù)近似最近鄰搜索，距離敏感哈希算法運用廣泛，為優(yōu)化該算法存在的搜索穩(wěn)定性較差問題，引入能將若干索引方法組合使用的多級索引方法，提出基于多級索引的高維數(shù)據(jù)近似最近鄰搜索算法，通過二級距離敏感哈希，實現(xiàn)高維數(shù)據(jù)近似最近鄰搜索。

2 基于多級索引的高維數(shù)據(jù)近似最近鄰搜索算法

2.1 近似最近鄰查詢

近似最近鄰查詢在高維數(shù)據(jù)處理中運用廣泛，數(shù)據(jù)集和查詢點定義同上，近似比率用c描述，且c大于1，該查詢將向量p∈D作為返回結(jié)果，可使dist(p，q)≤c×dist(p*，q)成立，q的最近鄰用p*描述。

2.2 LSH算法

距離敏感哈希(Locality-Sensitive Hashing，LSH)算法是高維數(shù)據(jù)近似最近鄰搜索方面極具代表性的算法，若要檢測出相似數(shù)據(jù)點，可通過任意哈希函數(shù)值使其以極高的幾率出現(xiàn)沖突[5，6]。

哈希函數(shù)在該算法中符合式(1)所示條件，它屬于單向映射函數(shù)

Prh∈H[h(u)=h(v)]=sim(u，v)

(1)

式中，相似度函數(shù)用sim(u，v)∈[0，1]描述；哈希函數(shù)簇用H描述；哈希函數(shù)用h描述，其以均勻方式自H內(nèi)選擇；兩個不同數(shù)據(jù)點用u、v描述；

式(2)描述了利用隨機(jī)投影法獲得的哈希函數(shù)表達(dá)式

(2)

式內(nèi)，矢量用r描述，其各元素符合正態(tài)分布[7]，在超平面內(nèi)，數(shù)據(jù)點u的位置決定著哈希函數(shù)取值，設(shè)定u1、u2表示數(shù)據(jù)點，兩者滿足式(3)所示表達(dá)式

(3)

任意方向矢量用ai描述，以p平穩(wěn)分布為基礎(chǔ)的哈希函數(shù)用{h：Rd→Z}描述，關(guān)于數(shù)據(jù)庫內(nèi)矢量點，通過該哈希函數(shù)將其投影至ai上，該矢量的各元素符合p平穩(wěn)分布，其中，若呈現(xiàn)柯西分布，那么p值為1，若呈現(xiàn)標(biāo)準(zhǔn)高斯分布，那么p值為2。對于兩個變量，如果其線性組合滿足p平穩(wěn)分布，則是在兩者均滿足p平穩(wěn)分布的條件下。{h：Rd→Z}的計算過程用式(4)描述

(4)

式內(nèi)，位于ai上，數(shù)據(jù)點v的投影用ai·v描述；投影窗口的量化寬度用w描述；參數(shù)用b描述，其值符合[0，w]的均勻分布，能極大地提高哈希函數(shù)的隨機(jī)性[8]；取整處理用? 」描述。設(shè)定v1、v2表示數(shù)據(jù)點，兩者滿足式(5)所示表達(dá)式

p(c)=Pr(ha，b(v1)=ha，b(v2))

(5)

設(shè)定hi為單個哈希函數(shù)，由于hi不具備較強(qiáng)的區(qū)分能力，建立如式(6)描述的第二級哈希函數(shù)：

gj(v)={hj，1(v)，…，hj，k(v)}j=1，…，l

(6)

式內(nèi)，對于數(shù)據(jù)點v，其哈希碼為利用k個整數(shù)組建的矢量，LSH函數(shù)簇用G={g：Rd→Zk}描述。

2.3 基于M2LSH的高維數(shù)據(jù)近似最近鄰搜索算法

處理分布不均勻的高維數(shù)據(jù)時，易造成索引文件中的哈希桶所存儲的數(shù)據(jù)出現(xiàn)數(shù)量不均衡現(xiàn)象，導(dǎo)致返回結(jié)果個數(shù)過多或過少，從而影響LSH算法的搜索穩(wěn)定性，因此使用二級距離敏感哈希(M2LSH)實現(xiàn)高維數(shù)據(jù)近似最近鄰搜索，使候選集盡量減少，提升算法的搜索精度和效率。

將索引創(chuàng)建在單個哈希表內(nèi)的步驟用圖1描述。

圖1 創(chuàng)建索引過程

組合哈希向量代表哈希桶，用于放置原始高維數(shù)據(jù)，設(shè)定對象o，對其實施組合哈希處理，并放進(jìn)與gi(o)=〈h1(o)，h2(o)，…，hk1(o)〉匹配的哈希桶內(nèi)。桶寬用w描述，其值較小，將計數(shù)器Counter設(shè)定于各組合哈希桶內(nèi)，能對桶內(nèi)對象數(shù)量進(jìn)行記錄[9，10]。

1)索引創(chuàng)建。

(a)使用哈希桶存儲高維數(shù)據(jù)，以(h1(o)，h2(o)，…，hk1(o)，1)描述各數(shù)據(jù)對象o完成gi(·)操作的形式，通過AND過程，對象o需放置的組合哈希桶號用o′描述，表示為(h1(o)，h1(o)，…，hk1(o))，計數(shù)器用1描述。

(b)若想為合并上步中獲取的組合哈希桶號做準(zhǔn)備，可以通過二次哈希對其進(jìn)行處理并投影至一條線上，利用該操作，能夠重新排列桶號，分配鄰近的哈希桶號至鄰近地點。

關(guān)于索引創(chuàng)建過程，需構(gòu)建的g(·)數(shù)量用i描述，且i=1，2，…，L，各g(·)和索引文件相匹配。

以下為桶合并實現(xiàn)過程：

Input Line (the second hashes)

Compute the AC

Set flag=0

Foreach i=1，…，k2

For j=1，…，length of Sortedlinei

If((count+=getCount(bucketID of linei))/(average count)<ρ&&dist(bucketID of current bucketID)

Flagi[bucketID]=flag

Else

在上述桶合并過程中，AC為高維數(shù)據(jù)總數(shù)與組合哈希桶數(shù)量的比值；待合并桶數(shù)量和AC的比值用ρ描述，通常取值為1.5；待合并桶距離限制用cs描述；二級哈希內(nèi)各線的桶號標(biāo)記用Flagi描述；在0-1范圍中，flag的變動形式用flag描述。

2)搜索階段。

搜索對象用q描述，組合哈希向量用q′描述，可通過一次哈希形成，q′投影到直線的地點，可在實現(xiàn)二次哈希的基礎(chǔ)上獲得，查找直線中和q′擁有同樣標(biāo)記的桶號，并將桶內(nèi)數(shù)據(jù)當(dāng)作搜索對象的候選搜索集合[12]。

(b)桶號o′(〈5，7，3，1〉，100)，表示通過AND過程后q的所得結(jié)果，則無須實現(xiàn)二次哈希，可將該桶內(nèi)數(shù)據(jù)直接當(dāng)作搜索對象的候選集。

(c)如果搜索對象完成一次哈希后，所得桶號內(nèi)僅存在極少的數(shù)據(jù)，且實現(xiàn)二次哈希后，未找到擁有同樣標(biāo)記的其余桶，則是哈希函數(shù)出現(xiàn)問題，利用OR過程即可彌補(bǔ)。

3 結(jié)果分析

高維數(shù)據(jù)一般由視頻、圖片等非結(jié)構(gòu)化數(shù)據(jù)生成，選擇五個大小與維度均存在差異的實際高維數(shù)據(jù)集，以及一個人造數(shù)據(jù)集作為實驗對象，使用本文算法實現(xiàn)高維數(shù)據(jù)近似最近鄰搜索，以驗證該算法的搜索性能，數(shù)據(jù)集詳情用表1描述。

表1 數(shù)據(jù)集詳情

使用近似比率(Ratio)評價搜索算法的性能，它表示近似和真實最近鄰的比值，其值與1越貼近，表明算法的搜索性能越優(yōu)異。

將合并哈希桶數(shù)量設(shè)定成5，哈希桶寬設(shè)定成1，測試不同相鄰?fù)熬嚯x(閾值ρ)下，傳統(tǒng)LSH算法和改進(jìn)的M2LSH算法的高維數(shù)據(jù)近似最近鄰搜索效果，所得Ratio結(jié)果用圖2描述。

分析圖2可以看出，LSH算法和M2LSH算法的近似比率均隨著相鄰?fù)熬嚯x增加而降低；LSH算法的近似比率下降趨勢明顯，最大近似比率約為0.75，當(dāng)相鄰?fù)熬嚯x增加至20時，近似比率已降低至0.21；當(dāng)相鄰?fù)熬嚯x小于等于16時，M2LSH算法的近似比率保持在1左右，當(dāng)相鄰?fù)熬嚯x增加至20時，其最小近似比率與LSH算法的最大近似比率較為接近。對比以上結(jié)果可得，相鄰?fù)熬嚯x對算法的搜索性能影響較大，本文算法優(yōu)化后的高維數(shù)據(jù)近似最近鄰搜索效果大幅度提升，且穩(wěn)定性較好。

選取報表數(shù)據(jù)集完成搜索測試，將其規(guī)模設(shè)定為100，哈希桶寬度設(shè)置為1、2、3、4，分析不同哈希函數(shù)數(shù)量下，各哈希桶寬度對數(shù)據(jù)集搜索近似比率的影響，結(jié)果如圖3。

圖3 哈希函數(shù)數(shù)量和哈希桶寬度對搜索近似比率的影響

分析圖3可以看出，隨著哈希函數(shù)數(shù)量增加，不同哈希桶寬度對應(yīng)的近似比率均呈上升趨勢；在哈希函數(shù)數(shù)量小于12的情況下，近似比率上升速率較快，在超過12后逐漸趨于固定值；當(dāng)哈希函數(shù)數(shù)量為2時，不同哈希桶寬度的近似比率較為接近，當(dāng)哈希函數(shù)數(shù)量小于8時，哈希桶寬度為1的近似比率始終保持最高，當(dāng)哈希函數(shù)數(shù)量大于8時，哈希桶寬度為3的近似比率處于最高數(shù)值，且仍有上升跡象。對比這些數(shù)據(jù)表明，哈希函數(shù)數(shù)量和哈希桶寬度對高維數(shù)據(jù)近似最近鄰搜索具有較大影響，將兩參數(shù)分別設(shè)置為12、3，不僅能獲得更優(yōu)異的搜索效果，還能極大地節(jié)省時間開銷，無需持續(xù)增加哈希函數(shù)數(shù)量。

引入實際搜索代價評價本文算法的搜索能力，其值越低，表明算法的搜索效果越理想。將哈希表數(shù)量分別設(shè)定成2、4、6、8，測試本文算法搜索表1中不同數(shù)據(jù)集獲得的實際搜索代價，結(jié)果用圖4描述。

圖4 不同數(shù)據(jù)集的實際搜索代價

分析圖4可以發(fā)現(xiàn)，在哈希表數(shù)量不斷增長的情況下，使用本文算法搜索不同數(shù)據(jù)集獲得的實際搜索代價均隨之降低，表明增加哈希表數(shù)量能夠提升高維數(shù)據(jù)近似最近鄰搜索效果；當(dāng)哈希表數(shù)量從2增長至6時，各數(shù)據(jù)集對應(yīng)的實際搜索代價下降幅度較大，當(dāng)哈希表數(shù)量從6增長至8時，實際搜索代價下降速率顯著減緩，表明在哈希表數(shù)量增長至一定程度后，對本文算法搜索效果的促進(jìn)作用會逐步減小。

4 結(jié)論

研究基于多級索引的高維數(shù)據(jù)近似最近鄰搜索算法，在原有距離敏感哈希算法的基礎(chǔ)上，提出二級距離敏感哈希算法，實現(xiàn)高維數(shù)據(jù)近似最近鄰精確、穩(wěn)定搜索。

為驗證所提算法的有效性，設(shè)計仿真驗證其應(yīng)用有效性。通過不同參數(shù)的設(shè)定，驗證該算法的搜索效果，以便采取針對性方案優(yōu)化算法整體性能。根據(jù)所得的實驗結(jié)果可知，該算法優(yōu)化后的搜索效果大幅度提升，且穩(wěn)定性較高。且該算法適用性極強(qiáng)，可為各類檢測、辨識、預(yù)警等技術(shù)領(lǐng)域提供借鑒。