云環(huán)境下基于MKd-Tree的大規(guī)模圖數(shù)據(jù)索引技術(shù)?

雷婷??

（成都工業(yè)學(xué)院通信工程系，成都611730）

云環(huán)境下基于MKd-Tree的大規(guī)模圖數(shù)據(jù)索引技術(shù)?

雷婷??

（成都工業(yè)學(xué)院通信工程系，成都611730）

由于高維屬性和海量數(shù)據(jù)所帶來的影響，數(shù)據(jù)管理需要相當(dāng)高的計(jì)算負(fù)載，傳統(tǒng)的集中索引技術(shù)已經(jīng)變得不切實(shí)際。為滿足數(shù)據(jù)的快速增長、海量和高維特性的要求，實(shí)現(xiàn)了一個(gè)高層次的分布式樹形索引結(jié)構(gòu)框架MRC-Tree?；贛RC-Tree框架基礎(chǔ)上，提出了兩種MKd-Tree索引結(jié)構(gòu)構(gòu)建方法，即OMKd-Tree和MMKd-Tree。理論分析和實(shí)驗(yàn)結(jié)果表明，基于MRC-Tree框架的MKd-Tree索引結(jié)構(gòu)構(gòu)建方法具有良好的可擴(kuò)展性和較高的檢索效率。

高維數(shù)據(jù)庫；圖數(shù)據(jù)；索引結(jié)構(gòu)；分布式樹形索引結(jié)構(gòu)框架；Map-Reduce框架；MKd-Tree

1 引言

近年來，隨著多媒體技術(shù)和數(shù)字化技術(shù)的進(jìn)步，高維數(shù)據(jù)庫的應(yīng)用得到了快速的發(fā)展，如海量的多媒體數(shù)據(jù)庫、生物信息學(xué)中龐大的蛋白質(zhì)數(shù)據(jù)庫、DNA數(shù)據(jù)庫等，這些信息一般使用特征抽取等方法映射為高維數(shù)據(jù)，然后通過計(jì)算這些高維數(shù)據(jù)之間距離范數(shù)實(shí)現(xiàn)相似性檢索。在這種背景下，高維數(shù)據(jù)索引結(jié)構(gòu)和適用于高維索引結(jié)構(gòu)的相似性檢索算法已經(jīng)成為研究人員研究的熱點(diǎn)，而在已有的眾多高維索引結(jié)構(gòu)中，有的特定工作在向量空間中，而有的是針對度量空間而設(shè)計(jì)。由于度量空間概念堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，簡單但精確的分區(qū)和減枝規(guī)則能夠被成功構(gòu)造。這對于建立新的索引結(jié)構(gòu)是非常重要的，特別是對于檢索執(zhí)行耗費(fèi)不僅是I／O約束的，而且是CPU約束的情況。目前，許多度量檢索結(jié)構(gòu)已經(jīng)被提出，與線性掃描相比，性能獲得顯著的加速。然而，這些檢索結(jié)構(gòu)的執(zhí)行耗費(fèi)隨著數(shù)據(jù)集的規(guī)模呈線性增長趨勢。這意味著，隨著數(shù)據(jù)規(guī)模的增大，檢索反應(yīng)時(shí)間遲早會(huì)變得不可容忍。另一方面，據(jù)評估，每年有近93%的多媒體數(shù)據(jù)是以數(shù)字的形式存在，新增多媒體數(shù)據(jù)的總量已經(jīng)超過1 018字節(jié)，而且每年還以指數(shù)倍增長。為了能夠處理海量的、不斷增長的多媒體數(shù)據(jù)相似性檢索，可擴(kuò)展架構(gòu)的需求已經(jīng)促使研究人員開始重視這方面的問題。在這個(gè)研究領(lǐng)域，Map-Reduce框架由于良好的可擴(kuò)展性和自組織性，豐富的平臺(tái)支持，正在迅速獲得廣泛的應(yīng)用，并為解決海量多媒體數(shù)據(jù)相似性檢索問題奠定了堅(jiān)實(shí)的基礎(chǔ)。

盡管Map-Reduce框架［1］非常成功，但是它僅僅能夠抽象獨(dú)立處理單個(gè)的數(shù)據(jù)實(shí)體。大多數(shù)情況下，數(shù)據(jù)和計(jì)算密集型的應(yīng)用并不適合直接使用這種簡單模型。Map-Reduce框架范圍之外，一類與樹形結(jié)構(gòu)相關(guān)的應(yīng)用普遍被用在幾乎所有的計(jì)算領(lǐng)域?；跇湫谓Y(jié)構(gòu)的應(yīng)用，特別是涉及大規(guī)模數(shù)據(jù)密集型處理的情況，需要使用分布式計(jì)算和存儲(chǔ)系統(tǒng)。例如，使用標(biāo)記語言表示的結(jié)構(gòu)化文檔，如SGML和它的變種XML，都是基于樹形結(jié)構(gòu)表示的。這些文檔往往需要復(fù)雜的檢索處理，并且可以有效地利用它們的樹形結(jié)構(gòu)實(shí)現(xiàn)。許多檢索程序都是基于檢索樹的，如BST［2］、B-Trees［3］、R-Trees［4］和Kd-Tree［5］，其目的都是為了使數(shù)據(jù)檢索更加快捷高效。空間樹形結(jié)構(gòu)也已經(jīng)被廣泛應(yīng)用于幾何造型、圖形和圖像等高維數(shù)據(jù)處理中。在高性能計(jì)算中，基于樹形結(jié)構(gòu)的數(shù)據(jù)密集型應(yīng)用也廣泛存在，既有獲取和挖掘科學(xué)數(shù)據(jù)集的應(yīng)用，也有分子動(dòng)力學(xué)和計(jì)算電磁學(xué)等領(lǐng)域的應(yīng)用。

