雷婷??

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

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

雷婷??

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

由于高維屬性和海量數(shù)據(jù)所帶來(lái)的影響，數(shù)據(jù)管理需要相當(dāng)高的計(jì)算負(fù)載，傳統(tǒng)的集中索引技術(shù)已經(jīng)變得不切實(shí)際。為滿(mǎn)足數(shù)據(jù)的快速增長(zhǎng)、海量和高維特性的要求，實(shí)現(xiàn)了一個(gè)高層次的分布式樹(shù)形索引結(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ù)庫(kù)；圖數(shù)據(jù)；索引結(jié)構(gòu)；分布式樹(shù)形索引結(jié)構(gòu)框架；Map-Reduce框架；MKd-Tree

1 引言

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

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

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

2 MRC-Tree框架

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

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

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

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

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

操作依賴(lài)于用戶(hù)指定的select函數(shù)，該函數(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è)檢索路徑上，沒(méi)有節(jié)點(diǎn)被包含在檢索結(jié)果集合中；

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

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

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

函數(shù)treeCompute用于處理樹(shù)形結(jié)構(gòu)中的節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)中的信息：treeCompute（μ）ㄧ→μ′。其中，μ′＝（kμ，X′μ）表示更新節(jié)點(diǎn)μ。在更新節(jié)點(diǎn)μ過(guò)程中，其他節(jié)點(diǎn)的集合也需要被考慮。用戶(hù)指定如何確定與μ相關(guān)的節(jié)點(diǎn)列表，并通過(guò)generate函數(shù)在μ上定義交集。使用用戶(hù)指定的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è)依賴(lài)標(biāo)識(shí)dy。這個(gè)標(biāo)識(shí)用來(lái)表明，若多個(gè)交集之間存在依賴(lài)，是否需要在函數(shù)中考慮，generate（μ）→（list（ν），dy）。

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

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

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

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

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

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

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

（5）范圍檢索：對(duì)于一個(gè)空間樹(shù)形結(jié)構(gòu)，樹(shù)中每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著Rd空間中的一個(gè)盒子。假設(shè)需要在樹(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最簡(jiǎn)單的方式，首先根據(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)的主存。接下來(lái)，為每個(gè)數(shù)據(jù)塊在子計(jì)算節(jié)點(diǎn)上分別建立一個(gè)獨(dú)立的Kd-Tree。檢索過(guò)程中，根計(jì)算節(jié)點(diǎn)接受目標(biāo)檢索特征向量，并將特征傳遞給所有的子計(jì)算節(jié)點(diǎn)，然后收集返回結(jié)果并整合，輸出最終排序好的結(jié)果；

（2）OMKd-Tree：該方法并行化過(guò)程中僅僅建立一棵Kd-Tree，其上部位于根計(jì)算節(jié)點(diǎn)，下部被切分到各個(gè)子計(jì)算節(jié)點(diǎn)，存儲(chǔ)特征的葉子節(jié)點(diǎn)也位于這些子節(jié)點(diǎn)上。檢索過(guò)程中，根據(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子樹(shù)計(jì)算最近鄰，返回結(jié)果給根計(jì)算節(jié)點(diǎn)。最后，根計(jì)算節(jié)點(diǎn)進(jìn)行結(jié)果整合排序，輸出最終排序好的結(jié)果。

顯而易見(jiàn)，OMKd-Tree最大的優(yōu)點(diǎn)是對(duì)于單個(gè)特征向量?jī)H需要訪(fǎng)問(wèn)少量子計(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ì)成為瓶頸，本文通過(guò)引入多個(gè)根計(jì)算節(jié)點(diǎn)副本來(lái)解決此問(wèn)題。建立適用的OMKd-Tree面臨兩個(gè)主要挑戰(zhàn)：一是如何建立一個(gè)包含超高維特征向量（成千上萬(wàn)維）的Kd-Tree，這種情況下，在單一計(jì)算節(jié)點(diǎn)上建立Kd-Tree是不可行的；二是在OMKd-Tree上如何實(shí)現(xiàn)回溯。本文通過(guò)以下兩個(gè)方案來(lái)解決這兩個(gè)問(wèn)題。

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

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

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

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

（2）分布式檢索階段：通過(guò)分配Map-Reduce將目標(biāo)特征向量分配到合適的子計(jì)算節(jié)點(diǎn)，然后通過(guò)匹配計(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)過(guò)程中，由于分布式環(huán)境對(duì)外提供其他計(jì)算服務(wù)，本文實(shí)驗(yàn)過(guò)程是與其他程序共享分布式資源，因此，在實(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磁盤(pán)陣列（IBM DS3400）存儲(chǔ)。

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

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

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

（1）測(cè)試集

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

（2）干擾集

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

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

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

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

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

4.2 性能分析

實(shí)驗(yàn)中，通過(guò)改變分布式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）來(lái)調(diào)節(jié)、測(cè)試和分析分布式索引結(jié)構(gòu)的性能。

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

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

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

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

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

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

如圖8所示，隨著計(jì)算節(jié)點(diǎn)個(gè)數(shù)的增大，回溯步驟、數(shù)據(jù)集規(guī)模和距離閾值都恒定的情況下，OMKd-Tree的預(yù)測(cè)精度和檢索CPU時(shí)間幾乎不變，吞吐量明顯提高；對(duì)于MMKd-Tree，預(yù)測(cè)精度下降，檢索CPU時(shí)間提高，吞吐量也相應(yīng)提高，但提高幅度沒(méi)有OMKd-Tree明顯；對(duì)于OMKd-Tree，樹(shù)頂層的層數(shù)在特征Map-Reduce階段被構(gòu)造。對(duì)于MMKd-Tree，定義了圖像數(shù)據(jù)集被分組的個(gè)數(shù)。對(duì)于相同數(shù)目的計(jì)算節(jié)點(diǎn)，OMKd-Tree的總體性能（檢索精度、檢索CPU時(shí)間和吞吐量）優(yōu)于MMKd-Tree。特別是，隨著計(jì)算節(jié)點(diǎn)的個(gè)數(shù)增長(zhǎng)，OMKd-Tree的檢索CPU時(shí)間幾乎不變，而MMKd-Tree呈增長(zhǎng)趨勢(shì)。這是因?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ù)庫(kù)規(guī)模的影響Fig.7 The effect of image database size

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

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

5 總結(jié)

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

［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］過(guò)潔，徐曉旸，潘金貴.虛擬場(chǎng)景的一種快速優(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