張?zhí)煲唬瑥埥芩?/p>

(1. 清華大學(xué)微電子與納電子學(xué)系，北京 100084；2. 大連理工大學(xué)電子信息與電氣工程學(xué)部，遼寧 大連 116024)

1 引言

目前數(shù)據(jù)的存儲(chǔ)工作是通過半結(jié)構(gòu)化路由完成的，同時(shí)存儲(chǔ)對(duì)象為文件，采用文件名或者文件ID進(jìn)行標(biāo)識(shí)，同時(shí)構(gòu)建對(duì)應(yīng)的邏輯拓?fù)浣Y(jié)構(gòu)，并且借助DHT對(duì)關(guān)鍵字進(jìn)行索引[1，2]，利用隨機(jī)哈希函數(shù)將結(jié)構(gòu)化數(shù)據(jù)映射到Overlay Network相同的ID空間中。現(xiàn)階段，在DHT上進(jìn)行關(guān)鍵字索引的技術(shù)還需要進(jìn)一步完善，尤其是無序數(shù)據(jù)的索引更是重中之重。

國內(nèi)外相關(guān)專家針對(duì)結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引方面的內(nèi)容進(jìn)行了大量的研究，例如劉良桂等人[3]根據(jù)類屬性提取關(guān)鍵字，構(gòu)建分組索引，通過分組加密的形式降低索引和查詢請(qǐng)求的加密時(shí)間，獲取各個(gè)組分量的類別信息，更好實(shí)現(xiàn)分組索引。朱慶等人[4]將多模態(tài)場景數(shù)據(jù)抽象為圖的節(jié)點(diǎn)和邊，將稀疏矩陣采用時(shí)空索引的方式進(jìn)行存儲(chǔ)和描述，最終結(jié)合多維樹實(shí)現(xiàn)索引。由于上述兩種方法未能采用模糊聚類算法對(duì)數(shù)據(jù)進(jìn)行分割處理，導(dǎo)致查詢時(shí)間、索引構(gòu)建時(shí)間以及通信開銷上升，查詢準(zhǔn)確率下降等。為了有效解決上述問題，提出一種基于查詢采樣的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引方法，經(jīng)實(shí)驗(yàn)測試證明，所提方法能夠有效提升查詢正確率，同時(shí)還能夠降低查詢時(shí)間、索引構(gòu)建時(shí)間以及通信開銷，以更快的速度完成查詢采樣。

2 結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引方法

2.1 結(jié)構(gòu)化數(shù)據(jù)劃分和樹狀索引結(jié)構(gòu)的建立

采用模糊聚類算法對(duì)全部數(shù)據(jù)進(jìn)行預(yù)處理[5，6]，同時(shí)確保每一個(gè)需要分割的數(shù)據(jù)是通過網(wǎng)格進(jìn)行連通的。其中，算法的詳細(xì)操作步驟如下所示：

1)對(duì)網(wǎng)格模型優(yōu)先進(jìn)行預(yù)處理；

2)計(jì)算網(wǎng)格每對(duì)面片的最短距離權(quán)值Dist(facei，facej)；

3)為不同的面片分配對(duì)應(yīng)的分割片，同時(shí)得到對(duì)應(yīng)的可能性值；

4)計(jì)算模糊分解，同時(shí)將其劃分為三個(gè)部分；

5)在模糊分解中獲取準(zhǔn)確的分界線，將網(wǎng)格劃分為精確的兩部分。

計(jì)算網(wǎng)絡(luò)S中兩個(gè)鄰近面片facei和facej之間的加權(quán)距離Weight(facei，facej)，以此為基礎(chǔ)計(jì)算測地線距離和夾角距離，最終得到兩個(gè)面片之間的最短距離。

計(jì)算相鄰面片facei和facej之間的夾角距離Ang-Dist(αij)，如式(1)所示

Ang-Dist(αij)=η(1-cosαij)

(1)

式中，η代表凹凸面角的取值；αij代表法向量夾角。

接下來計(jì)算相鄰兩個(gè)面片facei和facej之間的測地線距離Geod(facei，facej)

Geod(facei，facej)=dis(centeri，v)+dis(centerj，v)

(2)

式中，v代表公共頂點(diǎn)；centeri和centerj代表面片的中心點(diǎn)。

通過式(1)和式(2)求解出的夾角距離和測地線距離，并計(jì)算對(duì)應(yīng)的加權(quán)處理后距離Weight(facei，facej)，對(duì)應(yīng)的計(jì)算公式為

(3)

式中，avg(Geod)代表全部相鄰面片中全部測地線距離平均值；avg(Ang-Dist)代表全部相鄰平面夾角距離平均值；δ代表夾角距離和測試線距離經(jīng)過加權(quán)后的比重值。

