王 倩,朱 變

大數(shù)據(jù)是云計(jì)算的基礎(chǔ)和核心技術(shù).隨著以博客、微博等新型的社交網(wǎng)絡(luò)的逐漸呈現(xiàn),以及物聯(lián)網(wǎng)等技術(shù)的興起,大數(shù)據(jù)時(shí)代已經(jīng)到來.2008年,Nature推出Big Data專刊[1-5].2011年,Science推出Dealing with Data?？痆6],主要是關(guān)于大數(shù)據(jù)相關(guān)的問題進(jìn)行討論.關(guān)于大數(shù)據(jù)的定義沒有統(tǒng)一的概念.大數(shù)據(jù)的概念比較有代表性的是3V定義[7].還有關(guān)于4V的定義,就是在3V的基礎(chǔ)上增加了新的特性.4V的第4個(gè)V給出的定義也不統(tǒng)一,國際數(shù)據(jù)公司認(rèn)為第4個(gè)V是大數(shù)據(jù)具有價(jià)值性,而IBM認(rèn)為第4個(gè)V應(yīng)該具有真實(shí)性[8].

大數(shù)據(jù)的產(chǎn)生先后經(jīng)歷了3個(gè)階段.第一階段是運(yùn)營式階段,這個(gè)階段是數(shù)據(jù)量的第一次大的飛躍,比如:超市的銷售記錄系統(tǒng)、銀行的交易記錄系統(tǒng)、醫(yī)院病人的醫(yī)療記錄等等,這一階段數(shù)據(jù)的產(chǎn)生方式是被動(dòng)的.第二階段是用戶原創(chuàng)內(nèi)容階段,這個(gè)階段是數(shù)據(jù)量出現(xiàn)的第二次大的飛躍,但是真正數(shù)據(jù)量產(chǎn)生是在Web2.0時(shí)代.第三階段是感知式系統(tǒng)階段,這個(gè)階段是大數(shù)據(jù)產(chǎn)生最根本的原因.隨著技術(shù)的不斷發(fā)展,人們有能力制造帶有處理功能的傳感器,遍布于社會(huì)各個(gè)角落,不斷地產(chǎn)生新的數(shù)據(jù).這一階段數(shù)據(jù)的產(chǎn)生方式是自動(dòng)的.面對(duì)龐大的數(shù)據(jù)資源,如何有效地存儲(chǔ)和高效地查詢這些大數(shù)據(jù)是當(dāng)前要解決的問題.

大數(shù)據(jù)的數(shù)據(jù)類型包括非結(jié)構(gòu)化的、半結(jié)構(gòu)化的和結(jié)構(gòu)化的數(shù)據(jù).按照它的應(yīng)用類型分為三類,海量交易數(shù)據(jù)、海量交互數(shù)據(jù)和海量處理數(shù)據(jù).企業(yè)OLTP(聯(lián)機(jī)事務(wù)處理)應(yīng)用屬于海量交易數(shù)據(jù)類.比如:關(guān)系數(shù)據(jù)庫的增、刪、改和查.傳感器、GPS和Web信息等屬于海量交互數(shù)據(jù)類.企業(yè)OLAP應(yīng)用(聯(lián)機(jī)分析處理)屬于海量處理數(shù)據(jù)類,是數(shù)據(jù)倉庫的核心部分.

圖像、生物信息等領(lǐng)域需要對(duì)大數(shù)據(jù)集進(jìn)行相似性的查詢.大量數(shù)據(jù)將引起較高的查詢代價(jià),所以利用各種索引結(jié)構(gòu)管理特征向量.索引結(jié)構(gòu)分兩種結(jié)構(gòu).第一種是基于順序掃描的索引,它是通過掃描來進(jìn)行估計(jì)文件,比如:VA-File.在國內(nèi),索引結(jié)構(gòu)也有相關(guān)的研究,比如:基于矢量的量化索引方法[9]、基于聚類分解的高維度量空間索引[10]等.第二種是樹狀索引的結(jié)構(gòu),比如,R-Tree,MTree等.

在高維空間中,如果維數(shù)遠(yuǎn)超過10維時(shí),數(shù)據(jù)集的聚集情況變差,樹狀索引效率隨之下降.如果維數(shù)小于10維時(shí),數(shù)據(jù)的聚集強(qiáng),已知的樹狀索引結(jié)構(gòu)已經(jīng)證明了它的有效性.那么,如何解決中等規(guī)模維數(shù)的數(shù)據(jù)(大于10維而小于610維)成為一個(gè)復(fù)雜的問題.