基于樹形結(jié)構(gòu)的數(shù)據(jù)和計(jì)算密集型應(yīng)用往往需要用戶大量的編程工作，特別是對于處理分布式環(huán)境中大的樹形結(jié)構(gòu)?；贛ap-Reduce框架的抽象樹形結(jié)構(gòu)是非常有幫助的，但由于樹形結(jié)構(gòu)及其相應(yīng)算法的多樣性，構(gòu)建一個(gè)基于Map-Reduce框架的樹形結(jié)構(gòu)是非常有挑戰(zhàn)性的。參照文獻(xiàn)［6－9］，基于Hadoop環(huán)境，本文為樹形結(jié)構(gòu)的檢索和計(jì)算實(shí)現(xiàn)一個(gè)高層次的分布式架構(gòu)，即MRC-Tree（Computation based on Map-Reduce on tree structures），也稱為樹形結(jié)構(gòu)上基于Map-Reduce的計(jì)算。盡管樹形結(jié)構(gòu)及其應(yīng)用在上面的算法類型多種多樣，該抽象方法可以為更廣泛的應(yīng)用提供充分的一般性。MRC-Tree框架包含需要用戶指定的函數(shù)（由基本函數(shù)Map和 Reduce組成），通過精巧設(shè)計(jì)這些函數(shù)，可以通過多種方式實(shí)現(xiàn)樹形結(jié)構(gòu)中廣泛使用的操作。這些函數(shù)都是基于基本的父子（Parent-Child）關(guān)系，因此對于所有樹形結(jié)構(gòu)都一樣，同時(shí)，將存儲(chǔ)機(jī)制、容錯(cuò)問題和并發(fā)問題等問題都移交給Hadoop平臺(tái)管理。然后，在MRC-Tree框架基礎(chǔ)上，基于原始的Kd-Tree索引結(jié)構(gòu)［5］，提出兩種并行化Kd-Tree的方法，即MMKd-Tree（Build multiple Kd-Trees by splitting data equally based on Map-Reduce）和OMKd-Tree（Build one distributed Kd-Tree based on Map-Reduce）。Kd-Tree是一種根據(jù)K維空間中的點(diǎn)集對空間進(jìn)行分割的數(shù)據(jù)結(jié)構(gòu)，采用多維索引值進(jìn)行查找，常用于范圍查找和最近鄰查找等，是一種特殊的二叉空間分割樹。在高維空間檢索，特別是圖形檢索，諸如碰撞檢測、遮擋剔除、游戲以及光線追蹤等領(lǐng)域［10－11］應(yīng)用廣泛。最后，通過實(shí)驗(yàn)，分別從檢索CPU時(shí)間、檢索精度、吞吐量以及可擴(kuò)展性4個(gè)方面來評估MMKd-Tree和OMKd-Tree索引結(jié)構(gòu)性能。理論分析和實(shí)驗(yàn)結(jié)果表明，基于MRC-Tree框架的OMKd-Tree索引結(jié)構(gòu)具有良好的可擴(kuò)展性和較高的檢索效率。

2 MRC-Tree框架

對于樹形結(jié)構(gòu)，用戶可以通過父節(jié)點(diǎn)與子節(jié)點(diǎn)之間鏈接導(dǎo)航的拓?fù)浣Y(jié)構(gòu)來訪問樹節(jié)點(diǎn)上特定的應(yīng)用信息。樹形結(jié)構(gòu)的表示形式和存儲(chǔ)結(jié)構(gòu)對于用戶是無關(guān)緊要的，即便它是以一種分布式的方式存儲(chǔ)。本節(jié)的研究內(nèi)容是在超大的樹形結(jié)構(gòu)上支持?jǐn)?shù)據(jù)和計(jì)算密集型應(yīng)用，通過實(shí)現(xiàn)MRC-Tree框架來提供多個(gè)并發(fā)計(jì)算，為了使算法更高效地執(zhí)行，MRC-Tree框架提供分布式計(jì)算方法。MRC-Tree框架如圖1所示。

圖1MRC-Tree框架結(jié)構(gòu)圖Fig.1 The MRC-Tree frame structure

