高维空间范围查询并行算法研究

徐红波，胡 文，潘海为，高 祥，刘润涛

(1.哈尔滨商业大学计算机与信息工程学院，哈尔滨150028;2.哈尔滨工程大学计算机科学与技术学院，哈尔滨150001;3.哈尔滨理工大学应用科学学院，哈尔滨150080)

空间数据库被广泛地应用到多个领域中.如今对海量复杂空间信息进行查询越来越需要空间数据库的支持.空间范围查询查找点集中位于查询区域中的点[1].

线性扫描范围查询算法BFRQ依次扫描点集中每个点，计算该点是否位于查询区域中，如果位于该查询区域中，那么当前点在结果集中，否则继续扫描下一个点[2].

基于R树空间范围查询算法RRQ从根结点开始深度优先遍历R树.若访问的结点是索引结点，则依次判断该结点的分支对应的最小外包矩形是否与查询区域相交，若是，递归遍历该分支对应的子树，否则，继续判断下个分支;若访问的结点是叶子结点，则依次判断该结点中存储的数据点是否落在查询区域中，若是，则该点在结果集中，否则，继续判断下个点.R树中存在最小外包矩形之间交叠问题.基于R树空间范围查询算法的执行时间指数依赖于空间维度.该现象被称为“维度灾难”[3].

基于VA文件空间范围查询算法VARQ顺序扫描文件中每个位串，若查询区域包含位串所在网格，则位串对应点在结果集中，否则，判断查询区域与位串对应的网格是否相交，若相交，则访问数据文件对应点的坐标，判断该点是否落在查询区域中，若是，则该点在结果集中[4].

基于NB树空间范围查询算法NBRQ在树中定位查询点q，然后向前和向后分别扫描前驱点Pp和后继点Ps.当 Pp满足 Norm(Pp)＜Norm(q)－DIAMETER时，退出向前遍历，否则，判断Pp与q之间的距离是否小于查询半径DIAMETER，若小于，则Pp在结果集中，否则，继续判断Pp的前驱点，直到双向链表的表头为止;当ps满足Norm(ps)＞Norm(q)+DIAMETER时，退出向后遍历操作，否则，判断ps与q之间的距离是否小于DIAMETER，若小于，ps在结果集中，否则，继续访问ps的后继点，直到双向链表的表尾为止[5].

本文采用并行技术[6]解决高维空间范围查询问题，将d维范围查询操作转换到d个从处理机上的一维范围查询操作.从处理并行执行范围查询操作，大大减少了算法的查询时间.

1 基本概念

二维空间查询区域对应矩形.三维空间查询区域对应长方体.以此类推，d维空间查询区域对应超矩形.超矩形的形状可以由主对角线上的两个顶点确定，但是本文将超矩形投影到每一维上，用投影线段表示超矩形.

例如，在图1中矩形可以由x轴上的线段[27，56]和y轴上的线段[28，68]表示.d维空间查询区域在每一维上的投影之后将得到d条线段用来表示超矩形.

图1 二维空间查询区域

定义1 d维空间查询区域定义为Rd=((l1，u1)，(l2，u2)，...，(ld，ud))，其中 li≤ui(i=1，...，d).

定义2 给定点集P={p1，p2，…，pn}，点集P 中每个点 pi=(pi1，pi2，...，pid)，点集 P 在第 i维上的投影Pi定义为由点集P中每个点的第i维坐标组成的集合，记作Pi={p1i，p2i，…，pni}.

定义3 给定点集P={p1，p2，…，pn}，点集P 中每个点 pi=(pi1，pi2，...，pid)，查询区域 Rd=((l1，u1)，(l2，u2)，...，(ld，ud))，d 维空间范围查询定义为RQ(P，Rd)={p(p1，p2，…，pn)|(p∈P)∧ (l1≤p1≤u1)∧ (l2≤p2≤u2)∧…∧ (ld≤pd≤ud)}.

空间范围查询并行算法在执行之前需要建立索引结构.索引结构采用B+树.B+树是一种平衡多路查找树.算法首先计算点集P在每一维上的投影Pi，然后在投影Pi上建立B+树，因此点集P经过投影之后对应d棵B+树.具体操作过程如图2所示.

图2 索引结构创建过程

2 并行算法

空间范围查询并行算法划分为2个阶段:索引创建阶段和执行查询阶段.索引创建阶段:首先根据空间维度d，主节点机调用d个从节点机并行计算，将保存在主节点机中的点集P分别发送到d个从节点上，在第i个从节点机中计算点集P在第i维上的投影Pi，然后在投影Pi上建立 B+树Bi.执行查询阶段:给定查询区域Rd，d个从节点机并行查询在B+树Bi中位于线段[li，ui]上的点集，然后每个从节点机将查询结果发送给主节点机，主节点机只需计算这些点集的交集，即为范围查询的结果.

算法PRQ(P，Rd)

输入:点集P，查询区域Rd;

输出:点集P落在查询区域Rd中的点集r;

BEGIN

call d slave node processors;