當(dāng)結(jié)構(gòu)化數(shù)據(jù)完成預(yù)處理后，無法直接通過原始模型進(jìn)行連通，首先需要對(duì)原始模型進(jìn)行簡化處理，即網(wǎng)格模型預(yù)處理，詳細(xì)的操作流程如下所示：

1)計(jì)算任意兩個(gè)面片之間的最短路徑Dist(facei，facej)；

2)假設(shè)Dist(facei，facej)的取值存在∞，則說明網(wǎng)格不連通，跳轉(zhuǎn)至步驟3)；假設(shè)不存在∞，則說明網(wǎng)格連通，則繼續(xù)進(jìn)行分割即可；

3)如果網(wǎng)格模型中隨機(jī)兩個(gè)面片是連通的，則說明兩者不在同一網(wǎng)格內(nèi)。

在模糊聚類算法計(jì)算的過程中，選取面片之間距離值Dist(facei，facej)最大的面片，同時(shí)選取一對(duì)代表點(diǎn)采用REPA和REPB表示。通過式(4)和式(5)計(jì)算分割面片SA和SB的可能性值PA(facei)和PB(facei)：

(4)

(5)

通過模糊聚類算法獲取模糊分割結(jié)果[7，8]，進(jìn)而獲取分解模型需要分解的兩個(gè)部分，其中兩部分的邊界都是模糊邊界，將模糊邊界設(shè)定為模糊部分。

設(shè)定p代表分割片patch的面片，進(jìn)行聚類的主要目的就是將面片聚類劃分為兩個(gè)部分，通過式(6)對(duì)其進(jìn)行最小化處理

(6)

式中，pA和pB代表不同的分割片面片。

獲取分解結(jié)果需要優(yōu)先在模糊部分SC區(qū)域構(gòu)建一個(gè)邊界，當(dāng)邊界確定后，則SC中的面片就能夠分配到對(duì)應(yīng)的分割片中。

通過上述分析，主要使用模糊聚類算法對(duì)數(shù)據(jù)進(jìn)行分割[9，10]，并且深入分析全部數(shù)據(jù)的組成結(jié)構(gòu)，得到結(jié)構(gòu)化數(shù)據(jù)的詳細(xì)分布信息。當(dāng)數(shù)據(jù)完成分割處理后，需要借助B+樹構(gòu)建樹狀索引。由于單位為距離，需要對(duì)各個(gè)類別的聚類環(huán)進(jìn)行編號(hào)和排序操作，然后將其放置到B+樹中，以獲取最優(yōu)參考點(diǎn)。

2.2 基于查詢采樣的結(jié)構(gòu)化數(shù)據(jù)分布情況估計(jì)

當(dāng)結(jié)構(gòu)化數(shù)據(jù)被訪問時(shí)，將平均訪問概率設(shè)定為數(shù)據(jù)存儲(chǔ)的重要依據(jù)，然后通過最小聚類環(huán)判定數(shù)據(jù)是否為邊緣數(shù)據(jù)。

為了全面掌握結(jié)構(gòu)化數(shù)據(jù)分布情況和策略索引之間的關(guān)聯(lián)性，采用查詢采樣方法進(jìn)行分析和研究。設(shè)定聚類環(huán)為單位，得到結(jié)構(gòu)化數(shù)據(jù)的平均訪問概率。在此基礎(chǔ)上，進(jìn)一步分析數(shù)據(jù)分布情況對(duì)索引概率的影響，簡化數(shù)據(jù)存儲(chǔ)和掃描流程。

聚類環(huán)可索引能力ICi的計(jì)算公式為

(7)

式中，ci代表第i個(gè)聚類環(huán)，P(ci)代表聚類環(huán)i被訪問的平均概率；Nci代表聚類環(huán)i中全部數(shù)據(jù)的總數(shù)；b代表節(jié)點(diǎn)的數(shù)據(jù)容納量；u代表樹中的節(jié)點(diǎn)總數(shù)；H代表樹中間節(jié)點(diǎn)的高度。

當(dāng)ICi的取值小于或者等于0，則說明聚類環(huán)為邊緣聚類環(huán)，對(duì)應(yīng)的數(shù)據(jù)則為邊緣數(shù)據(jù)。