在樹形結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)存儲(chǔ)的信息由樹的拓?fù)浣Y(jié)構(gòu)信息和特定的應(yīng)用信息兩部分組成。其中，樹的拓?fù)湫畔ǜ腹?jié)點(diǎn)與子節(jié)點(diǎn)之間的鏈接、節(jié)點(diǎn)在樹中的層次等。樹形結(jié)構(gòu)的節(jié)點(diǎn)可以表示成μ、ν、ω，在節(jié)點(diǎn)μ中，使用元組μ＝（kμ，Xμ）表示特定的應(yīng)用信息，kμ為唯一的節(jié)點(diǎn)標(biāo)識符，Xμ為存儲(chǔ)在節(jié)點(diǎn)μ中的其他信息。例如，kμ可以是二叉檢索樹中的編號信息、八叉樹中的域信息等。kμ和Xμ的數(shù)據(jù)類型是用戶指定的。使用符號“ㄧ→”表示MRC-Tree框架提供給用戶的函數(shù)，符號“→”表示由用戶提供的函數(shù)。MRC-Tree框架包括兩個(gè)關(guān)鍵操作，一個(gè)操作是用來表示多個(gè)檢索在樹形結(jié)構(gòu)上并發(fā)執(zhí)行，另一個(gè)操作是用來表示在樹形結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)上執(zhí)行計(jì)算。這兩個(gè)操作都依賴于有限的用戶指定函數(shù)，通過這些精心設(shè)計(jì)的函數(shù)可以實(shí)現(xiàn)不同類型的樹及其基于樹的操作。

2.1 基于樹形結(jié)構(gòu)的檢索操作

基于樹形結(jié)構(gòu)的檢索操作提供了自上而下的檢索，從樹的根開始遍歷，遞歸向下一個(gè)或多個(gè)分支路徑遍歷，從一個(gè)節(jié)點(diǎn)遍歷至另一個(gè)或更多的子節(jié)點(diǎn)，檢索操作的結(jié)果是一個(gè)樹節(jié)點(diǎn)列表。盡管并行執(zhí)行特定類型樹形結(jié)構(gòu)的單次檢索一直是一個(gè)理論研究問題，為提高單次檢索效率，往往選擇將數(shù)據(jù)分區(qū)索引，然后通過分布式檢索算法進(jìn)行檢索以及結(jié)果整合。實(shí)踐中往往使用并發(fā)多檢索和數(shù)據(jù)分區(qū)檢索相結(jié)合，可以充分利用分布式系統(tǒng)中的計(jì)算資源。而且對于并發(fā)多重檢索問題，并行計(jì)算是非常有效的。通過檢索項(xiàng)列表，treeSearch操作允許多個(gè)并發(fā)檢索同時(shí)執(zhí)行，最后以list（list（ν））方式返回所有檢索結(jié)果。令K表示單一檢索項(xiàng)，即

其中，list（K）＝（K1，K2，…Kn）是一個(gè)包含n個(gè)檢索項(xiàng)的列表，而相應(yīng)的結(jié)果節(jié)點(diǎn)列表為

操作依賴于用戶指定的select函數(shù)，該函數(shù)從樹形結(jié)構(gòu)中取出一個(gè)節(jié)點(diǎn)μ，檢索項(xiàng)K作為輸入，輸出一個(gè)節(jié)點(diǎn)列表：select（μ，K）→list（ν）。

其中，list（ν）有以下3種情況：

（1）list（ν）＝（μ），這種情況下，檢索停止在μ，μ被包括在檢索結(jié)果集合中；

（2）list（ν）為空，檢索停止，在這個(gè)檢索路徑上，沒有節(jié)點(diǎn)被包含在檢索結(jié)果集合中；

（3）list（ν）包含一個(gè)或多個(gè)μ的孩子，select被遞歸應(yīng)用到list（ν）中的每個(gè)節(jié)點(diǎn)上。

為實(shí)現(xiàn)select函數(shù)，用戶需要訪問一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和孩子節(jié)點(diǎn)分別通過以下系統(tǒng)指定方式獲得：parent（μ）ㄧ→ν和children（μ）ㄧ→list（ν）。

2.2 基于樹形結(jié)構(gòu)的計(jì)算操作

函數(shù)treeCompute用于處理樹形結(jié)構(gòu)中的節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)中的信息：treeCompute（μ）ㄧ→μ′。其中，μ′＝（kμ，X′μ）表示更新節(jié)點(diǎn)μ。在更新節(jié)點(diǎn)μ過程中，其他節(jié)點(diǎn)的集合也需要被考慮。用戶指定如何確定與μ相關(guān)的節(jié)點(diǎn)列表，并通過generate函數(shù)在μ上定義交集。使用用戶指定的combine函數(shù)，合并節(jié)點(diǎn)μ與交集中的值，計(jì)算節(jié)點(diǎn)μ′。generate和combine函數(shù)定義如下。

