MapReduce框架下的優(yōu)化高維索引與KNN查詢

梁俊杰,李鳳華,劉瓊妮,尹 利

(1.湖北大學(xué)計算機與信息工程學(xué)院,湖北武漢 430062;2.中國科學(xué)院信息工程研究所信息安全國家重點實驗室,北京 100093;3.北京電子科技學(xué)院,北京 100070)

?

MapReduce框架下的優(yōu)化高維索引與KNN查詢

梁俊杰1,李鳳華2,3,劉瓊妮1,尹 利1

(1.湖北大學(xué)計算機與信息工程學(xué)院,湖北武漢 430062;2.中國科學(xué)院信息工程研究所信息安全國家重點實驗室,北京 100093;3.北京電子科技學(xué)院,北京 100070)

針對大規(guī)模高維數(shù)據(jù)近似查詢效率低下的問題,利用MapReduce編程模型在大規(guī)模集群上的數(shù)據(jù)與任務(wù)的并行計算與處理優(yōu)勢,提出MapReduce框架下大規(guī)模高維數(shù)據(jù)索引及KNN查詢方法(iPBM),重點突破MapReduce數(shù)據(jù)塊(block)的優(yōu)化劃分與各數(shù)據(jù)塊對計算的共同貢獻兩大難題,利用兩階段數(shù)據(jù)劃分策略并依據(jù)相關(guān)性與并行性原則將數(shù)據(jù)均勻分配到各數(shù)據(jù)塊中,設(shè)計分布式的雙層空間索引結(jié)構(gòu)與并行KNN查詢算法,檢索時利用全局索引、局部索引與二維位碼索引實現(xiàn)三層數(shù)據(jù)過濾,大幅縮小搜索范圍并降低高維向量計算代價,實驗表明iPBM對大規(guī)模高維數(shù)據(jù)的近似查詢具有準確性、高效性和擴展性.

云計算;MapReduce;KNN查詢;高維索引

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.015

1 引言

隨著下一代互聯(lián)網(wǎng)、物聯(lián)網(wǎng)和云計算[1]等信息技術(shù)的創(chuàng)新發(fā)展和重點應(yīng)用,用戶面臨海量數(shù)據(jù)或大數(shù)據(jù)諸多挑戰(zhàn),很多領(lǐng)域數(shù)據(jù)呈現(xiàn)高維表現(xiàn)形態(tài),如金融交易數(shù)據(jù)、多媒體數(shù)據(jù)、航天數(shù)據(jù)、生物數(shù)據(jù)等,維度高達幾十維甚至上百維.高維空間數(shù)據(jù)應(yīng)用常見以近似查詢(similarity query)為主,如何提高大規(guī)模高維數(shù)據(jù)近似查詢效率已成為學(xué)術(shù)界的研究熱點.

為適應(yīng)大數(shù)據(jù)使用管理需求,Google公司提出了MapReduce計算模型[2,3],將運行于大規(guī)模集群上的復(fù)雜并行計算過程高度地抽象為兩個函數(shù):Map和Reduce.一個Map/Reduce作業(yè)(Job)通常會把輸入的數(shù)據(jù)集切分為若干獨立的數(shù)據(jù)塊,由Map任務(wù)(Task)以完全并行的方式處理它們,結(jié)果輸入給Reduce任務(wù).MapReduce框架由一個單獨的Master和集群節(jié)點上的Slave共同組成.Master負責(zé)調(diào)度構(gòu)成一個作業(yè)的所有任務(wù),這些任務(wù)分布在不同的slave上.這種框架的設(shè)計可以充分利用整個集群的網(wǎng)絡(luò)帶寬,同時保障了系統(tǒng)可靠性和容錯性,是目前云計算環(huán)境的核心計算模式.

