李煥軍

摘 要 本文對(duì)經(jīng)典多維索引技術(shù)SR-Tree在節(jié)點(diǎn)溢出時(shí)使用的分裂方法進(jìn)行了優(yōu)化，針對(duì)其容易導(dǎo)致節(jié)點(diǎn)分裂后的新節(jié)點(diǎn)中存在著大量的互相重疊區(qū)域的問(wèn)題，提出了一種新的基于空間劃分的索引技術(shù)FCSR-Tree，并對(duì)溢出節(jié)點(diǎn)采用效率更高的分裂算法——用聚類(lèi)技術(shù)進(jìn)行“一分為四”的劃分，把重疊區(qū)域的對(duì)象劃分到一個(gè)節(jié)點(diǎn)中去，從而降低了分裂后節(jié)點(diǎn)的重疊現(xiàn)象，減少了kNN檢索時(shí)的多路查找。并在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)中驗(yàn)證了FCSR-Tree的查詢效率。

【關(guān)鍵詞】多維索引 特征選擇 聚類(lèi) kNN檢索

1 引言

多維索引作為對(duì)多維復(fù)雜內(nèi)容的檢索效率進(jìn)行優(yōu)化的一種關(guān)鍵技術(shù)和重要手段，其廣闊的應(yīng)用前景為學(xué)術(shù)界和產(chǎn)業(yè)界所公認(rèn)，一直是研究熱點(diǎn)。SR-Tree是一種經(jīng)典的多維索引技術(shù)，自被提出以來(lái)，在空間數(shù)據(jù)庫(kù)、多媒體、地理信息系統(tǒng)等領(lǐng)域的內(nèi)容檢索中得到廣泛應(yīng)用。

SR-Tree是受SS-Tree和R*-Tree技術(shù)的啟發(fā)而設(shè)計(jì)出來(lái)的一種多維索引技術(shù)。但是與同為空間索引的SS-Tree與R*-tree技術(shù)類(lèi)似，SR-Tree也繼承了基于數(shù)據(jù)劃分的多維索引的缺點(diǎn)：在將大量對(duì)象插入到節(jié)點(diǎn)的過(guò)程中，其節(jié)點(diǎn)溢出時(shí)使用的分裂處理方法容易導(dǎo)致節(jié)點(diǎn)分裂后的新節(jié)點(diǎn)中存在著大量的互相重疊區(qū)域，導(dǎo)致了對(duì)象檢索時(shí)的多路查找，降低了檢索效率。

本文針對(duì)SR-Tree技術(shù)的上述問(wèn)題進(jìn)行優(yōu)化，提出了一種新的基于空間劃分的索引技術(shù)FCSR-Tree，并借鑒了基于空間進(jìn)行劃分的多維索引技術(shù)Quad-Tree[8]的“一分為四”理念，對(duì)溢出節(jié)點(diǎn)設(shè)計(jì)了基于聚類(lèi)技術(shù)的效率更高的分裂處理算法，把重疊區(qū)域的對(duì)象劃分到一個(gè)節(jié)點(diǎn)中去，從而降低了分裂后節(jié)點(diǎn)的重疊現(xiàn)象，減少了檢索時(shí)的多路查找，提升了總體效率。

2 FCSR-Tree的數(shù)據(jù)結(jié)構(gòu)

FCSR-Tree的索引節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)與SR-Tree類(lèi)似，SR-Tree的結(jié)構(gòu)如圖1所示。它采用最小包圍圓形（N維球體）與最小包圍矩形（N維方體）的公共部分來(lái)表示節(jié)點(diǎn)的區(qū)域，同時(shí)具有了SS-Tree與R*-tree的優(yōu)勢(shì)：既有了較小的半徑，可以將數(shù)據(jù)對(duì)象分配到較小直徑的區(qū)域；也具有較小的容積，能夠?qū)?shù)據(jù)對(duì)象分配到有較小的空間容量的區(qū)域中。從而能夠在多維空間中一定程度的避免區(qū)域重疊。