（1）generate函數(shù)：generate函數(shù)將節(jié)點(diǎn)μ作為輸入，返回一個(gè)包含節(jié)點(diǎn)μ上的交集和一個(gè)依賴標(biāo)識dy。這個(gè)標(biāo)識用來表明，若多個(gè)交集之間存在依賴，是否需要在函數(shù)中考慮，generate（μ）→（list（ν），dy）。

（2）combine函數(shù)：合并函數(shù)需要指定如何合并關(guān)于節(jié)點(diǎn)μ的信息來計(jì)算它的更新值，這些信息來自節(jié)點(diǎn)μ的交集中所有節(jié)點(diǎn)，combine（μ，ν）→μ′。

2.3 映射樹形結(jié)構(gòu)操作到MRC-Tree框架

樹形結(jié)構(gòu)上的鍵值檢索：對于一個(gè)可以完全有序集合，檢索樹被廣泛用于索引集合中的鍵值檢索。在MRC-Tree框架上，使用treeSearch操作在檢索樹上實(shí)現(xiàn)多個(gè)檢索并發(fā)執(zhí)行。操作定義如下。

（1）域檢索：基于Rd（d∈N）層次劃分的空間樹形結(jié)構(gòu)種類較多，例如：四叉樹、八叉樹、Kd-trees、R＋－Trees等。在這種情況下，檢索鍵值K是d維空間中的一個(gè)區(qū)域，檢索結(jié)果是一個(gè)葉子節(jié)點(diǎn)列表，其中每個(gè)節(jié)點(diǎn)都對應(yīng)一個(gè)與K相交的區(qū)域。

（2）局部計(jì)算：樹形結(jié)構(gòu)中最簡單的計(jì)算操作是在樹的每個(gè)節(jié)點(diǎn)上進(jìn)行局部計(jì)算，這時(shí)，無需考慮與其他節(jié)點(diǎn)的交集。treeCompute可以被用來簡化定義generate函數(shù)，僅需要返回節(jié)點(diǎn)本身，同時(shí)也可以簡化combine函數(shù)的計(jì)算：

（3）向上聚類：是指對樹中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)聚類從它的后裔節(jié)點(diǎn)開始，并不直接從內(nèi)部節(jié)點(diǎn)子樹的所有葉子節(jié)點(diǎn)開始計(jì)算聚類，這樣代價(jià)較大，而采用從節(jié)點(diǎn)孩子的聚類值進(jìn)行計(jì)算。要做到這一點(diǎn)，在計(jì)算父節(jié)點(diǎn)的聚類之前，首先需要計(jì)算孩子節(jié)點(diǎn)的聚類值。為實(shí)現(xiàn)這種操作，將一個(gè)節(jié)點(diǎn)的交集定義為它的孩子，同時(shí)在函數(shù)generate中，將dy標(biāo)識設(shè)為true。函數(shù)combine定義每個(gè)孩子節(jié)點(diǎn)的聚類操作，由⊕表示：

（4）向下聚類：與向上樹形結(jié)構(gòu)聚類相反，向下樹形結(jié)構(gòu)聚類是指對樹中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)聚類從它的祖先節(jié)點(diǎn)開始。要做到這一點(diǎn)，首先取得一個(gè)節(jié)點(diǎn)父節(jié)點(diǎn)的聚類值，然后同當(dāng)前節(jié)點(diǎn)值合并。為實(shí)現(xiàn)這種操作，generate函數(shù)被要求返回父節(jié)點(diǎn)，以及將dy標(biāo)識設(shè)為true，數(shù)據(jù)聚類操作⊕，被定義在combine函數(shù)中：

（5）范圍檢索：對于一個(gè)空間樹形結(jié)構(gòu)，樹中每個(gè)節(jié)點(diǎn)都對應(yīng)著Rd空間中的一個(gè)盒子。假設(shè)需要在樹的每個(gè)節(jié)點(diǎn)上執(zhí)行計(jì)算，計(jì)算使用的是與中心節(jié)點(diǎn)的距離范圍為［d1，d2］的同層所有節(jié)點(diǎn)。

3 MKd-Tree

本文基于MRC-Tree框架，提出兩種并行化Kd-Tree的方法，即MMKd-Tree（Build multiple Kd-Trees by splitting data equally based on Map-Reduce）和OMKd-Tree（Build one distributed Kd-Tree based on Map-Reduce），如圖2所示。

圖2 基于MRC-Tree框架的Kd-Tree并行化方案Fig.2 Distributed Kd-tree schemes based on the MRC-Tree

（1）MMKd-Tree：并行化Kd-Tree最簡單的方式，首先根據(jù)計(jì)算節(jié)點(diǎn)個(gè)數(shù)將數(shù)據(jù)集均勻切分為獨(dú)立的n－1塊（1個(gè)根計(jì)算節(jié)點(diǎn)，n－1個(gè)子計(jì)算節(jié)點(diǎn)），近似保證每個(gè)數(shù)據(jù)塊適合子計(jì)算節(jié)點(diǎn)的主存。接下來，為每個(gè)數(shù)據(jù)塊在子計(jì)算節(jié)點(diǎn)上分別建立一個(gè)獨(dú)立的Kd-Tree。檢索過程中，根計(jì)算節(jié)點(diǎn)接受目標(biāo)檢索特征向量，并將特征傳遞給所有的子計(jì)算節(jié)點(diǎn)，然后收集返回結(jié)果并整合，輸出最終排序好的結(jié)果；