高效的數(shù)據(jù)存取策略是提高高維數(shù)據(jù)查詢性能的關(guān)鍵,為了避免不必要的數(shù)據(jù)存取普遍做法是利用索引技術(shù).在大數(shù)據(jù)時代,如何將高維索引技術(shù)和并行計算模型有機結(jié)合是一個新的研究方向,最近幾年針對云計算環(huán)境下的索引技術(shù)研究受到學(xué)者的廣泛關(guān)注[4～8].Dittrich等人分別在2010年和2012年VLDB會議上提出了Hadoop++[9]和HAIL[10].Hadoop++系統(tǒng)使用了一種稱為Trojan的索引結(jié)構(gòu),將描述輸入片段(input splits)的索引信息寫入片段中,在一個片段中可以有多個局部索引(partial index),每個局部索引只描述片段中部分數(shù)據(jù)信息,在這些局部索引中有一個主索引(primary index),查詢時根據(jù)需要查找相應(yīng)的索引.Trojan索引的創(chuàng)建過程是在數(shù)據(jù)加載階段完成,因此不影響查詢效率.HAIL是為縮短Hadoop++索引構(gòu)造時間,對每個Hadoop備份數(shù)據(jù)創(chuàng)建了一個聚類索引,檢索時選擇最佳的索引而提高查詢效率.Hadoop++和HAIL都是在Hadoop默認的數(shù)據(jù)塊劃分基礎(chǔ)上建立索引,需要進一步考慮查詢需求和數(shù)據(jù)分布對數(shù)據(jù)劃分的影響.Eltabakh等人對Hadoop進行擴展提出了CoHadoop[11],定義文件級屬性(file-level property)概念稱為locator,在NameNode上新增一個locator數(shù)據(jù)表,將locator屬性值相同的文件存儲到同一個DataNode上,達到將相關(guān)數(shù)據(jù)存儲在同一節(jié)點上的目的,但是如何實現(xiàn)系統(tǒng)自動判斷兩個文件是否相關(guān)是CoHadoop的難點.Zaschke發(fā)表在2014年SIGMOD會議上的論文,描述了一種多維數(shù)據(jù)存儲和索引結(jié)構(gòu)稱為PH樹[12],為減少存儲空間在索引結(jié)構(gòu)中共享二進制描述前綴,PH樹支持點查詢和范圍查詢時快速數(shù)據(jù)存取,但PH樹如何擴展到MapReduce框架有待進一步研究.文獻[13～15]是在MapReduce框架的計算節(jié)點上建立局部B+-Tree、R-Tree或四叉樹索引,并基于局部索引構(gòu)造全局索引,查詢時依據(jù)查詢模型動態(tài)選擇合適的索引,這些方法都是基于MapReduce默認的數(shù)據(jù)劃分無法保障數(shù)據(jù)塊對計算共同貢獻.Wei等人提出了基于Voronoi圖數(shù)據(jù)劃分的knnJ查詢的MapReduce算法,將不同Voronoi圖的對象分配到不同的組內(nèi),但是算法效率對Voronoi圖支點選擇策略具有很強的依賴性[16].Doulkeridis等探討了利用MapReduce處理Top-K查詢的一些基本問題,但是缺少對問題的深入分析和實驗驗證[17].國內(nèi),劉義等人在2013年發(fā)表論文[18,19],提出了一種采樣算法以快速確定空間劃分函數(shù),構(gòu)建了符合MapReduce計算模型的索引結(jié)構(gòu),并利用分布式R-樹索引實現(xiàn)K-近鄰連接查詢,該方法主要限定于地理空間的knnJ查詢,沒有測試高維空間對算法性能的影響.

針對目前鮮有人研究MapReduce框架下的高維數(shù)據(jù)索引及KNN檢索方法[20],MapReduce框架自身缺少數(shù)據(jù)分塊劃分優(yōu)化策略以及無法保證每個數(shù)據(jù)分塊對計算共同貢獻的缺陷,本文提出了一種新的MapReduce框架下的高維索引(Index Partition Bitcodes in MapReduce,簡稱iPBM).充分利用MapReduce框架在大規(guī)模集群上的數(shù)據(jù)和任務(wù)的并行計算與處理能力,基于高維數(shù)據(jù)分布和近似查詢特點優(yōu)化高維空間數(shù)據(jù)塊的劃分機制,設(shè)計可擴展的、分布式的雙層空間索引以及KNN并行查詢算法,檢索過程實現(xiàn)了數(shù)據(jù)快速篩選避免了大量數(shù)據(jù)無效計算,實驗表明iPBM在提高高維數(shù)據(jù)查詢效率和擴展性方面都具有明顯優(yōu)勢.

2 問題描述和背景知識

為了簡化問題闡述,本文引用的符號和含義如表1所示，并作如下合理的假設(shè):

(1)針對分析型應(yīng)用環(huán)境,數(shù)據(jù)集相對穩(wěn)定.因此,索引只需一次構(gòu)建,用于多次查詢.

(2)MapReduce始終保持負載均衡,當(dāng)數(shù)據(jù)量發(fā)生變化時,MapReduce可以適當(dāng)增加或減少服務(wù)器數(shù)量或者調(diào)整配置參數(shù).

(3)高維向量相似性用相應(yīng)的空間點距離來表示.不失一般性,本文采用歐氏(Euclidean)距離.

(4)文中以KNN查詢?yōu)槔榻B高維數(shù)據(jù)近似查詢實現(xiàn)過程,其他種類的近似查詢可以依此類推,限于篇幅不做詳述.

表1 相關(guān)符號描述

定義1 KNN查詢 假設(shè)高維向量對象集DS={P1,P2,…,Pn},查詢點Q,則KNN查詢返回DS中與Q距離最近的k個對象,并按距離升序排列:KNN(DS,Q,k)={Pr,Pt,…,Ps|Pr,Pt,Ps∈DS}.