對(duì)此,筆者提出了云環(huán)境下聚類分解的高維數(shù)據(jù)混合索引方法.首先,通過聚類的分解來分割數(shù)據(jù),減少查詢的數(shù)據(jù)訪問;然后,分兩個(gè)階段進(jìn)行單節(jié)點(diǎn)的最近鄰計(jì)算:第一階段,以葉節(jié)點(diǎn)為單位,通過掃描線算法來獲取節(jié)點(diǎn)內(nèi)部所有對(duì)象的局部最近鄰結(jié)果;第二階段,依據(jù)計(jì)算的結(jié)果得出啟發(fā)式的裁剪距離,并采用范圍查詢算法獲取外部的最近鄰對(duì)象.

1 相關(guān)工作

高維數(shù)據(jù)的索引分為兩類.第一類是向量空間的索引,采用類B+-tree的索引結(jié)構(gòu)而進(jìn)行的索引[11],比如:R樹.這種索引的不足是在計(jì)算距離的費(fèi)用昂貴.第二類是度量空間的索引,可以彌補(bǔ)第一類索引存在的不足.這類索引首先要選取距離的參考點(diǎn),依據(jù)數(shù)據(jù)對(duì)象和各參考點(diǎn)計(jì)算距離.然后索引數(shù)據(jù)的對(duì)象,比如:M-tree[12].但這種索引對(duì)樹節(jié)點(diǎn)的利用率較低,影響了M-tree的查詢效率.

無論采用樹狀索引結(jié)構(gòu)還是采用順序索引結(jié)構(gòu)都是屬于單一的索引策略,沒有考慮到數(shù)據(jù)的分布和索引策略之間的關(guān)系.有些學(xué)者將樹狀索引結(jié)構(gòu)和順序索引結(jié)構(gòu)結(jié)合在一起進(jìn)行研究,依據(jù)數(shù)據(jù)分布情況選擇適當(dāng)索引的策略,并進(jìn)行分類:第一類是基于順序索引方法采用樹狀的索引結(jié)構(gòu)[13],不需要掃描所有的壓縮文件.另一類是引入順序掃描方法到樹狀的索引里,比如:2004年,Edgar[14]采用順序掃描的方法對(duì)一部分的數(shù)據(jù)順序掃描,研究結(jié)果表明在高維的承受力上得到了提高.2006年,在高維度量空間索引上,張軍旗等人[10]提出了一種聚類分解的方法,理論證明,該方法是最優(yōu)的分割方法.

2 高維數(shù)據(jù)混合索引

首先,采用Kmeans聚類算法對(duì)數(shù)據(jù)集進(jìn)行更細(xì)致地劃分,并根據(jù)最佳聚類分解數(shù)目進(jìn)行聚類分解.然后,計(jì)算單節(jié)點(diǎn)的最近鄰結(jié)果,此計(jì)算分兩個(gè)階段:第一個(gè)階段,以葉節(jié)點(diǎn)為單位,通過掃描線算法來獲取節(jié)點(diǎn)內(nèi)部所有對(duì)象的局部最近鄰結(jié)果;第二個(gè)階段,依據(jù)計(jì)算的結(jié)果得出啟發(fā)式的裁剪距離,并采用范圍查詢算法獲取外部的最近鄰對(duì)象.

2.1 數(shù)據(jù)劃分

首先,采用Kmeans聚類算法[15],該算法是MacQueen在1967年提出,具體流程如下:

(1)選擇樣本點(diǎn)k個(gè),這k個(gè)樣本點(diǎn)是從樣本數(shù)據(jù)集D里選擇出來的,再將選擇出的樣本點(diǎn)值作初始聚類中心的值;

(2)當(dāng)?shù)趈次迭代時(shí),依次計(jì)算樣本點(diǎn)D中的所有點(diǎn)ptt(=1,…,n)到各個(gè)簇中心ui(j)的歐式距離d t(,i);

(3)根據(jù)第2步計(jì)算結(jié)果找到最小的距離,把最小距離的pt劃入ui(j)距離的最小簇;

(4)對(duì)每個(gè)簇的聚類中心進(jìn)行更新;

(5)對(duì)數(shù)據(jù)集D中的所有樣本點(diǎn)進(jìn)行平方誤差Ei的計(jì)算,得出的結(jié)果再與前一次Ei-1誤差進(jìn)行比較.

然后,采用聚類分解的方法,對(duì)數(shù)據(jù)進(jìn)行更細(xì)致地劃分.高維空間聚類數(shù)據(jù)處的位置是稀疏的,聚類之間的重疊現(xiàn)象比較嚴(yán)重,所以,在查詢效率上大多數(shù)的聚類是不高的.分割數(shù)據(jù)后建立樹狀索引.