（2）OMKd-Tree：該方法并行化過程中僅僅建立一棵Kd-Tree，其上部位于根計(jì)算節(jié)點(diǎn)，下部被切分到各個(gè)子計(jì)算節(jié)點(diǎn)，存儲(chǔ)特征的葉子節(jié)點(diǎn)也位于這些子節(jié)點(diǎn)上。檢索過程中，根據(jù)Kd-Tree遍歷退出位置，根計(jì)算節(jié)點(diǎn)引導(dǎo)目標(biāo)檢索特征向量到相應(yīng)的子計(jì)算節(jié)點(diǎn)。子計(jì)算節(jié)點(diǎn)根據(jù)相應(yīng)的Kd-Tree子樹計(jì)算最近鄰，返回結(jié)果給根計(jì)算節(jié)點(diǎn)。最后，根計(jì)算節(jié)點(diǎn)進(jìn)行結(jié)果整合排序，輸出最終排序好的結(jié)果。

顯而易見，OMKd-Tree最大的優(yōu)點(diǎn)是對于單個(gè)特征向量僅需要訪問少量子計(jì)算節(jié)點(diǎn)。因此，子計(jì)算節(jié)點(diǎn)可以同時(shí)并行處理多個(gè)特征向量，大部分計(jì)算都發(fā)生在子計(jì)算節(jié)點(diǎn)中，文獻(xiàn)［12］已經(jīng)證實(shí)該方法是合理的。隨著子計(jì)算節(jié)點(diǎn)數(shù)量的提高，根計(jì)算節(jié)點(diǎn)將會(huì)成為瓶頸，本文通過引入多個(gè)根計(jì)算節(jié)點(diǎn)副本來解決此問題。建立適用的OMKd-Tree面臨兩個(gè)主要挑戰(zhàn)：一是如何建立一個(gè)包含超高維特征向量（成千上萬維）的Kd-Tree，這種情況下，在單一計(jì)算節(jié)點(diǎn)上建立Kd-Tree是不可行的；二是在OMKd-Tree上如何實(shí)現(xiàn)回溯。本文通過以下兩個(gè)方案來解決這兩個(gè)問題。

（1）OMKd-Tree并不是在單個(gè)計(jì)算節(jié)點(diǎn)上建立Kd-Tree，而是在根節(jié)點(diǎn)上建立一個(gè)特性分布樹，即Kd-Tree的上層。這是因?yàn)閿?shù)據(jù)量龐大且維度較高，不可能在單個(gè)節(jié)點(diǎn)上滿足特征向量所有維度，可以采取簡單的對特征進(jìn)行抽樣，并在單個(gè)計(jì)算節(jié)點(diǎn)上使用盡可能多的內(nèi)存。通過計(jì)算Kd-Tree建樹算法抽樣的均值，上面的方法并不會(huì)影響最終Kd-Tree的性能。

（2）OMKd-Tree方法僅在子計(jì)算節(jié)點(diǎn)上執(zhí)行回溯算法，根節(jié)點(diǎn)無需回溯。為判定需要訪問哪個(gè)子計(jì)算節(jié)點(diǎn)，需要計(jì)算到切分點(diǎn)之間的距離，如果距離低于判定閾值，將該計(jì)算節(jié)點(diǎn)包含到下一步需要處理的過程中。

基于MRC-Tree框架實(shí)現(xiàn)MMKd-Tree和OMKd-Tree，如圖3所示，主要分為兩個(gè)階段：

（1）分布式建樹階段：特征向量Map-Reduce將向量集合切分到各個(gè)子計(jì)算節(jié)點(diǎn)，接下來通過索引Map-Reduce在各個(gè)子計(jì)算節(jié)點(diǎn)建立不同的Kd-Tree。

（2）分布式檢索階段：通過分配Map-Reduce將目標(biāo)特征向量分配到合適的子計(jì)算節(jié)點(diǎn)，然后通過匹配計(jì)算Map-Reduce檢索相應(yīng)的Kd-Tree，并進(jìn)行結(jié)果收集和整理，最后輸出結(jié)果。

圖3 基于Map-Reduce的分布式Kd-Tree機(jī)制Fig.3 Distributed Kd-Tree scheme based on the Map-Reduce

4 實(shí)驗(yàn)驗(yàn)證及性能分析