3 MapReduce框架下的高維索引

iPBM是在MapReduce的開源框架Hadoop平臺下實現(xiàn)的,KNN查詢分為兩個階段:

(1)索引構(gòu)建階段:對海量高維數(shù)據(jù)進行聚類和分區(qū)劃分,針對Master和Slave分別設(shè)計不同的索引結(jié)構(gòu).(2)KNN查詢階段:利用雙層索引確定候選點對象集和任務(wù)劃分,執(zhí)行并行KNN查詢.

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

MapReduce框架由一個提供元數(shù)據(jù)服務(wù)的Master節(jié)點和若干個提供存儲的Slave節(jié)點組成,適合大規(guī)模數(shù)據(jù)并行計算和任務(wù)處理.為了適應(yīng)這種機制,創(chuàng)建索引之前有必要對數(shù)據(jù)集進行必要的預(yù)處理,使得數(shù)據(jù)應(yīng)盡可能均勻地劃分到多個數(shù)據(jù)塊中,并對最終結(jié)果均有貢獻.

3.1.1 聚類劃分

數(shù)據(jù)劃分首先是對數(shù)據(jù)集DS進行聚類分析.不失一般性,我們采用K-means聚類方法[21]對d維空間數(shù)據(jù)進行全局分析,得到數(shù)據(jù)簇C={C1,C2,…,Cm}及質(zhì)心O={O1,O2,…,Om}.

3.1.2 分區(qū)劃分

數(shù)據(jù)空間聚類劃分后,對各個數(shù)據(jù)簇按其數(shù)據(jù)分布特征做進一步的分區(qū)劃分,得到數(shù)據(jù)簇的分區(qū)AS={A1,A2,…,A2d}.為方便描述,本文將數(shù)據(jù)簇質(zhì)心作為簇的參考點用于計算分區(qū)和點對象的位碼索引值,也可以選擇其他點作為參考點.

定理1 劃分分區(qū)的維數(shù) 假設(shè)數(shù)據(jù)簇的大小Size(C)、點對象的大小Size(P)以及查詢結(jié)果集K值,則劃分數(shù)據(jù)簇分區(qū)的維數(shù):

公式中c是常量(c≥1),它的作用是使劃分后的分區(qū)內(nèi)包含的點對象數(shù)量至少是K的c倍,這樣每個候選簇只需確定一個候選分區(qū)就能基本滿足查詢結(jié)果對象個數(shù)要求,避免了搜索多個分區(qū)的計算復(fù)雜性.以我們的實驗數(shù)據(jù)二十維向量空間為例,數(shù)據(jù)集DS大小540MB,點對象大小為104Byte.根據(jù)K-means聚類算法DS被劃分成4個數(shù)據(jù)簇A、B、C、D,其中數(shù)據(jù)簇B大小為250MB.假設(shè)K=10,c=20,根據(jù)定理1計算用于劃分數(shù)據(jù)簇B分區(qū)的維數(shù)為13,簇B被劃分為213個分區(qū).

定義2 分區(qū)位碼A(b1,b2,…,bd′) 假設(shè)整數(shù)變量i代表維標(1≤i≤d′),則bi表示分區(qū)A的第i維位碼、oi表示質(zhì)心O的第i維位碼、pi表示任意點P的第i維位碼,假設(shè)A所在的數(shù)據(jù)簇質(zhì)心為O(o1,o2,…,od′),由于同一分區(qū)內(nèi)所有點對象具有相同的位碼值,因此可以由區(qū)內(nèi)任意一點P(p1,p2,…,pd′)的位碼值得到分區(qū)A的位碼:

由定義2可以看出,一個分區(qū)的位碼表達該分區(qū)相對簇參考點的位置關(guān)系,在數(shù)據(jù)簇內(nèi)任一分區(qū)均可用長度為d′的唯一位碼字符串來表示.以二維向量空間為例,各個分區(qū)的位碼表示如圖1所示.

為有效克服高維空間“維數(shù)災(zāi)難[22]”影響,iPBM綜合利用近似向量表示法和一維向量轉(zhuǎn)換法的優(yōu)點,利用二維的位碼索引值壓縮高維向量表示.

定義3 位碼索引值 高維向量點對象P(p1,p2,…,pd)的位碼索引值為P(Dp,Bp),其中Dp是P與所屬簇參考點間的距離;Bp是P與參考點間的近似位置關(guān)系,即P的位碼值.

由定義3 可知,位碼索引值的主要作用體現(xiàn)在檢索過程中不僅可以根據(jù)Bp過濾候選分區(qū),而且可以根據(jù)Dp進一步過濾候選分區(qū)環(huán),從而在沒有任何高維歐氏距離計算情況下就能實現(xiàn)搜索范圍兩級過濾,大大縮小搜索范圍從而降低高維向量距離計算代價.3.2 數(shù)據(jù)存儲