send point set P to d slave node processors;

1:for the ith slave node processors do

Pi={p1i，p2i，…，pni};

BuildBTree(Pi);

2:for the ith slave node processors do

ri=Search([li，ui]，Bi);

send rito the master node processors;

r=φ;

3:for i=1 to d do

r=r∩ri;

return r;

END

函数BuildBTree(Pi)的功能是在投影Pi上构建B+树，将投影Pi中的每个点依次插入到B+树中.若将插入操作作为单位操作，则函数BuildBTree的时间复杂度是O(n).

函数 Search([li，ui]，Bi)的功能是在 B+树Bi中查询位于区间[li，ui]上的点.函数Search首先根据关键字li在B+树Bi的双向链表中查找其所在的位置，然后顺着链表结构向右扫描，直到关键字大于Ui为止.图3给出函数Search的执行过程，给定区间[3，6]，首先根据关键字3在B+树中向下进行搜索，直到定位到双向链表中第一个节点，第一个节点的第3个关键字正好等于3，然后沿着双向链表向右扫描每个关键字，直到第三个叶子节点中的关键字7为止，返回关键字对应的点集{p3，p4，p5，p6}.

图3 函数Search的执行过程

定理1 算法PRQ的空间复杂度为O(dn)，时间复杂度为O(h+n(ui－li)/(uimax－limin)+d).

证明:(空间复杂度)d个从节点机需要分别存储包含n个点的点集P，故算法的空间复杂度为O(dn).(时间复杂度)索引创建阶段需要计算点集的投影和B+树，需要非常大的计算量，但是索引创建阶段属于算法的初始化阶段，只需执行1次，之后只对索引结构B+树进行更新操作，因此算法PRQ的第1步操作与算法的时间复杂度无关，算法的时间复杂度与第2步和第3步操作相关.假设点集P中的点是均匀分布的，函数 Search([li，ui]，Bi)首先在B+树Bi双向链表中定位li的位置，需要跟索引节点中的关键字进行比较，假设B+树的高为h，需要同h个索引节点进行关键字比较才能够定位li的位置.之后，只需要沿着双向链表向右依次扫描关键字是否小于ui，那么落在区间[li，ui]上关键字个数等于 n(ui－ li)/(uimaxlimax)，因此函数Search的时间复杂度为O(h+n(ui－li)/(uimax－ limin))，其中 uimax为投影 Pi的最大值，limin为投影Pi的最小值.第3步操作是求d个Ri的交集，其时间复杂度为d.故算法的时间复杂度是 O(h+n(ui－li)/(uimax－limin)+d)，证毕.

3 实验结果

为了验证范围查询并行算法的效率，本文比较算法PRQ与算法BFRQ、VARQ、RRQ之间的查询性能.编程环境:1.86GHz赛扬处理器、1G内存、120G硬盘、Windows XP操作系统、Visual C++.net 2005.测试数据为由随机函数产生的满足均与分布的数据.

实验1考查数据量对查询时间的影响，实验中使用的数据是2维向量，数据量从10万条到160万条，查询区域面积是总面积的1%.从表1可知，算法PRQ的查询时间小于算法RRQ.算法BFRQ和算法VARQ的查询时间最多.

表1 数据量与执行时间的关系

实验2验证当空间维度变化时对查询时间的影响.实验中随机生成维度分别为32、64、128、256、512的点数据，查询区域在每维上的区间长度是该维长度的1/10，数据量均为100万.

表2 空间维度与执行时间的关系

从表2的数据可知，随着空间维度的增加，算法PRQ的性能依然高效，而其他算法的性能明显恶化.在d=512时算法BFRQ的查询时间小于算法RRQ.当d≥128时算法VARQ的查询时间小于算法BFRQ.

4 结语

现有空间范围串行查询算法应用到高维数据空间时执行效率较低.本文采用并行技术提出一种高维空间范围查询并行算法.实验结果表明在高维数据空间中算法的查询效率优于线性扫描算法、基于R树、VA文件空间范围查询算法.算法可行且有效.

[1] 郝忠孝.时空数据库查询与推理[M].北京:科学出版社，2010.

[2] 徐红波，郝忠孝.一种采用Z曲线高维空间范围查询算法[J].小型微型计算机系统，2009，30(10):1952－1955.

[3] BEYER K，GOLDSTEIN J，RAMAKRISHNAN R.When is“nearest neighbor”meaningful[C]//Proceedings of the 7th International Conference on Database Theory，[S.l.]:[s.n.]，1999，217－235.

[4] WEBER R，BLOTT S.An Approximation－based data structure for similarity search[R].ESPRIT Project HERMES，1997.

[5] MANUEL J F，JOAQUIM A J.Indexing high－dimensional data for content－ based retrieval in large databases[C]//Proceedings of the 8th International Conference on Database Systems for Advanced Applications，[S.l.]:[s.n.]，2003:267 －274.

[6] 陈国良，孙广中，徐 云，等.并行算法研究方法学[J].计算机学报，2008，31(9):1493－1502.