本節(jié)將顯示和討論分布式Kd-Tree索引結(jié)構(gòu)在IBM集群上獲得的實(shí)驗(yàn)結(jié)果。在實(shí)驗(yàn)過程中，由于分布式環(huán)境對外提供其他計(jì)算服務(wù)，本文實(shí)驗(yàn)過程是與其他程序共享分布式資源，因此，在實(shí)驗(yàn)結(jié)果上可能會(huì)出現(xiàn)小幅波動(dòng)。分布式環(huán)境構(gòu)成：1個(gè)Master管理節(jié)點(diǎn)服務(wù)器，8個(gè)刀片服務(wù)器（HS21）計(jì)算節(jié)點(diǎn)，1套8 TB磁盤陣列（IBM DS3400）存儲(chǔ)。

4.1 數(shù)據(jù)集

在實(shí)驗(yàn)中使用兩個(gè)不同統(tǒng)計(jì)類型的測試數(shù)據(jù)集，每種數(shù)據(jù)集都包括兩種不同類型圖像，如圖4所示。

圖4 數(shù)據(jù)集描述Fig.4 The dataset description

（1）測試集

已經(jīng)進(jìn)行標(biāo)注的圖像，作為參照目的。這個(gè)集合中的每個(gè)對象包括兩種類型的圖像：一是基準(zhǔn)圖像，表示要被檢索的真實(shí)圖像，用來驗(yàn)證檢索結(jié)果的正確與否；二是測試圖像集，用來查詢數(shù)據(jù)庫，表示與基準(zhǔn)圖像相近，由基準(zhǔn)圖像經(jīng)過變換后的圖像，例如不同視角、光照條件、縮放比例等。

（2）干擾集

表示構(gòu)成查詢數(shù)據(jù)庫的大部分圖像，盡管這些圖像在一定統(tǒng)計(jì)意義上與測試圖像有聯(lián)系，事實(shí)上與測試圖像集無關(guān)。算法必須能夠識別并過濾掉這些混亂和扭曲圖像，并找到基準(zhǔn)圖像。在現(xiàn)實(shí)的圖像集構(gòu)造過程中，這個(gè)集合將包括所有與基準(zhǔn)圖像語義相近的圖像，例如，與基準(zhǔn)圖像相近的語義是標(biāo)注為建筑類的圖像。

實(shí)驗(yàn)過程中，使用一個(gè)Holidays圖片集測試分布式Kd-tree索引結(jié)構(gòu)的性能。Holidays［9］（1 491幅圖片，4 456個(gè)描述器，500個(gè)檢索），這個(gè)數(shù)據(jù)集主要包含假日旅游的圖片。擾亂數(shù)據(jù)集使用Flickr旅游圖片，通過使用Flickr站點(diǎn)檢索引擎，檢索關(guān)鍵字為“travel”和“Holiday travel”，獲取總計(jì)達(dá)1 M張各種類型的假日旅游的圖片（自然、建筑、大海和火山等）。

最后，該數(shù)據(jù)集總計(jì)1 M張圖片，500個(gè)檢索圖片，每個(gè)圖片平均有1 500個(gè)描述特征。對于所有圖片，總計(jì)特征為15億。在本文中，圖片特征提取方法使用SIFT算法［13］。使用下面公式進(jìn)行檢索精度評估：

該公式表示，檢索返回的Top-k個(gè)圖片中包含基準(zhǔn)圖像在檢索總次數(shù)中所占的比例。其中，rq表示基準(zhǔn)圖像在檢索結(jié)果中的排名，若｛rq≤k｝為真，則｛rq≤k｝＝1。

對于分布式Kd-Tree，為了權(quán)衡精度和檢索時(shí)間，本文限定了每個(gè)特征的回溯范圍，而且這個(gè)范圍由所有Kd-Tree子樹共享。例如，對于MMKd-Tree，回溯限定為B＝3 k，如果一個(gè)特征有兩個(gè)子計(jì)算節(jié)點(diǎn)，則每個(gè)使用1.5 k；若是3個(gè)子計(jì)算節(jié)點(diǎn)，則是1 k。對于具有M個(gè)子計(jì)算節(jié)點(diǎn)的OMKd-Tree，每個(gè)節(jié)點(diǎn)使用B／M個(gè)回溯步驟。

4.2 性能分析

實(shí)驗(yàn)中，通過改變分布式Kd-Tree索引系統(tǒng)中計(jì)算節(jié)點(diǎn)的個(gè)數(shù)M（2≤M≤8）、距離閾值d（0.05≤

d≤0.3）、回溯步驟數(shù)Nb（512≤Nb≤30 k）、圖片規(guī)模Ns（1 k≤Ns≤10 M）、檢索圖片次數(shù)Nr（1≤Nr≤150）來調(diào)節(jié)、測試和分析分布式索引結(jié)構(gòu)的性能。

首先，使用1 M圖片數(shù)據(jù)集，測試不同的參數(shù)對與分布式Kd-Tree性能的影響：距離閾值d、回溯步驟數(shù)Nb和子計(jì)算節(jié)點(diǎn)個(gè)數(shù)為M。