在數(shù)據(jù)存儲時為了兼顧相關(guān)性和并行性兩方面原則,iPBM將一個簇數(shù)據(jù)的所有Block放在一個Slave節(jié)點上,一個Slave節(jié)點可以存儲多個簇的數(shù)據(jù),同時將簇中所有分區(qū)的數(shù)據(jù)均勻分配到該簇的每個Block中.這樣做的好處是,查詢時篩選出候選分區(qū)后,根據(jù)候選分區(qū)的對象信息存儲在多個Block中的特點,可以利用多個Map任務(wù)并行計算,提高查詢并行性和查詢效率.在本文第四章KNN查詢算法介紹中,可以看出這種數(shù)據(jù)劃分和存儲的好處.

在iPBM中,在Master節(jié)點上設(shè)計了一個定位表存儲各個數(shù)據(jù)簇在Slave節(jié)點上的分布信息.如圖2和圖3所示,定位表指示簇A和簇D存儲在Slave1上,簇B存儲在Slave2上,簇C存儲在Slave3上,則簇A的數(shù)據(jù)塊A1和A2以及簇D的數(shù)據(jù)塊D1存放在Slave1上,簇B的數(shù)據(jù)塊B1、B2和B3存放在Slave2上,簇C的數(shù)據(jù)塊C1和C2存放在Slave3上.另外的3個Slave節(jié)點存儲這些簇的備份.

3.3 索引結(jié)構(gòu)

依據(jù)iPBM的數(shù)據(jù)劃分和存儲結(jié)構(gòu),為KNN查詢設(shè)計基于高維空間位置編碼的雙層索引G-L(圖4),包含全局索引G-Index和局部索引L-Index.全局索引存放在Master節(jié)點上負責(zé)數(shù)據(jù)定位.局部索引存放在Slave節(jié)點上負責(zé)數(shù)據(jù)存取.

定義4 全局索引G-Index以鍵值對形式存儲數(shù)據(jù)簇元數(shù)據(jù)信息,表示為.其中Oi(oi1,oi2,…,oid) (i=1,2,…,m)為第i個數(shù)據(jù)簇的質(zhì)心坐標,Ri為該簇的覆蓋半徑.

定義5 局部索引L-Index以鍵值對形式存儲數(shù)據(jù)簇內(nèi)的分區(qū)和點對象信息,表示為.Aj(bj1,bj2,…,bjd′)(j=1,2,…,2d′)為數(shù)據(jù)簇的第j個分區(qū)的位碼,nj(nj>0)為該分區(qū)內(nèi)的點對象個數(shù).

以圖1數(shù)據(jù)劃分示意圖,雙層索引G-L結(jié)構(gòu)如圖4所示.

4 基于G-L索引的KNN查詢

4.1 數(shù)據(jù)篩選

定義6 候選分區(qū)環(huán) 假設(shè)查詢點Q在候選簇C的位碼索引值為Q(DQ,BQ)，則候選分區(qū)與查詢范圍(Q,r)相交的局部環(huán)狀區(qū)域為候選分區(qū)環(huán)，候選分區(qū)環(huán)內(nèi)的任一點對象P(DP,BP)滿足DP∈[Max(0,DQ-r),Min(DQ+r,R)]。

由定義6可以看出,在不需要高維向量距離計算情況下,根據(jù)點對象的位碼索引值就可以判斷該點是否屬于候選點,從而降低高維計算代價,有效克服“維數(shù)災(zāi)難”影響.候選分區(qū)環(huán)內(nèi)的點對象即為最終的KNN查詢結(jié)果候選點對象.以二維空間為例,假設(shè)兩個查詢Q1和Q2,Q1查詢的候選分區(qū)為數(shù)據(jù)簇B的A3區(qū)和數(shù)據(jù)簇D的A2區(qū)(圖5中分別用深灰和灰色表示),Q2查詢的候選分區(qū)為數(shù)據(jù)簇C的A1區(qū)(圖5中淺灰表示),各自對應(yīng)的候選分區(qū)環(huán)如圖6所示.

4.2 KNN查詢

我們設(shè)計了MapReduce框架下基于G-L索引的并行KNN查詢方法,以圖6中的Q1查詢?yōu)槔?KNN查詢過程如圖7所示.

5 實驗結(jié)果與分析

5.1 實驗環(huán)境

