分布式度量索引模型設計研究

王昂，李川

（四川大學計算機學院，成都 610065）

分布式度量索引模型設計研究

王昂，李川

（四川大學計算機學院，成都 610065）

度量空間的索引是傳統數據領域熱點問題。基于空間樹索引思想，提出一種高性能、高可擴展的面向大規模高維空間數據的分布式索引模型。實驗表明，該方案與傳統索引結構相比具有明顯的性能提高，同時面對數據規模的爆炸性增長具有高可擴展性。

度量空間；最近鄰查詢；大數據

0 引言

隨著無線通信技術和移動終端技術的飛速發展，移動互聯網應運而生。隨之而來的，是數據量急速膨脹，這為傳統數據處理方法帶來嚴峻的挑戰。在度量空間中，如何進行高維向量的相似性檢索問題一直是數據處理與檢索領域的熱點[2]。在地理信息系統、圖像檢索[1]、多媒體數據庫、模式識別[6]、超大規模集成電路、生物DNA數據庫等眾多領域都有廣泛的應用[3～4]。

常見的高維信息索引方法都試圖使查詢達到近乎線性的增長，以應對數據膨脹。伴隨著移動互聯網信息時代的到來，且數據記錄采集設備的不斷普及，各種社會記錄、多媒體、科學計算等數據爆炸性增長，使得這一問題變得更加尖銳。如何進行分布式并行度量空間索引，國內外學者鮮有研究。本文基于MVP-Tree結構[5]提出高可擴展的面向大規模高維空間數據的分布式索引模型。

1 分布式度量索引模型

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

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

本文模型度量空間索引模型框架如圖2所示，用戶的請求首先發送到Master主機（圖2中實際為Master集群，其中包含多個Master主機），然后Master主機根據自身存儲的索引結構進行相應操作。在插入操作時，Master主機將按照度量空間劃分原則將點插入相應的分布式Slave節點。當用戶請求檢索操作時，Master主機根據查詢算法返回給用戶相應的Slave查詢接口，由用戶向相應的Slave節點尋求檢索結果，以減輕Master主機負擔。

圖1 空間劃分圖

圖2 模型框架

當用戶需要插入一個新的對象時，插入請求會發送到Master主機。Master主機通過查詢索引樹求出其所落在的次空間區域，然后將插入信息傳送到相應的Slave節點。Slave節點收到請求后將節點插入到其自身空間索引樹中。

空間劃分后的另外一個重要問題是如何處理用戶的近鄰檢索請求。當用戶請求檢索時，首先將檢索指令發送到Maser主機。Master主機根據自身構建的主空間劃分索引樹計算，返回需要檢索的Slave機器接口信息。客戶端封裝好的API會自動根據Master主機返回的Slave信息去請求數據。Slave節點收到請求后，檢索查詢節點的近鄰集合。返回的Slave數目并不一定只有一個，當查詢對象Y位于度量空間劃分超平面附近時，則需要從多個Slave節點上尋找近鄰。

2 實驗分析

為說明本文模型的有效性，將本文模型與MVPTree算法比較，并通過調節模型參數進行對比實驗。本文模型可通過調整Master主機數目和Slave節點數目來應對不同的應用場景。實驗中距離度量采用的歐幾里得距離進行計算，實驗具體細節將在本節中進行說明。

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

由于MVP-Tree索引結構的性能較于VP-Tree、RTree、KD-Tree要好，故本文Slave機器采用MVP-Tree結構。由于本文模型的模塊化設計，分布式Slave機器上的索引樹可以用任何一種度量空間索引結構進行代替。

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

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

3 結語

面對大規模海量高維數據的查詢檢索，本文基于空間樹索引的理念，提出具有高性能、高可擴展的面向大規模高維空間數據的分布式索引模型。本文模型與其他結構索引樹相同，都是對度量空間進行劃分。但由于單機數據處理能力有限，可擴展性差等缺點，本文模型樹將多臺機器進行整合，并行地進行分布式索引，極大地提高的索引性能。此外，還可通過增加次空間劃分數目來應對數據膨脹問題。實驗表明本文模型可以有效地解決大規模高維空間索引難題，為分布式度量空間索引提供了很有價值的借鑒意義。

[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樹結構的多層匹配算法在哼唱識別中的應用[J].清華大學學報（自然科學版）.2009.49（S1）: 1419～1424

[4] 凌康.基于位置敏感哈希的相似性搜索研究[D].南京：南京大學計算機科學與技術系，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] 陳濤,謝陽群.文本分類中的特征降維方法綜述[J].情報學報,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-），男，山東棗莊人，碩士，研究方向為數據挖掘

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導師，研究方向為數據庫和數據挖掘等

2014-12-25

2015-01-14

國家自然科學基金（No.61103043）、國家“十二五”科技支撐計劃項目（No.2012BAG04B02）、武漢大學軟件工程國家重點實驗室開放基金項目（No.SKLSE2012-09-26）