如圖5所示，隨著距離閾值的增大，OMKd-Tree將會(huì)訪問更多的子（葉子）計(jì)算節(jié)點(diǎn)，由于回溯步驟Nb是固定的，葉子節(jié)點(diǎn)的子樹不能夠訪問足夠深度，因此檢索精度會(huì)逐漸降低。而由于回溯步驟確定，檢索CPU時(shí)間沒有明顯變化。而對于MMKd-Tree，距離閾值變化并不會(huì)影響需要訪問的子計(jì)算節(jié)點(diǎn)，因此預(yù)測精度不會(huì)變化，檢索時(shí)間會(huì)隨之略微下降，因?yàn)檫@是顯而易見的，圖中并沒有畫出。

圖5 距離閾值的影響Fig.5 The effect of the distance threshold

如圖6所示，隨著回溯步驟的增大，子（葉子）計(jì)算節(jié)點(diǎn)的個(gè)數(shù)是固定的，訪問葉子節(jié)點(diǎn)的深度會(huì)隨之增大，檢索精度也隨之提高，檢索CPU時(shí)間也隨之提高；顯然，隨著回溯步驟的增大，OMKd-Tree在檢索精度和檢索CPU時(shí)間方面，與MMKd-Tree相比更具優(yōu)勢。

圖6回溯步驟的影響Fig.6 The effect of the backtracking step

圖7 顯示了圖像規(guī)模增長對這兩種索引結(jié)構(gòu)的影響。隨著圖像規(guī)模的增大，樹的深度會(huì)隨之提高，由于回溯步驟、計(jì)算節(jié)點(diǎn)個(gè)數(shù)和距離閾值是恒定的，所以預(yù)測精度隨之下降，檢索CPU時(shí)間呈上升趨勢，吞吐量對于兩種方法在峰值之前都成上升趨勢，顯然OMKd-Tree的吞吐量遠(yuǎn)高于MMKd-Tree，而且當(dāng)圖像規(guī)模為10 M時(shí)，OMKd-Tree吞吐量繼續(xù)呈上升趨勢，而MMKd-Tree開始下降。顯然，與MMKd-Tree相比，OMKd-Tree具有更高的檢索精度、更低的CPU時(shí)間代價(jià)和更高的吞吐量。

如圖8所示，隨著計(jì)算節(jié)點(diǎn)個(gè)數(shù)的增大，回溯步驟、數(shù)據(jù)集規(guī)模和距離閾值都恒定的情況下，OMKd-Tree的預(yù)測精度和檢索CPU時(shí)間幾乎不變，吞吐量明顯提高；對于MMKd-Tree，預(yù)測精度下降，檢索CPU時(shí)間提高，吞吐量也相應(yīng)提高，但提高幅度沒有OMKd-Tree明顯；對于OMKd-Tree，樹頂層的層數(shù)在特征Map-Reduce階段被構(gòu)造。對于MMKd-Tree，定義了圖像數(shù)據(jù)集被分組的個(gè)數(shù)。對于相同數(shù)目的計(jì)算節(jié)點(diǎn)，OMKd-Tree的總體性能（檢索精度、檢索CPU時(shí)間和吞吐量）優(yōu)于MMKd-Tree。特別是，隨著計(jì)算節(jié)點(diǎn)的個(gè)數(shù)增長，OMKd-Tree的檢索CPU時(shí)間幾乎不變，而MMKd-Tree呈增長趨勢。這是因?yàn)?，盡管回溯步驟被分布到所有機(jī)器上，特征向量仍然需要拷貝并發(fā)送到所有計(jì)算節(jié)點(diǎn)上，內(nèi)存拷貝需要耗費(fèi)大量CPU時(shí)間。同時(shí)注意到，吞吐量也隨著計(jì)算節(jié)點(diǎn)的個(gè)數(shù)增加而增加，OMKd-Tree的吞吐量遠(yuǎn)遠(yuǎn)大于MMKd-Tree。

圖7 圖像數(shù)據(jù)庫規(guī)模的影響Fig.7 The effect of image database size

圖9 顯示，不同Top-k的k值對于檢索精度的影響，k的范圍是從1～150。顯而易見，隨著k值增大，檢索精度隨之提高，而且圖像規(guī)模越小檢索精度越高。因?yàn)椋瑥?0 M圖像庫中查找一幅圖像，命中正確圖像的概率為10－7。顯然，數(shù)據(jù)庫規(guī)模越大，命中概率越低，檢索精度越低。

圖9Top-k查詢中k值的影響Fig.9 The effect of k in the Top-k query

5 總結(jié)

本文面向云環(huán)境中大規(guī)模圖像查詢需求，設(shè)計(jì)了一個(gè)基于Map-Reduce模型的分布式樹形結(jié)構(gòu)檢索和計(jì)算抽象框架MRC-Tree，實(shí)現(xiàn)了基于MRC-Tree的分布式的圖像索引結(jié)構(gòu)建立算法OMKd-Tree和MMKd-Tree，并通過實(shí)驗(yàn)分析了兩類算法的性能。本文所提出的高維特征索引機(jī)制是一個(gè)初步嘗試，尚有不少需進(jìn)一步開展的工作，如對于OMKd-Tree算法，通過自適應(yīng)的參數(shù)設(shè)置來進(jìn)一步提高索引結(jié)構(gòu)的性能；融合多種高維特征（包括高層語義特征），拓展MRC-Tree框架以適應(yīng)融合特征，以達(dá)到更好的查詢效果。