實驗由4臺HP刀片服務(wù)器搭建了一個內(nèi)部網(wǎng)絡(luò),組成4個節(jié)點的Hadoop集群,其中 1 個節(jié)點作為 Master,其余3 個節(jié)點作為 Slave,網(wǎng)絡(luò)內(nèi)的各個節(jié)點通過100M網(wǎng)卡相互訪問.Master節(jié)點服務(wù)器CPU:Inter(R) Xeon(R) E5620 2.4GHz 4*4核,Memory:8GB,Disk:300G*8.Salve節(jié)點服務(wù)器CPU:Inter(R) Xeon(TM) 3.00GHZ 4核,Memory:1GB,Disk:146.8G*2.每臺服務(wù)器上安裝OS:64bit CentOS6.2,Hadoop 版本1.0.3和Eclipse版本4.3.1.Hadoop默認參數(shù)配置block為64M,數(shù)據(jù)備份數(shù)為3.

由于沒有合適規(guī)模的真實數(shù)據(jù)集,本文按照表2的數(shù)據(jù)格式生成了一批聚類數(shù)據(jù),其中每類數(shù)據(jù)的基準維度為 20,所有值均為 0-10000之間的整數(shù),以2000萬條記錄為標準,大約2G的數(shù)據(jù)量.

表2 數(shù)據(jù)格式

MapReduce框架下默認的分區(qū)劃分是通過HashPartitioner類實現(xiàn),HashPartitioner繼承的是Partitioner類,是Mapper作業(yè)使用key的hashCode對數(shù)據(jù)進行均勻劃分的方法.為了實現(xiàn)iPBM的分區(qū)劃分,實驗中利用eclipse向MapReduce框架源碼中增加新的分區(qū)劃分類,命名為BitCodePartitioner并繼承Partitioner類,再修改MapReduce配置文件使默認分區(qū)方式指向BitCodePartitioner,使BitCodePartitioner代替HashPartitioner成為默認分區(qū)劃分類,將修改后的MapReduce源碼利用Ant Builder 進行重新打包編譯成為新的MapReduce框架,即iPBM框架.

5.2 實驗結(jié)果與分析

影響實驗運行時間的因素有:數(shù)據(jù)規(guī)模、數(shù)據(jù)維度、查詢K值、服務(wù)器數(shù)量等.因此,在研究某一因素對執(zhí)行時間的影響時,需要保證其他因素固定不變,以保證實驗數(shù)據(jù)的可靠性.由于本文中數(shù)據(jù)劃分和索引構(gòu)建是預(yù)處理過程,一次預(yù)處理可以為后續(xù)的多次查詢提供服務(wù),因此預(yù)處理時間未計入總時間.

5.2.1 數(shù)據(jù)規(guī)模變化對查詢時間的影響

圖8展示了數(shù)據(jù)維度為20維,K=20,集群節(jié)點數(shù)為4,數(shù)據(jù)規(guī)模分別為2千萬、4千萬、6千萬、8千萬、1億、2億條記錄時,KNN查詢執(zhí)行時間的變化情況.從實驗結(jié)果來看:當(dāng)數(shù)據(jù)維度、K值、服務(wù)器數(shù)量等固定時,執(zhí)行時間隨著數(shù)據(jù)規(guī)模的增加而近似線性增長,即本文方法對數(shù)據(jù)規(guī)模的變化不敏感.通過分析可知iPBM設(shè)計的大規(guī)模高維數(shù)據(jù)預(yù)處理和索引機制,有效地抑制了查詢時間隨數(shù)據(jù)規(guī)模急劇增長.聚類預(yù)處理將相關(guān)數(shù)據(jù)分布在同一Salve上,使得查詢操作集中在Map階段而非Reduce階段,從而避免了網(wǎng)絡(luò)傳輸代價;分區(qū)預(yù)處理使得分區(qū)數(shù)據(jù)均勻分配到多個block中,這樣可以充分利用Map任務(wù)在集群上分布式計算和任務(wù)處理能力;同時KNN查詢通過雙層索引實現(xiàn)了三級過濾過程進一步縮小實際需要搜索的范圍,因此數(shù)據(jù)規(guī)模變化對查詢時間的影響不大.

5.2.2 擴展性

從兩個方面考察iPBM方法的擴展性:

(1)數(shù)據(jù)維度變化效果:圖9 展示了數(shù)據(jù)規(guī)模為2千萬,K=20,集群節(jié)點數(shù)為4,數(shù)據(jù)維度分別為10、20、30、40、50、100時,KNN查詢執(zhí)行時間的變化情況.