在大量對(duì)象插入的過(guò)程中，節(jié)點(diǎn)之間的嚴(yán)重重疊是不可避免的，從而導(dǎo)致了對(duì)象檢索時(shí)的多路查找。當(dāng)待插入的多維數(shù)據(jù)對(duì)象大量增加時(shí)，會(huì)導(dǎo)致索引的中間節(jié)點(diǎn)的廣度增大的同時(shí)，索引節(jié)點(diǎn)之間的重疊區(qū)域也會(huì)相應(yīng)增大。此時(shí)，若FCSR-Tree仍然采用SR-Tree的查詢算法，查找時(shí)需要訪問(wèn)所有的涉及重疊區(qū)域的索引樹(shù)分枝，但是由于索引分支數(shù)量的增加，會(huì)導(dǎo)致檢索性能急劇下降。

圖2是索引節(jié)點(diǎn)分裂方式的差異的一個(gè)示意圖。從中可以看出，一個(gè)節(jié)點(diǎn)按照左圖的方式進(jìn)行分裂后，分裂得到的兩個(gè)新節(jié)點(diǎn)是不存在重疊區(qū)域的，這意味著在對(duì)這部分?jǐn)?shù)據(jù)進(jìn)行檢索時(shí)，不存在會(huì)導(dǎo)致額外I/O開(kāi)銷(xiāo)的多路查找。而該節(jié)點(diǎn)若按照右圖所示的方式進(jìn)行分裂，分裂后得到的兩個(gè)節(jié)點(diǎn)之間存在這一個(gè)重疊區(qū)域部分，當(dāng)數(shù)據(jù)對(duì)象的特征向量維度較高時(shí)，這種索引節(jié)點(diǎn)之間的重疊區(qū)域面積增長(zhǎng)的更快，使得檢索時(shí)的要搜索更多的分枝數(shù)，增加了多路查找，降低了查詢的處理效率。

3 FCSR-Tree節(jié)點(diǎn)的分裂處理方法

為了解決上一節(jié)中提到的索引節(jié)點(diǎn)分裂導(dǎo)致查詢效率受損的問(wèn)題，本文在實(shí)現(xiàn)FCSR-Tree時(shí)，借鑒多維索引技術(shù)Quad-Tree的“一分為四”理念，對(duì)擬分裂的節(jié)點(diǎn)中的數(shù)據(jù)采用k-Means聚類(lèi)技術(shù)進(jìn)行數(shù)據(jù)劃分，并根據(jù)聚類(lèi)劃分的結(jié)果對(duì)節(jié)點(diǎn)進(jìn)行分裂處理。接下來(lái)，首先對(duì)傳統(tǒng)的節(jié)點(diǎn)分裂方法進(jìn)行剖析，然后再介紹FCSR-Tree的節(jié)點(diǎn)分裂處理策略。

3.1 傳統(tǒng)分裂方法的分析

假設(shè)M是索引節(jié)點(diǎn)中對(duì)象上限，m是節(jié)點(diǎn)中對(duì)象的下限。根據(jù)大量的實(shí)驗(yàn)研究表明，較大的m值可以保證節(jié)點(diǎn)存儲(chǔ)空間的利用率，但是會(huì)限制節(jié)點(diǎn)分裂的合理性。m的值取M的20-40%時(shí)，通常能保證較好的查詢效率與插入效率。此時(shí)既能保持很好節(jié)點(diǎn)利用率，也可以充分的利用了節(jié)點(diǎn)空間利用率。