當(dāng)完成結(jié)構(gòu)化數(shù)據(jù)的分割后建立樹狀索引，以此為依據(jù)構(gòu)建查詢集合Q，利用Q在B+樹中對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行存儲(chǔ)索引，同時(shí)計(jì)算數(shù)據(jù)的平均訪問概率P。其中，聚類環(huán)內(nèi)的數(shù)據(jù)過濾能力和P值存在密切關(guān)聯(lián)，P值越大，則過濾能力越差。另外，聚類環(huán)的可索引能力是通過查詢概率和索引計(jì)算式得到的。最終，還需要通過中心權(quán)限定理以及設(shè)定的置信度控制采樣次數(shù)，確保算法能夠以最快的速度和最少的次數(shù)完成采樣。

各個(gè)聚類環(huán)被訪問的期望主要將聚類環(huán)是否為邊緣環(huán)作為邊緣環(huán)的判定依據(jù)，同時(shí)也能夠完成采樣目標(biāo)的查詢。對(duì)于被訪問概率為p的聚類環(huán)而言，設(shè)定各個(gè)聚類環(huán)中的變量是隨機(jī)且獨(dú)立分布的，在n次采樣過程中，聚類環(huán)被訪問的頻率ηn需要滿足n和p的二次分布條件。結(jié)合中心極限定理，能夠獲取參數(shù)的標(biāo)準(zhǔn)正態(tài)分布。

根據(jù)置信度的查詢采樣控制，需要借助置信度的調(diào)節(jié)實(shí)現(xiàn)采樣頻率和精度兩者的均衡。進(jìn)行查詢采樣的主要目的就是估算不同聚類環(huán)的可索引能力，為了確保估算結(jié)果的準(zhǔn)確性，在計(jì)算時(shí)需要及時(shí)對(duì)樹狀索引結(jié)構(gòu)進(jìn)行修正，確保ICi不會(huì)發(fā)生任何變化，同時(shí)還能夠提前終止采樣，降低采樣數(shù)量。

2.3 結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引

為了有效提升高維數(shù)據(jù)庫的查詢效率，需要通過數(shù)據(jù)的分布情況來選擇合適的索引策略。其中，結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引的組成結(jié)構(gòu)如圖1所示。

圖1 結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引結(jié)構(gòu)圖

為了加快結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)速度和索引效率，需要設(shè)定一個(gè)專門的緩存系統(tǒng)，系統(tǒng)中主要包含一個(gè)用戶跟蹤的緩存幀描述器。同時(shí)，在以塊為單位的存儲(chǔ)系統(tǒng)中，加入B+樹索引，以全面提升檢索效率。

在采用B+樹實(shí)現(xiàn)索引的過程中，需要在原始結(jié)構(gòu)的基礎(chǔ)上增加一些全新的頁結(jié)構(gòu)。其中，新增頁結(jié)構(gòu)也能夠劃分為多個(gè)頁節(jié)點(diǎn)。詳細(xì)的操作過程如下所示：

1)對(duì)各個(gè)分支頁進(jìn)行初始化處理；

2)假設(shè)層數(shù)為1，跳轉(zhuǎn)至步驟3)；

3)假設(shè)當(dāng)前頁有可用空間，則直接插入當(dāng)前頁，同時(shí)輸出分支頁記錄；

4)假設(shè)當(dāng)前頁沒有可用空間，分裂當(dāng)前頁，假設(shè)當(dāng)前頁為根節(jié)點(diǎn)，則樹長高一層，分配一個(gè)全新的根節(jié)點(diǎn)；反之，則跳轉(zhuǎn)至步驟3)；

5)假設(shè)層數(shù)不為1，則跳轉(zhuǎn)至步驟7)；

6)通過當(dāng)前頁和鍵值Key獲取當(dāng)前頁節(jié)點(diǎn)對(duì)應(yīng)子樹的頁號(hào)，利用子樹的頁號(hào)在緩存區(qū)中讀取對(duì)應(yīng)的子節(jié)點(diǎn)；

7)將當(dāng)前層數(shù)減1設(shè)定為全新的輸入值，通過遞歸調(diào)用算法進(jìn)行調(diào)節(jié)，輸出結(jié)果賦值；

8)如果當(dāng)前頁未滿，則直接跳轉(zhuǎn)至步驟2)；

9)假設(shè)當(dāng)前頁已滿，則對(duì)當(dāng)前頁進(jìn)行分裂處理；反之，則跳轉(zhuǎn)至步驟2)。

由于樹型索引具有較強(qiáng)的過濾性能，所以優(yōu)先通過順序掃描方法對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行稀疏處理；然后將全部結(jié)構(gòu)化數(shù)據(jù)自動(dòng)存儲(chǔ)到樹型索引中繼續(xù)進(jìn)行關(guān)鍵字查詢，為后續(xù)的研究奠定一定的理論依據(jù)，同時(shí)也確保查詢結(jié)果的準(zhǔn)確性。

