王昂，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

分布式度量索引模型設(shè)計(jì)研究

王昂，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

度量空間的索引是傳統(tǒng)數(shù)據(jù)領(lǐng)域熱點(diǎn)問(wèn)題?；诳臻g樹(shù)索引思想，提出一種高性能、高可擴(kuò)展的面向大規(guī)模高維空間數(shù)據(jù)的分布式索引模型。實(shí)驗(yàn)表明，該方案與傳統(tǒng)索引結(jié)構(gòu)相比具有明顯的性能提高，同時(shí)面對(duì)數(shù)據(jù)規(guī)模的爆炸性增長(zhǎng)具有高可擴(kuò)展性。

度量空間；最近鄰查詢；大數(shù)據(jù)

0 引言

隨著無(wú)線通信技術(shù)和移動(dòng)終端技術(shù)的飛速發(fā)展，移動(dòng)互聯(lián)網(wǎng)應(yīng)運(yùn)而生。隨之而來(lái)的，是數(shù)據(jù)量急速膨脹，這為傳統(tǒng)數(shù)據(jù)處理方法帶來(lái)嚴(yán)峻的挑戰(zhàn)。在度量空間中，如何進(jìn)行高維向量的相似性檢索問(wèn)題一直是數(shù)據(jù)處理與檢索領(lǐng)域的熱點(diǎn)[2]。在地理信息系統(tǒng)、圖像檢索[1]、多媒體數(shù)據(jù)庫(kù)、模式識(shí)別[6]、超大規(guī)模集成電路、生物DNA數(shù)據(jù)庫(kù)等眾多領(lǐng)域都有廣泛的應(yīng)用[3～4]。

常見(jiàn)的高維信息索引方法都試圖使查詢達(dá)到近乎線性的增長(zhǎng)，以應(yīng)對(duì)數(shù)據(jù)膨脹。伴隨著移動(dòng)互聯(lián)網(wǎng)信息時(shí)代的到來(lái)，且數(shù)據(jù)記錄采集設(shè)備的不斷普及，各種社會(huì)記錄、多媒體、科學(xué)計(jì)算等數(shù)據(jù)爆炸性增長(zhǎng)，使得這一問(wèn)題變得更加尖銳。如何進(jìn)行分布式并行度量空間索引，國(guó)內(nèi)外學(xué)者鮮有研究。本文基于MVP-Tree結(jié)構(gòu)[5]提出高可擴(kuò)展的面向大規(guī)模高維空間數(shù)據(jù)的分布式索引模型。

1 分布式度量索引模型

本節(jié)由模型框架、空間劃分、插入與檢索機(jī)制、擴(kuò)展性等幾方面對(duì)本文模型進(jìn)行介紹，并進(jìn)一步探討模型思想與解決方案。

該模型借助于樹(shù)結(jié)構(gòu)將度量空間進(jìn)行劃分，如圖1（a）所示。對(duì)空間索引樹(shù)進(jìn)行水平切割，上層淺層次劃分的空間本文稱之為“主空間”，下部劃分出的空間稱之為“次空間”。圖1（a）中將度量空間劃分成為8個(gè)次空間，在實(shí)際應(yīng)用中可以根據(jù)現(xiàn)實(shí)需求進(jìn)行調(diào)整。對(duì)索引樹(shù)的切割平面越靠近根節(jié)點(diǎn)，劃分出的次空間數(shù)目越少，則每個(gè)次空間就越大，分布式機(jī)器負(fù)載就越重。主空間索引樹(shù)保存在Master主機(jī)中，Master主機(jī)負(fù)責(zé)對(duì)用戶提交的插入與查詢操作進(jìn)行導(dǎo)引，并對(duì)整個(gè)系統(tǒng)進(jìn)行監(jiān)控與負(fù)載均衡。劃分好的次空間分別放置于分布式Slave機(jī)器集群上，分布式Slave機(jī)器會(huì)對(duì)分配到的空間構(gòu)建MVP-Tree索引，用于其所管轄空間的對(duì)象插入與查詢。圖1（b）是以圓形向外擴(kuò)展的索引樹(shù)，中間陰影部分保存在Master主機(jī)中作為基本索引。四周擴(kuò)散的8種顏色代表八個(gè)次空間，是存儲(chǔ)在分布式Slave機(jī)器上的MVP-Tree索引。