從實驗結(jié)果來看:當(dāng)數(shù)據(jù)規(guī)模、K值、服務(wù)器數(shù)量等固定時,執(zhí)行時間隨著數(shù)據(jù)維度的增加呈上升趨勢且上升的幅度相對穩(wěn)定,基本保持在43.7%的水平,未出現(xiàn)隨著維度的增加計算時間大幅增加的情況.同時實驗數(shù)據(jù)表明,隨維度不斷增大而查詢時間增長放緩(從10維到50維,查詢時間增長率分別為71.3%,56.8%,18.8%,7.8%),說明iPBM對高維數(shù)據(jù)具有很好的抗壓性.在iPBM中使用了三層數(shù)據(jù)過濾技術(shù),包括聚類、分區(qū)以及候選分區(qū)環(huán),大大降低了數(shù)據(jù)搜索范圍,同時利用數(shù)據(jù)位碼索引值壓縮表示形式,降低了高維向量距離計算代價,這是維度對查詢時間影響不大的主要原因.特別需要說明的是,實驗中為了降低MapReduce框架下數(shù)據(jù)傳輸代價的影響,我們通過調(diào)整Hadoop參數(shù)配置(如表3所示),使得在不同維度下數(shù)據(jù)劃分的block數(shù)量盡量保持一致,這樣實驗結(jié)果更能反映維度變化對查詢時間的影響.

表3 不同數(shù)據(jù)維數(shù)下的Hadoop參數(shù)配置

(2)集群節(jié)點數(shù)量變化效果:圖10展示了數(shù)據(jù)規(guī)模為2000萬,維度為20,K=20,Slave節(jié)點數(shù)分別為3、6、9、12、15時,KNN查詢執(zhí)行時間的變化情況.從實驗結(jié)果來看:當(dāng)數(shù)據(jù)規(guī)模、數(shù)據(jù)維度、K值等固定時,執(zhí)行時間隨著服務(wù)器數(shù)量增加而減少的趨勢很明顯,平均降幅接近1/3.隨著集群節(jié)點數(shù)量增多,通過iPBM方法將數(shù)據(jù)均分到更多的服務(wù)器上參與計算和任務(wù)處理,增大數(shù)據(jù)處理能力從而減少查詢時間.

以上兩個方面都說明了iPBM方法具有較好的可擴展性.

5.2.3 K值變化對查詢時間的影響

圖11展示了數(shù)據(jù)規(guī)模為2000萬,維度為20,集群節(jié)點數(shù)為4,K值分別為10、20、30、40、50時,KNN查詢執(zhí)行時間的變化情況.從實驗結(jié)果來看:當(dāng)數(shù)據(jù)規(guī)模、數(shù)據(jù)維度、服務(wù)器數(shù)量等固定時,k值的變化對執(zhí)行時間基本沒有影響.分析可知iPBM在數(shù)據(jù)劃分時將分區(qū)包含對象數(shù)量保持為K的數(shù)倍,使得每個分區(qū)的記錄數(shù)足夠滿足KNN檢索結(jié)果的需要,因此不同K值篩選出的候選分區(qū)和對應(yīng)的block集合基本一致,即不同K值需要計算的數(shù)據(jù)基本相同,從而KNN查詢消耗時間差距不大.

5.2.4 iPBM與非優(yōu)化的MapReduce方法對比

(1)高效性:由于iPBM是在MapReduce框架下對數(shù)據(jù)劃分做了優(yōu)化處理,同時利用分布式雙層索引提高查詢效率.為了體現(xiàn)這些策略的優(yōu)勢,我們將iPBM與傳統(tǒng)MapReduce模型的查詢效率進行對比分析.圖12 展示了數(shù)據(jù)維度為20維,K=20,集群節(jié)點數(shù)為4,數(shù)據(jù)規(guī)模分別為2千萬、4千萬、6千萬、8千萬、1億、2億條記錄時,iPBM與未經(jīng)任何優(yōu)化處理的MapReduce模型的性能對比.從實驗結(jié)果來看,同等條件下iPBM查詢花費時間只有傳統(tǒng)MapReduce模型的45.6%左右,效率提升的效果非常明顯.充分說明iPBM采用的兼顧相關(guān)性和并行性的數(shù)據(jù)分塊方式,較MapReduce默認的數(shù)據(jù)分塊方式,能夠更好地適應(yīng)大規(guī)模數(shù)據(jù)應(yīng)用環(huán)境.同時也說明了iPBM將高維向量轉(zhuǎn)換為二維位碼索引值降低了高維距離計算復(fù)雜性,以及雙層索引機制大大縮小了搜索范圍,這些策略對提升查詢效率發(fā)揮了重要作用.

(2)準確性:iPBM是在MapReduce框架下修改了數(shù)據(jù)劃分方式,為了驗證新的劃分方式下KNN查詢結(jié)果的準確性,我們將iPBM與傳統(tǒng)MapReduce模型進行了對比分析,圖13展示了數(shù)據(jù)維度為20維,K=20,集群節(jié)點數(shù)為4,數(shù)據(jù)規(guī)模分別為2千萬、4千萬、6千萬、8千萬、1億、2億條記錄時兩者的準確度.由于非優(yōu)化的MapReduce框架下KNN查詢是對所有的數(shù)據(jù)進行全范圍掃描,因此能夠保障查詢準確性.而從實驗結(jié)果來看,同等條件下iPBM準確性與非優(yōu)化MapReduce相當(dāng),這是因為iPBM在KNN查詢時既考慮了單一簇范圍內(nèi)的結(jié)果查詢,也考慮了跨簇范圍下結(jié)果查詢,不存在范圍漏查的可能性,因此iPBM能夠保證較高的查詢準確性.