采用聚類分解方法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行平均分解:

在各個(gè)聚類環(huán)中數(shù)據(jù)點(diǎn)數(shù)是相同的.當(dāng)數(shù)據(jù)間的距離接近于類似鐘形的分布時(shí),聚類環(huán)內(nèi)外半徑差較大是分布稀疏的數(shù)據(jù),而半徑差較小是分布密集的數(shù)據(jù).如果數(shù)據(jù)距離的分布是接近于均勻的,那么,分解方法采用等同平均分解聚類的半徑.

設(shè)聚類內(nèi)的數(shù)據(jù)點(diǎn)數(shù)用 cluster 表示,各個(gè)聚類需分解的聚類環(huán)數(shù)用m表示,cluster/m為被分解的各個(gè)聚類環(huán)內(nèi)部的數(shù)據(jù)點(diǎn)的個(gè)數(shù),r 1,r 2是表示環(huán)的內(nèi)半徑和外半徑,按聚類中數(shù)據(jù)點(diǎn)的數(shù)量進(jìn)行平均分解的步驟:

第一步 按照升序排列,各個(gè)數(shù)據(jù)點(diǎn)和聚類中心之間的距離,并形成一個(gè)隊(duì)列Q;

第二步 設(shè)內(nèi)半徑ri1=0是第一個(gè)聚類環(huán),第cluster /m個(gè)點(diǎn)與聚類中心之間的距離也就是第一個(gè)聚類環(huán)的外半徑ro1;

第三步 設(shè)第i個(gè)聚類環(huán)的內(nèi)半徑rii=roi-1,在隊(duì)列Q中第i個(gè)聚類環(huán)的外半徑roi就是第i× (cluster/m)個(gè)點(diǎn)和聚類中心之間的距離;

第四步 重復(fù)前三步操作,分出第m個(gè)聚類環(huán)停止操作.

2.2 單節(jié)點(diǎn)最近鄰計(jì)算

首先,建立Hilbert小頂錐,讓根節(jié)點(diǎn)入堆、依次排序來取Hilbert值最小的的節(jié)點(diǎn).假如這個(gè)節(jié)點(diǎn)是內(nèi)部的節(jié)點(diǎn),那么該節(jié)點(diǎn)所有子節(jié)點(diǎn)入堆;如果該節(jié)點(diǎn)不是內(nèi)部節(jié)點(diǎn)而是葉節(jié)點(diǎn),那么內(nèi)部對(duì)象的最近鄰就計(jì)算出來.如果堆是空的話,那么完成了全局最近鄰的計(jì)算.

要計(jì)算葉節(jié)點(diǎn)ζ內(nèi)部對(duì)象的最近鄰,可以分為兩個(gè)階段來完成:第一個(gè)階段,計(jì)算葉節(jié)點(diǎn)ζ內(nèi)部最近鄰和臨近矩陣Mvζ;第二個(gè)階段,Mvζ作為查詢的窗口,利用范圍的查詢得到可能影響最近鄰結(jié)果的外部對(duì)象,并計(jì)算完備性的結(jié)果.

對(duì)于第二個(gè)階段出現(xiàn)問題,做了這樣的處理:

(1)如果葉節(jié)點(diǎn)ζ不與內(nèi)部任一對(duì)象的臨近圓相交,則丟棄.

(2)如果葉節(jié)點(diǎn)ζ與內(nèi)部任一對(duì)象的臨近圓相交,更新相應(yīng)對(duì)象的最近鄰結(jié)果;如果出現(xiàn)多于兩個(gè)或兩個(gè)以上的對(duì)象存在的話,則采用首次獲得的對(duì)象.

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

為了驗(yàn)證所提出的方法具有良好的查詢效率和性能,筆者從兩個(gè)方面進(jìn)行了實(shí)驗(yàn)比對(duì):(1)與單純的聚類法,查詢效率比較;(2)與其他相關(guān)索引,性能比對(duì).

為了保證實(shí)驗(yàn)的正確性,實(shí)驗(yàn)中用到的數(shù)據(jù)集從http://dbgroup.cs.tsinghua.edu.cn/liyan/u_mining.tar.gz下載.實(shí)驗(yàn)所使用硬件系統(tǒng)為2.8 GHz CPU,1G內(nèi)存的計(jì)算機(jī).根據(jù)查詢代價(jià)最小化的聚類數(shù)目得出,對(duì)本數(shù)據(jù)集最優(yōu)的聚類分解總數(shù)為2 268(根據(jù)公式3得出,文獻(xiàn)[10]中已得到證明).

3.1 查詢效率的對(duì)比