在傳統(tǒng)處理方式中，當(dāng)需向一個(gè)已包含M個(gè)對(duì)象的節(jié)點(diǎn)N中插入一個(gè)新對(duì)象時(shí)，先不進(jìn)行分裂，而是在索引樹(shù)中同層的其他節(jié)點(diǎn)中進(jìn)行動(dòng)態(tài)調(diào)整，選取N節(jié)點(diǎn)中的一部分對(duì)象重新插入，以推遲節(jié)點(diǎn)的分裂，這樣使得節(jié)點(diǎn)的最小包圍圓形（N維球體）或最小包圍矩形（N維方體）區(qū)域間重疊較小，獲得較高的節(jié)點(diǎn)存貯利用率，有時(shí)還可以避免節(jié)點(diǎn)的分裂。反之，則分裂節(jié)點(diǎn)N。

此時(shí)需將M+1個(gè)對(duì)象分裂到兩個(gè)節(jié)點(diǎn)N和N'中。選擇原N節(jié)點(diǎn)中兩個(gè)最大的點(diǎn)作為新節(jié)點(diǎn)的中心，然后將剩余點(diǎn)分配到距離最近的中心的節(jié)點(diǎn)中。從而實(shí)現(xiàn)兩個(gè)節(jié)點(diǎn)中心的數(shù)據(jù)的方差最小化。

當(dāng)數(shù)據(jù)維度較高時(shí)，溢出節(jié)點(diǎn)分裂之后的二個(gè)新節(jié)點(diǎn)之間容易產(chǎn)生類(lèi)似于圖2所示的重疊區(qū)域，將導(dǎo)致對(duì)該區(qū)域檢索時(shí)需要進(jìn)行多路查找，嚴(yán)重影響檢索效率。根據(jù)分裂后的二部分節(jié)點(diǎn)的劃分面積和/周長(zhǎng)/重疊面積最小的準(zhǔn)則，基于窮舉的思想，羅列出各種一分為二符合要求組合，并從中選取面積和最小的組合，作為分裂策略。但是該算法復(fù)雜度太高，達(dá)到了2M-1，而且隨著節(jié)點(diǎn)數(shù)的增加，耗費(fèi)的時(shí)間將會(huì)呈指數(shù)上升。即使在此過(guò)程中采用近似優(yōu)化，在數(shù)據(jù)量和數(shù)據(jù)維度較高是，效率仍不夠理想。

3.2 FCSR-Tree節(jié)點(diǎn)的“一分為四”分裂策略

本文在FCSR-Tree中提出一種新分裂算法，即將節(jié)點(diǎn)“一分為四”，使得節(jié)點(diǎn)分裂后的新節(jié)點(diǎn)數(shù)目達(dá)到四個(gè)。同時(shí)選取m/M之比為20%到30%之間，在保證了下限時(shí)，還可以根據(jù)實(shí)際的聚類(lèi)劃分，使分裂后的每個(gè)節(jié)點(diǎn)中的對(duì)象數(shù)量具有了一定的適應(yīng)性。通過(guò)上述分裂處理形成四個(gè)節(jié)點(diǎn)，一方面可以使得節(jié)點(diǎn)的重疊區(qū)域劃分在一個(gè)節(jié)點(diǎn)中，減少了數(shù)據(jù)對(duì)象檢索時(shí)的多路查找；另一方面可以使節(jié)點(diǎn)的容量增加，即分裂后的節(jié)點(diǎn)可以可插入的數(shù)據(jù)對(duì)象比“一分為二”的分裂存儲(chǔ)多一倍的條目；最后它縮小了分裂后節(jié)點(diǎn)的覆蓋面積，降低了數(shù)據(jù)區(qū)域發(fā)生重疊的概率。

在對(duì)待分裂的索引節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行聚類(lèi)劃分時(shí)，本文選取了k-means算法，過(guò)將K-means中的k設(shè)置為4，最終將數(shù)據(jù)分為四組，每組數(shù)據(jù)放入分裂后的一個(gè)節(jié)點(diǎn)中。FCSR-Tree的索引節(jié)點(diǎn)分裂流程如下：

（1）節(jié)點(diǎn)數(shù)目達(dá)到M+1或者M(jìn)+2時(shí)，先判斷節(jié)點(diǎn)是否是第一次溢出，如是則調(diào)用重新插入算法，推遲節(jié)點(diǎn)的分裂。反之，則分裂節(jié)點(diǎn)N。