6 結(jié)束語

針對MapReduce數(shù)據(jù)和任務(wù)并行處理機制,提出了一種適用于MapReduce框架下的高維數(shù)據(jù)近似查詢方法.針對大規(guī)模高維向量空間分布特點、近似查詢需求以及MapReduce編程模式,設(shè)計了基于聚類和分區(qū)的數(shù)據(jù)劃分優(yōu)化策略,將整個數(shù)據(jù)集均勻劃分到集群中各個數(shù)據(jù)塊(block)并共同承擔(dān)計算任務(wù),有利于充分發(fā)揮MapReduce任務(wù)并行處理優(yōu)勢;基于劃分思想構(gòu)建分布式雙層索引,全局索引位于Master節(jié)點上用于KNN查詢時對候選數(shù)據(jù)簇的篩選,局部索引位于Slave節(jié)點上用于進一步確定候選分區(qū)和候選點對象,實現(xiàn)三層過濾過程大大縮小需要搜索的范圍;同時利用二維位碼索引值壓縮高維向量表示以降低維數(shù)災(zāi)難影響.實驗表明基于MapReduce編程模型的高維數(shù)據(jù)近似查詢方法iPBM對查詢效率具有明顯的提升效果,同時具有良好的擴展性.本文的研究工作主要是針對高維數(shù)據(jù)集比較穩(wěn)定,索引一次構(gòu)建多次使用的環(huán)境,沒有考慮索引更新維護代價.下一步需要研究在數(shù)據(jù)更新比較頻繁的應(yīng)用場景下,如何提升查詢性能.

[1]黃震華.云環(huán)境下Top-n推薦算法[J].電子學(xué)報,2015,43(1):54-61.

Huang Zhenhua.Top-n recommendation algorithms for cloud data[J].Acta Electronica Sinica,2015,43(1):54-61.(in Chinese)

[2]李建江,崔健,王聃,等.MapReduce并行編程模型研究綜述[J].電子學(xué)報,2011,39(11):2635-2642.

Li Jianjiang,Cui Jian,Wang Dan,et al.Survey of MapReduce parallel programming model[J].Acta Electronica Sinica,2011,39(11):2635-2642.(in Chinese)

[3]Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Proceedings of Operating Systems Design and Implementation ,2004,51(1):107-113.

[4]Zhang C,Li F,Jestes J.Efficient parallel kNN joins for large data in MapReduce[A].Proceedings of the 15th International Conference on Extending Database Technology[C].ACM,2012.38-49.

[5]Doulkeridis C,Nφrv?g K.A survey of large-scale analytical query processing in MapReduce[J].Vldb Journal,2014,23(3):355-380.

[6]Vlachou A,Doulkeridis C,Nφrv?g K.Distributed top-k query processing by exploiting skyline summaries[J].Distributed & Parallel Databases,2012,30(3-4):1-33.

[7]Vlachou A,Doulkeridis C,Kjetil G,et al.On efficient top-k query processing in highly distributed environments[A].ACM Sigmod International Conference on Management of Data[C].ACM,2008.753-764.

[8]史英杰,孟小峰.云數(shù)據(jù)管理系統(tǒng)中查詢技術(shù)研究綜述[J].計算機學(xué)報,2013,36(2):209-225.

Shi Yingjie,Meng Xiaofeng.A survey of query techniques in cloud data management systems[J].Chinese Journal of Computers,2013,36(2):209-225.(in Chinese)

[9]Dittrich J,Quiané-Ruiz J A,Jindal A,et al.Hadoop++:making a yellow elephant run like a cheetah (Without It Even Noticing)[J].Proceedings of the Vldb Endowment,2010,3(12):518-529.

[10]Dittrich J,Quiané-Ruiz J A,Richter S,et al.Only aggressive elephants are fast elephants[J].Infection,2012,5(11):243.

[11]Eltabakh M Y,Tian Y,Zcan F,et al.CoHadoop:flexible data placement and its exploitation in Hadoop[J].Proceedings of the Vldb Endowment,2011,4(9):575-585.

[12]Z?schke T,Zimmerli C,Norrie M C.The ph-tree:A space-efficient storage structure and multi-dimensional index[A].Proceedings of the 2014 ACM Sigmod International Conference on Management of Data[C].ACM,2014:397-408.

[13]Wu S,Jiang D,Ooi B C,et al.Efficient B-tree based indexing for cloud data processing[J].Proceedings of the VLDB Endowment,2010,3(1-2):1207-1218.