［1］Dean J，Ghemawat S.Map-Reduce：Simplified Data Processing on Large clusters［J］.ACM Communication，2008，51（1）：107－113.

［2］Heger D A.A Disquisition on the Performance Behavior of Binary Search Tree Data Structures［J］.European Journal for the Informatics Professional，2004，5（5）：67－75.

［3］Comer D.The Ubiquitous B-Tree［J］.ACM Computing Surveys，1979，11（2）：121－137.

［4］Guttman A.R-Trees：A Dynamic Index Structure for Spatial Searching［C］／／Proceedings of the 1984 ACM SIGMOD International Conference on Management of data.New York：ACM，1984：47－57.

［5］Bentley J L.Multidimensional binary search trees used for as-sociative searching［J］.ACM Communication，1975，18（9）：509－517.

［6］Abhinav SARJE，Srinivas ALURU.A Map-Reduce Style Framework for Trees［R］.Technical Report，2009.

［7］Sarje A，Aluru S.A Map-Reduce Style Framework for Computations on Trees［C］／／Proceedings of 2010 39th International Conference on Parallel Processing.San Diego，California，USA：IEEE，2010：343－352.

［8］楊恒，王慶，何周燦.面向高維圖像特征匹配的多次隨機(jī)子向量量化哈希算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22（3）：494－510. YANG Heng，WANG Qing，HE Zhou-can.Multiple Randomized Sub-vectors Quantization Hashing for High-Dimensional Image Feature Matching［J］.Journal of Computer-Aided Design＆Computer Graphics，2010，22（3）：494－502.（in Chinese）

［9］Silpal-Anan C，Hartley R.Optimised KD-trees for fast image descriptor matching［C］／／Proceedings of 2008 IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，AK：IEEE，2008：1－8.

［10］過潔，徐曉旸，潘金貴.虛擬場景的一種快速優(yōu)化Kd-Tree構(gòu)造方法［J］.電子學(xué)報(bào)，2011，39（8）：1811－1817. GUO Jie，XU Xiao-yang，PAN Jin-gui.Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way［J］.Acta Electronica Sinica，2011，39（8）：1811－1817.（in Chinese）

［11］Aly M，Munich M，Perona P.Indexing in large scale image collections：Scaling properties and benchmark［C］／／Proceedings of the 2011 IEEE Workshop on Applications of Computer Vision.Kona，HI：IEEE，2011：418－425.

［12］Jegou H，Douze M，Schmid C.Hamming embedding and weak geometric consistency for large scale image search［C］／／Proceedings of 2008 10th European Conference on Computer Vision：Part I.Marseille，F(xiàn)rance：IEEE，2008：304－317.

［13］Lowe D G.Object recognition from local scale-invariant features［C］／／Proceedings of the 7th IEEE International Conference on Computer Vision.Kerkyra：IEEE，1999：1150－1157.

LEI Ting was born in Chenzhou，Hunan Province，in 1981.She is now a lecturer with the M.S.degree and also a CCF member.Her research concerns data mining，clound computing.

Email：tinglei.uestc＠gmail.com

Large Scale Graph Data Index Based on MKd-Tree in Cloud Environment

LEI Ting
（Department of Communication Engineering，Chengdu Technological University，Chengdu 611730，China）

Managing the high-dimensional，large-scale data needs extremely high computational load.Traditional centralized indexing techniques apparently become impractical.To address the demanding needs caused by this rapidly growing，large-scale，and high-dimensional information ecology，a high-level distributed framework for searches and computations on tree indexing structures based on Map-Reduce in the Hadoop environment，MRCTree（Computation based on Map-Reduce on tree structures）is achieved.And then，two MKd-Tree（Kd-Tree based on Map-Reduce）index structures based on MRC-Tree framework，OMKd-Tree（Build one distributed Kd-Tree based on Map-Reduce）and MMKd-tree（Build multiple Kd-Trees by splitting data equally based on Map-Reduce）are proposed.Finally，the theoretical analysis and experiment results illustrate that the methods are highly effective and extensible to the similarity search in high-dimensional data environment.

high-demensional database；graph data；index structure；distributed tree index structure framework；Map-Reduce framework；MKd-Tree

date：2013－01－05；Revised date：2013－06－18

??通訊作者：tinglei.uestc＠gmail.comCorresponding author：tinglei.uestc＠gmail.com

TP391

A

1001－893X（2013）07－0909－08

雷婷（1981—），女，湖南郴州人，碩士，講師，CCF會(huì)員，主要研究方向?yàn)楹Ａ繑?shù)據(jù)挖掘、云計(jì)算。

10.3969／j.issn.1001－893x.2013.07.017

2013－01－05；

2013－06－18