（2）重新插入之后再次發(fā)生節(jié)點(diǎn)的溢出，則節(jié)點(diǎn)需要分裂。從節(jié)點(diǎn)中的M+1或者M(jìn)+2個(gè)數(shù)據(jù)對(duì)象任意選擇四個(gè)對(duì)象的中心作為初始聚類(lèi)中心。

（3）根據(jù)每個(gè)聚類(lèi)對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與四個(gè)中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行較均衡劃分；

（4）重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象）；

（5）迭代第（3）至（4）步直至新的均值與原均值相等或小于指定閾值；

（6）得到四個(gè)數(shù)量較均衡的簇，其中的數(shù)據(jù)劃分到分裂后的四個(gè)索引節(jié)點(diǎn)中。

總的來(lái)說(shuō)，F(xiàn)CSR-Tree節(jié)點(diǎn)的“一分為四”分裂處理算法的核心流程可以用下述偽代碼來(lái)描述。

算法：FCSR-Tree索引節(jié)點(diǎn)分裂算法

輸入：需要進(jìn)行分裂的葉子節(jié)點(diǎn)對(duì)象A

輸出：分裂之后的葉子節(jié)點(diǎn)Bi（i=1，2，3，4）

1. for k=1，…n，

2. 令C（K）為從節(jié)點(diǎn)A中隨機(jī)選取的一個(gè)點(diǎn)；

3. while葉子節(jié)點(diǎn)Bi中有變化發(fā)生 do

4. 應(yīng)用k-Means技術(shù)形成聚類(lèi)；

5. for k=1，….，n do；

6. Bi={X屬于A|A（Ck，x）≤A（Cj，x） 且

對(duì)所有j=1…..k，j≠k}；

7. end；

8. 計(jì)算新的聚類(lèi)中心；

9. for k=1，….，n do

10. Ck=Bi內(nèi)數(shù)據(jù)對(duì)象的均值向量；

11. end；

12. end；

對(duì)于索引的中間節(jié)點(diǎn)，節(jié)點(diǎn)分裂算法在節(jié)點(diǎn)數(shù)目達(dá)到M+1或者M(jìn)+2時(shí)開(kāi)始分裂。中間節(jié)點(diǎn)分裂之后把在聚類(lèi)中心區(qū)域附近的葉子節(jié)點(diǎn)劃分在一起，有利于使距離上相近的葉子節(jié)點(diǎn)成一個(gè)新的中間節(jié)點(diǎn)。這樣分裂后的中間節(jié)點(diǎn)可以更好的進(jìn)行KNN檢索與范圍查詢。

對(duì)于葉子節(jié)點(diǎn)，它的節(jié)點(diǎn)分裂算法是先判斷是否先進(jìn)行重新插入操作，然后再進(jìn)行葉子節(jié)點(diǎn)的分裂。葉子節(jié)點(diǎn)分裂之后，將在聚類(lèi)中心區(qū)域附近的數(shù)據(jù)對(duì)象劃分在一起，使其距離上相近的對(duì)象聚類(lèi)成一個(gè)新的節(jié)點(diǎn)。這樣分裂后的葉子節(jié)點(diǎn)也便于更好的進(jìn)行kNN檢索與范圍查詢?？偟膩?lái)說(shuō)，葉子節(jié)點(diǎn)的分裂處理與中間節(jié)點(diǎn)略有不同，葉子節(jié)點(diǎn)在對(duì)象數(shù)溢出（即對(duì)象數(shù)量為M+1）時(shí)即開(kāi)始進(jìn)行分裂處理。

4 基于FCSR-Tree的kNN檢索

對(duì)于基于FCSR-Tree的kNN檢索，本文采用深度優(yōu)先的策略進(jìn)行處理優(yōu)化，具體說(shuō)明如下：