本文模型度量空間索引模型框架如圖2所示，用戶的請(qǐng)求首先發(fā)送到Master主機(jī)（圖2中實(shí)際為Master集群，其中包含多個(gè)Master主機(jī)），然后Master主機(jī)根據(jù)自身存儲(chǔ)的索引結(jié)構(gòu)進(jìn)行相應(yīng)操作。在插入操作時(shí)，Master主機(jī)將按照度量空間劃分原則將點(diǎn)插入相應(yīng)的分布式Slave節(jié)點(diǎn)。當(dāng)用戶請(qǐng)求檢索操作時(shí)，Master主機(jī)根據(jù)查詢算法返回給用戶相應(yīng)的Slave查詢接口，由用戶向相應(yīng)的Slave節(jié)點(diǎn)尋求檢索結(jié)果，以減輕Master主機(jī)負(fù)擔(dān)。

圖1 空間劃分圖

圖2 模型框架

當(dāng)用戶需要插入一個(gè)新的對(duì)象時(shí)，插入請(qǐng)求會(huì)發(fā)送到Master主機(jī)。Master主機(jī)通過(guò)查詢索引樹(shù)求出其所落在的次空間區(qū)域，然后將插入信息傳送到相應(yīng)的Slave節(jié)點(diǎn)。Slave節(jié)點(diǎn)收到請(qǐng)求后將節(jié)點(diǎn)插入到其自身空間索引樹(shù)中。

空間劃分后的另外一個(gè)重要問(wèn)題是如何處理用戶的近鄰檢索請(qǐng)求。當(dāng)用戶請(qǐng)求檢索時(shí)，首先將檢索指令發(fā)送到Maser主機(jī)。Master主機(jī)根據(jù)自身構(gòu)建的主空間劃分索引樹(shù)計(jì)算，返回需要檢索的Slave機(jī)器接口信息?？蛻舳朔庋b好的API會(huì)自動(dòng)根據(jù)Master主機(jī)返回的Slave信息去請(qǐng)求數(shù)據(jù)。Slave節(jié)點(diǎn)收到請(qǐng)求后，檢索查詢節(jié)點(diǎn)的近鄰集合。返回的Slave數(shù)目并不一定只有一個(gè)，當(dāng)查詢對(duì)象Y位于度量空間劃分超平面附近時(shí)，則需要從多個(gè)Slave節(jié)點(diǎn)上尋找近鄰。

2 實(shí)驗(yàn)分析

為說(shuō)明本文模型的有效性，將本文模型與MVPTree算法比較，并通過(guò)調(diào)節(jié)模型參數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)。本文模型可通過(guò)調(diào)整Master主機(jī)數(shù)目和Slave節(jié)點(diǎn)數(shù)目來(lái)應(yīng)對(duì)不同的應(yīng)用場(chǎng)景。實(shí)驗(yàn)中距離度量采用的歐幾里得距離進(jìn)行計(jì)算，實(shí)驗(yàn)具體細(xì)節(jié)將在本節(jié)中進(jìn)行說(shuō)明。

本文實(shí)驗(yàn)采用人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。人工數(shù)據(jù)集根據(jù)實(shí)驗(yàn)需要隨機(jī)生成不同維度，不同數(shù)量的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，以驗(yàn)證模型的有效性。本文分別在64維和128維向量數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，每個(gè)維度取值為0～9之間的隨機(jī)數(shù)。

由于MVP-Tree索引結(jié)構(gòu)的性能較于VP-Tree、RTree、KD-Tree要好，故本文Slave機(jī)器采用MVP-Tree結(jié)構(gòu)。由于本文模型的模塊化設(shè)計(jì)，分布式Slave機(jī)器上的索引樹(shù)可以用任何一種度量空間索引結(jié)構(gòu)進(jìn)行代替。