采用最優(yōu)KNN查詢策略對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行檢索時(shí)[11，12]，按照順序?qū)ξ募械娜繑?shù)據(jù)進(jìn)行掃描，確保聚類環(huán)內(nèi)的全部查詢半徑和查詢結(jié)果會(huì)實(shí)時(shí)更新。針對(duì)B+樹索引而言，全部的聚類環(huán)主要通過數(shù)據(jù)距離查詢點(diǎn)的距離長短進(jìn)行排序，并且放置到對(duì)應(yīng)的序列中。同時(shí)還需要進(jìn)一步判定聚類環(huán)區(qū)域和查詢區(qū)域是否相交，假設(shè)兩者是相交關(guān)系，則對(duì)聚類環(huán)內(nèi)的數(shù)據(jù)進(jìn)行搜索，并且在樹狀索引中裁剪出稀疏數(shù)據(jù)，根據(jù)順序搜索策略達(dá)到結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引的目的。

3 仿真研究

為了驗(yàn)證所提基于查詢采樣的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引方法的有效性，需要進(jìn)行仿真測試。

1)結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引構(gòu)建效率測試

在相同的數(shù)據(jù)集中，實(shí)驗(yàn)重點(diǎn)分析采用模糊聚類分解前后的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引構(gòu)建效率變化情況，將索引構(gòu)建時(shí)間設(shè)定為測試指標(biāo)，分析采用傳統(tǒng)聚類算法和模糊聚類算法后的索引構(gòu)建時(shí)間變化情況，如圖2所示。

圖2 傳統(tǒng)聚類和模糊聚類算法的索引構(gòu)建時(shí)間對(duì)比結(jié)果

分析圖2中的實(shí)驗(yàn)數(shù)據(jù)可知，當(dāng)通過傳統(tǒng)聚類算法和模糊聚類算法分別進(jìn)行結(jié)構(gòu)化數(shù)據(jù)分割處理后，其中采用模糊聚類算法后的索引構(gòu)建時(shí)間明顯低于傳統(tǒng)聚類方法，同時(shí)也能夠在查詢過程中有效避免整體聚類搜索，進(jìn)而使所提方法的索引構(gòu)建時(shí)間得到明顯降低，索引構(gòu)建效率大幅度提升。

選取文獻(xiàn)[3]方法和文獻(xiàn)[4]方法作為測試對(duì)象，分析各個(gè)方法的索引構(gòu)建時(shí)間變化情況，詳細(xì)的實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同方法的索引構(gòu)建時(shí)間測試結(jié)果

由圖3中的實(shí)驗(yàn)數(shù)據(jù)可知，當(dāng)數(shù)據(jù)規(guī)模開始持續(xù)增加，各個(gè)方法對(duì)應(yīng)的索引構(gòu)建時(shí)間也開始飛速增加。但是相比另外兩種方法，所提方法的索引構(gòu)建時(shí)間明顯更低一些，充分證明在所提方法中加入模糊聚類算法的可行性和正確性。

2)通信開銷和查詢時(shí)間測試分析

實(shí)驗(yàn)分別模擬三種不同方法在復(fù)雜查詢條件下的通信開銷和查詢時(shí)間變化情況，具體實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 不同方法的通信開銷測試結(jié)果

圖5 不同方法的查詢時(shí)間測試結(jié)果

分析圖4和圖5中的實(shí)驗(yàn)數(shù)據(jù)可知，當(dāng)數(shù)據(jù)集的大小開始增加，三種方法的通信開銷和查詢時(shí)間也開始呈直線上升趨勢。相比另外兩種方法，所提方法的通信開銷和查詢時(shí)間明顯更低一些，充分證明了所提方法的優(yōu)越性。

3)查詢正確率測試分析

為了測試不同方法的可用性，實(shí)驗(yàn)將查詢正確率設(shè)定為測試指標(biāo)，詳細(xì)的實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同方法的查詢正確率測試結(jié)果

分析表1中的實(shí)驗(yàn)數(shù)據(jù)可知，查詢正確率會(huì)隨著失效節(jié)點(diǎn)的增加而降低，而且各個(gè)方法的下降幅度十分明顯。但是相比另外兩種方法，所提方法的查詢正確率還是更高一些。

4 結(jié)束語

為了更好實(shí)現(xiàn)結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引，結(jié)合查詢采樣算法提出一種基于查詢采樣的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)索引方法。經(jīng)實(shí)驗(yàn)測試證明，所提方法能夠有效降低查詢時(shí)間、索引構(gòu)建時(shí)間以及通信開銷，提升查詢準(zhǔn)確率，具有較強(qiáng)的可用性。