（1）首先假定查詢點(diǎn)p的最近鄰距離為無(wú)窮大，記作Nearest，在遍歷FCSR-Tree的向子樹(shù)搜索過(guò)程中，對(duì)每個(gè)沒(méi)有被訪問(wèn)過(guò)的新的非葉子節(jié)點(diǎn)，將他們按照最小包圍矩形（N維方體）排序，把結(jié)果保存在活動(dòng)分枝列表（ Active Branch List，ABL）中；

（2）采用SR-Tree的傳統(tǒng)剪枝規(guī)則，對(duì)ABL進(jìn)行修剪，刪除不必要的分枝；

（3）不停的對(duì)ABL 中每個(gè)節(jié)點(diǎn)（包括孩子），遞歸調(diào)用此算法，直到ABL為空；

（4）對(duì)于葉子節(jié)點(diǎn)，由于存儲(chǔ)的是數(shù)據(jù)對(duì)象信息，計(jì)算出其中每個(gè)對(duì)象到查詢對(duì)象p的距離，并更新Nearest。

為了進(jìn)一步優(yōu)化，對(duì)于kNN檢索，我們可以從上述檢索算法上進(jìn)行優(yōu)化擴(kuò)展，即找出k個(gè)距離查詢點(diǎn)p最近的對(duì)象，具體的方法和上述一樣，只是需要增加以下二個(gè)方面：需要一個(gè)緩沖器，用來(lái)存放當(dāng)前k個(gè)最近鄰，并且要把其中的記錄按距離進(jìn)行排序；對(duì)FCSR-Tree各個(gè)子樹(shù)的修剪，要根據(jù)當(dāng)前最近鄰緩沖器中最大距離進(jìn)行。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境和設(shè)置

在本文的實(shí)驗(yàn)中，采用64位操作系統(tǒng)CentOS6.4，內(nèi)存為16 GB，處理器為2.4GHz的Intel Xeon E5645，磁盤(pán)為2TB。實(shí)驗(yàn)中，基于從微軟Bing圖像檢索引擎中獲取的大規(guī)模多媒體數(shù)據(jù)集MSRA-MM 2.0，對(duì)FCSR-Tree與SR-Tree的kNN檢索效率進(jìn)行比較分析。實(shí)驗(yàn)中所用的特征向量數(shù)據(jù)是從MSRA-MM 2.0圖像數(shù)據(jù)級(jí)中抽取的64維HSV顏色直方圖數(shù)據(jù)。數(shù)據(jù)總量為100萬(wàn)，從中隨機(jī)挑選出k（k=20， 50， 100）個(gè)多維特征向量作為查詢集。在實(shí)驗(yàn)中，F(xiàn)CSR-Tree和SR-Tree的索引節(jié)點(diǎn)的頁(yè)面大小均設(shè)置為8KB。

5.2 數(shù)據(jù)量對(duì)kNN檢索性能的影響分析

在此實(shí)驗(yàn)中，將分析數(shù)據(jù)量的大小對(duì)基于FCSR-Tree和SR-Tree索引的kNN檢索的平均響應(yīng)時(shí)間的影響。在實(shí)驗(yàn)中，數(shù)據(jù)量為20萬(wàn)，40萬(wàn)，100萬(wàn)，k固定為100。實(shí)驗(yàn)結(jié)果如圖3所示。

從圖3中可以看到，在執(zhí)行100NN查詢時(shí)，基于本文提出的FCSR-Tree的查詢的響應(yīng)時(shí)間一直是低SR-Tree的，而且隨著數(shù)據(jù)量的增加，在查詢相應(yīng)時(shí)間段增幅上，F(xiàn)CSR-Tree也是由于SR-Tree。主要原因是：

（1）在大規(guī)模多維數(shù)據(jù)集上，采用了基于聚類(lèi)的“一分為四”節(jié)點(diǎn)分裂處理策略的FCSR-Tree所構(gòu)建的索引樹(shù)中的重疊區(qū)域要比SR-Tree少。相應(yīng)的，由此引起的多路查找和性能損耗也少；