面對(duì)大規(guī)模數(shù)據(jù)，通過(guò)調(diào)整主空間分區(qū)數(shù)目可以對(duì)數(shù)據(jù)進(jìn)行均衡負(fù)載。本文模型可以非常容易地通過(guò)增加Slave節(jié)點(diǎn)數(shù)目分擔(dān)負(fù)載。通過(guò)合理地選擇度量切割半徑，可以將度量空間中的點(diǎn)較為均勻地分布到Slave節(jié)點(diǎn)上。本文分別通過(guò)64維和128維的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。圖3（a）是基于64維數(shù)據(jù)進(jìn)行的一次近鄰檢索查詢耗時(shí)圖，其中橫坐標(biāo)第一行為數(shù)據(jù)規(guī)模，第二行和第三行為時(shí)間消耗具體數(shù)值，縱坐標(biāo)為消耗時(shí)間，單位為s。從實(shí)驗(yàn)結(jié)果圖可知，在數(shù)據(jù)規(guī)模較小時(shí)，本文模型并未體現(xiàn)出其優(yōu)勢(shì)。尤其是在數(shù)據(jù)量為100時(shí)，本文模型所消耗時(shí)間較之于MVP-Tree大0.001s，這是由于本文模型需要從Master主機(jī)中獲取需要被檢索的Slave機(jī)器接口信息，然后發(fā)送至客戶端。隨著數(shù)據(jù)量的增加，本文模型的優(yōu)勢(shì)逐漸凸顯。當(dāng)數(shù)據(jù)量達(dá)到500000之后，本文模型耗時(shí)是MVP-Tree一半左右，而且增長(zhǎng)較為平滑，查詢性能表現(xiàn)更好。數(shù)據(jù)量急速膨脹，這使得從Master主機(jī)檢索Slave機(jī)器接口信息的時(shí)間越來(lái)越顯得微不足道。當(dāng)數(shù)據(jù)從64維變?yōu)?28維時(shí)，如圖3（b）所示，本文模型依然顯示出良好的性能。

圖3 MVP-Tree與本文模型最近鄰查詢時(shí)間

3 結(jié)語(yǔ)

面對(duì)大規(guī)模海量高維數(shù)據(jù)的查詢檢索，本文基于空間樹(shù)索引的理念，提出具有高性能、高可擴(kuò)展的面向大規(guī)模高維空間數(shù)據(jù)的分布式索引模型。本文模型與其他結(jié)構(gòu)索引樹(shù)相同，都是對(duì)度量空間進(jìn)行劃分。但由于單機(jī)數(shù)據(jù)處理能力有限，可擴(kuò)展性差等缺點(diǎn)，本文模型樹(shù)將多臺(tái)機(jī)器進(jìn)行整合，并行地進(jìn)行分布式索引，極大地提高的索引性能。此外，還可通過(guò)增加次空間劃分?jǐn)?shù)目來(lái)應(yīng)對(duì)數(shù)據(jù)膨脹問(wèn)題。實(shí)驗(yàn)表明本文模型可以有效地解決大規(guī)模高維空間索引難題，為分布式度量空間索引提供了很有價(jià)值的借鑒意義。

[1] Google Images.[2014-03-20].https://images.google.com.hk

[2] Kamel I,Faloutsos C.Hilbert R2tree:An Improved R-tree Using Fractals[C].Proceedings of the 20th VLDB,Santiago,Chile,1994: 500～509

[3] 侯玨,劉軼,鄭方,等.基于VP樹(shù)結(jié)構(gòu)的多層匹配算法在哼唱識(shí)別中的應(yīng)用[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版）.2009.49（S1）: 1419～1424

[4] 凌康.基于位置敏感哈希的相似性搜索研究[D].南京：南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，2012

[5] Tolga B,Meral O.Distance-Based Indexing for High-Dimensional Metric Spaces[C].Proceeding SIGMOD'97 Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data.New York,1997:357～368

[6] 陳濤,謝陽(yáng)群.文本分類(lèi)中的特征降維方法綜述[J].情報(bào)學(xué)報(bào),2005,24（6）:690～695

Research on the Design of Distributed Indexing Model

WANG Ang，LI Chuan
（College of Computer Science，Sichuan University，Chengdu 610065）

Indexing metric spaces has always been a hot subject in the area of data processing.Based on the idea of indexing tree in metric space, proposes a distributed indexing model for large high-dimensional metric spaces data.Experiments of large high-dimensional metric spaces data show the proposed model has more significant performance improvement compared with the traditional indexing structure and is highly scalable with the explosive growth of data.

Metric Space;Nearest Neighbor Query;Big Data

1007-1423（2015）03-0014-04

10.3969/j.issn.1007-1423.2015.03.004

王昂（1990-），男，山東棗莊人，碩士，研究方向?yàn)閿?shù)據(jù)挖掘

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)庫(kù)和數(shù)據(jù)挖掘等

2014-12-25

2015-01-14

國(guó)家自然科學(xué)基金（No.61103043）、國(guó)家“十二五”科技支撐計(jì)劃項(xiàng)目（No.2012BAG04B02）、武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目（No.SKLSE2012-09-26）