與單純的聚類方法相比,隨著數(shù)量的增加,基于聚類分解方法響應(yīng)時(shí)間越來越快.實(shí)驗(yàn)結(jié)果表明,筆者提出的方法具有良好的查詢效率.聚類數(shù)據(jù)分布稀疏,聚類間相互重疊的情況嚴(yán)重,大量的聚類參與查詢導(dǎo)致查詢效率不高.采用聚類分解方法,對(duì)分割數(shù)據(jù)建立樹狀索引,在查詢上有效地避免聚類邊緣相交引起的對(duì)整個(gè)聚類搜索,從而提高了查詢效率,如圖1所示.

3.2 性能比對(duì)

本組實(shí)驗(yàn)選擇有代表性的索引方法:M-tree、順序查找、iDisance進(jìn)行性能方面的實(shí)驗(yàn)分析.圖2所示,M-tree響應(yīng)時(shí)間最慢,順序查找和iDisance在響應(yīng)時(shí)間上是相當(dāng)?shù)?而云環(huán)境下聚類分解的高維數(shù)據(jù)混合索引方法明顯高于M-tree、順序查找和iDisance方法的效率.

圖1 聚類分解與單純的聚類方法的查詢效率對(duì)比

圖2 與其他方法在性能上的比較

4 結(jié)束語

筆者提出了一種基于云環(huán)境下聚類分解的高維數(shù)據(jù)混合索引方法.第一步,采用Kmeans聚類算法對(duì)數(shù)據(jù)進(jìn)行更細(xì)致地劃分;第二步,計(jì)算單節(jié)點(diǎn)的最近鄰.這一步分為兩個(gè)階段完成.實(shí)驗(yàn)分析表明,與單純的聚類方法相比,筆者提出的方法具有良好的查詢效率.與M-tree、順序查找、iDisance相比,基于聚類分解的混合索引方法在復(fù)雜查詢模式下具有良好的負(fù)載均衡.

參考文獻(xiàn):

[1]FOSTER I,YONG ZHAO,RAICUI,et al.Cloud computing and grid computing 360-degree compared[C]//Proceedings of the 2008 Grid Computing Environments Workshop.Washington,DC:IEEE Computer Society,2008:1-10.

[2]ARMBRUSTM,Fox A,GRIFFITH R,et al.Above the clouds:A Berkeley view of cloud computing[EB/OL].http://www.eecs.berleley.edu/Pubs/Techrpts/2009/EECS-2009-28.pdf.2009.

[3]陳康,鄭偉民.云計(jì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào),2009,20(5):1337-1348.

[4]馮登國,張敏,張妍,等.云計(jì)算安全研究[J].軟件學(xué)報(bào),2011,22(1):71-83.

[5]Nature.Big Data[EB/OL].http://www.nature.com/news/specials/bigdata/index.html.2012.

[6]Science.Special online collection:Dealing with data[EB/OL].http://www.sciencemag.org/site/special/-data/,2011.

[7]Grobelnik M.Bigdata computing:Creating revolutionary breakthroughs in commerce,science,and society[R/OL].http://videolectures.net/eswc-2012_grobelnik_big_data/.2012.

[8]Big data[EB/OL].http://en.wikipe-dia.org/wiki/big_data.2012.

[9]Ye HJ,Xu GY.Fast image search using vectorquantization[J].Journal of Software,2004,15(9):1361-1374.

[10]Zhang JQ,Zhou XD,Wang M,Shi BL.Cluster splitting basted high dimensionalmetric space index B+-Tree[J].Journal of saftware,2008,19(6):14011412.

[11]Guttman A.R-trees:A dynamic index structure for spatial searching.In:Youmark B,ed.Pro.of the ACM Int’1 Conf.On Management of Data.Boston:ACM Press,1984:47-57.

[12]Ciaccia P,Patella M,Zezula P.A cost model for similarity queries in metric spaces.In:Proc.of the 17thACM conf.on Principles on Database Systems.New York:ACM Press,1998:59-68.

[13]Berchtold S,Bohm C,Jagadish HV,et al.Independent quantization:An index compression technique for highdimensional data spaces.In:Proc.Of the 16th Int’1 Conf.on data Engineering(ICDE 2000).New Orleans:IEEE Computer Science Society Press,2000:577-588.

[14]Chavez E,Herrera N,Reyes N.Spatial approximation+se-quential scan=efficient metric indexing.In:Proc.Of the XXIV Int’1 conf.Of the Chilean(SCCC 2004).Computer Science Society,2004:121-128.

[15]MacQueen J.In:Proc.Fifth Berkeley Symp.On Math.Statist.And Prob.,Univ.of Calif.Press,1976.