FCSR—Tree：一種面向節(jié)點分裂優(yōu)化的多維索引技術

李煥軍

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

【關鍵詞】多維索引 特征選擇 聚類 kNN檢索

1 引言

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

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

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

2 FCSR-Tree的數(shù)據(jù)結構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（4）重新計算每個（有變化）聚類的均值（中心對象）；

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

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

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

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

輸入：需要進行分裂的葉子節(jié)點對象A

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

1. for k=1，…n，

2. 令C（K）為從節(jié)點A中隨機選取的一個點；

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

4. 應用k-Means技術形成聚類；

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

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

對所有j=1…..k，j≠k}；

7. end；

8. 計算新的聚類中心；

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

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

11. end；

12. end；

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

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

4 基于FCSR-Tree的kNN檢索

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

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

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

（3）不停的對ABL 中每個節(jié)點（包括孩子），遞歸調用此算法，直到ABL為空；

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

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

5 實驗結果與分析

5.1 實驗環(huán)境和設置

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

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

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

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

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

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

5.3 k值對kNN檢索性能的影響分析

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

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

6 結語

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

參考文獻

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

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

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

[4]羅曉華，鄭扣根，潘云鶴.基于SR-Tree的三維無級比例尺GIS空間對象綜合技術[J].計算機學報，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.

＼