[14]Wang J,Wu S,Gao H,et al.Indexing multi-dimensional data in a cloud system[A].Proceedings of the 2010 ACM Sigmod International Conference on Management of Data[C].ACM,2010:591-602.

[15]Ding L,Qiao B,Wang G,et al.An efficient Quad-Tree Based Index Structure for Cloud Data Management[M].Springer Berlin Heidelberg,2011.238-250.

[16]Lu W,Shen Y,Chen S,et al.Efficient processing of k nearest neighbor joins using mapreduce[J].Proceedings of the VLDB Endowment,2012,5(10):1016-1027.

[17]Doulkeridis C,Nφrv?g K.On saying enough already in MapReduce[A].Proceedings of the 1st International Workshop on Cloud Intelligence[C].ACM,2012:7.

[18]劉義,景寧,陳犖,等.MapReduce框架下基于R-樹的k-近鄰連接算法[J].軟件學(xué)報,2013,24(8):1836-1851.Liu Yi,Jing Ning,Chen Luo,et al.Algorithm for processing k-nearest join based on R-tree in MapReduce[J].Journal of Software,2013,24(8):1836-1851.(in Chinese)

[19]Liu Yi,Jing Ning,Chen Luo,et al.Parallel bulk-loading of spatial data with MapReduce:An R-tree case[J].Wuhan University Journal of Natural Sciences,2011,16(6):513-519.

[20]喬玉龍,潘正祥,孫圣和.一種改進的快速k-近鄰分類算法[J].電子學(xué)報,2005,33(6):1146-1149.

Qiao Yulong,Pan Zhengxiang,Sun Shenghe.Improved K nearest neighbors classification algorithm[J].Acta Electronica Sinica,2005,33(6):1146-1149.(in Chinese)

[21]付寧,喬立巖,彭喜元.基于改進K-means聚類和霍夫變換的稀疏源混合矩陣盲估計算法[J].電子學(xué)報,2009,37(4):92-96.

Fu Ning,Qiao Liyan,Peng Xiyuan.Blind recovery of mixing matrix with sparse sources based on improved K-means clustering and hough transform[J].Acta Electronica Sinica,2009,37 (4):92-96.(in Chinese)

[22]楊靜,趙家石,張健沛.一種面向高維數(shù)據(jù)挖掘的隱私保護方法[J].電子學(xué)報,2013,41(11):2187-2192.Yang Jing,Zhao Jiashi,Zhang Jianpei.A privacy preservation method for high dimensional data mining[J].Acta Electronica Sinica,2013,41(11):2187-2192.(in Chinese)

梁俊杰 女,1974年出生,湖北武漢人.教授、碩士生導(dǎo)師、CCF會員.研究方向為大數(shù)據(jù)、高維索引、數(shù)據(jù)庫管理系統(tǒng).

E-mail:ljjhubu@163.com

李鳳華(通信作者) 男,1966年生,湖北浠水人,博士,中國科學(xué)院信息工程研究所副總工、研究員、博士生導(dǎo)師,研究方向為網(wǎng)絡(luò)與系統(tǒng)安全、隱私保護、可信計算.

E-mail:lfh@iie.ac.cn

Optimized High-Dimensional Index and KNN Query in MapReduce

LIANG Jun-jie1,LI Feng-hua2,3,LIU Qiong-ni1,YIN Li1

(1.DepartmentofComputerScienceandTechnology,HubeiUniversity,Wuhan,Hubei430062,China;2.StateKeyLaboratoryofInformationSecurity,InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093,China;3.BeijingElectronicScience&TechnologyInstitute,Beijing100070,China)

To address the low efficiency problem caused by the approximate large-scale high-dimensional data query,we propose a novel high-dimensional index and KNN query method,called iPBM,which exploits two main problems,including the optimal division on the MapReduce’s data block and their contributions to the computing.Specifically,based on the principles of relativity and parallelity,iPBM employs a two-phase partitioning scheme of clustering and zoning to equally split the data to the available blocks,then we design a distributed two-layer index structure and parallel KNN query algorithm.With fully considering the global index,local index and two-dimensional bitcode property,iPBM achieves triple-layers filtering,and thus the number of queried area and the computing cost on the high-dimensional data is minimized.The accuracy,efficiency and scalability of the proposed iPBM are thoroughly evaluated via detailed simulations.

cloud;MapReduce;KNN query;high-dimensional index

2014-12-31；

2015-11-08；責(zé)任編輯：諸葉梅

國家發(fā)改委2012年信息安全專項(No.發(fā)改辦高技[2013]1309)；國家自然科學(xué)基金(No.61170251)；湖北省自然科學(xué)基金重點項目(No.2013CFA115)；武漢市科技攻關(guān)計劃(No.2013012401010851)

TP301

A

0372-2112 (2016)08-1873-08