王昂，李川

（四川大学计算机学院，成都 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）