（2）在進(jìn)行kNN檢索時(shí)，基于FCSR-Tree的檢索過(guò)程中，采用了基于近鄰隊(duì)列的優(yōu)化擴(kuò)展，進(jìn)一步提升了檢索效率。

5.3 k值對(duì)kNN檢索性能的影響分析

在此實(shí)驗(yàn)中，將分析k的取值對(duì)基于FCSR-Tree和SR-Tree索引的kNN檢索的平均響應(yīng)時(shí)間的影響。在實(shí)驗(yàn)中，數(shù)據(jù)量100萬(wàn)，k的取值為20，50，100。實(shí)驗(yàn)結(jié)果如圖4所示。

從圖4可以看出，盡管隨著k值的增加，SR-Tree的查詢響應(yīng)時(shí)間變化不大，而FCSR-Tree的查詢響應(yīng)時(shí)間變化相對(duì)明顯，但在各種場(chǎng)景下，F(xiàn)CSR-Tree的檢索性能均優(yōu)于SR-Tree?？紤]到SR-Tree和FCSR-Tree在數(shù)據(jù)結(jié)構(gòu)上的相似性，除了構(gòu)建索引時(shí)兩種技術(shù)的節(jié)點(diǎn)分裂處理方式的區(qū)別導(dǎo)致的樹(shù)形結(jié)構(gòu)和數(shù)據(jù)重疊區(qū)域的差異外，這主要是由于FCSR-Tree還額外引入了一個(gè)緩沖隊(duì)列來(lái)對(duì)近鄰對(duì)象進(jìn)行剪枝優(yōu)化。

6 結(jié)語(yǔ)

傳統(tǒng)多維索引技術(shù)的節(jié)點(diǎn)分裂處理方法通常容易促使分裂后的新節(jié)點(diǎn)中形成大量互相重疊的區(qū)域，從而導(dǎo)致對(duì)象檢索時(shí)產(chǎn)生多路查找，檢索效率受損。本文提出并實(shí)現(xiàn)了FCSR-Tree索引，采用聚類(lèi)技術(shù)對(duì)多維數(shù)據(jù)空間進(jìn)行“一分為四”的節(jié)點(diǎn)劃分和分裂處理。FCSR-Tree具有節(jié)點(diǎn)分裂效率高、分裂后的重疊區(qū)域小等優(yōu)點(diǎn)。大規(guī)模真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了FCSR-Tree的效率。

參考文獻(xiàn)

[1]N.Katayama，S.Satoh.The SR-tree：An Index Structure for High-Dimensional Nearest Neighbor Queries[C].Proc. SIGMOD，1997.

[2]張翀，唐九陽(yáng)，戴長(zhǎng)華，肖衛(wèi)東.一種適用于點(diǎn)和區(qū)間混合型維度數(shù)據(jù)集的多維索引[J].國(guó)防科技大學(xué)學(xué)報(bào)，2009，31（03）.

[3]B.Siddhartha，B.Hrishikesh；D. Sourav，K.Goran.Intelligent Analysis of Multimedia Information[M].IGI Global，2016.

[4]羅曉華，鄭扣根，潘云鶴.基于SR-Tree的三維無(wú)級(jí)比例尺GIS空間對(duì)象綜合技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（06）.

[5]D.White，R.Jain.Similarity Indexing with the SS-tree [C].Proc.ICDE，1996.

[6]Y.Manolopoulos，A.Nanopoulos，A. Papadopoulos，Y.Theodoridis.R-Trees：Theory and Applications[M]. Springer，2006.

[7]X.Wu，V.Kumar.The Top the Algorithms in Data Mining [M].CRC Press，2009.

[8]H.Samet.Foundations of Multidimensional and Metric Data Structures[M].Morgan Kaufmann，2006.

＼