一种基于距离的求解二维空间中代表性节点集的算法

摘要

本发明提供了一种新的基于距离的求解二维空间中代表性Skyl？ine节点集的算法，输入数据集，用BNL算法计算数据集中的Skyl？ine点集Q；对点集Q排序后求出初始点到其它任意Skyl？ine点的曼哈顿距离值并存储；求出Skyline点集中的k个代表性Skyline点；返回k个代表性Skyl？ine点。算法时间复杂度为O(k2log3m)，远低于现有技术中DRS算法的时间复杂度。

说明书

技术领域

本发明涉及一种新的基于距离的求解二维空间中代表性节点集 的算法(New Distance-based Representative Skyline,简称NDRS)。

背景技术

Skyline查询问题是由Borzsonyi在2001提出来的。近年来， Skyline的查询处理吸引了大批数据库研究者的注意力，迅速成为了 数据库领域的一个研究热点，大量的Skyline查询处理算法孕育而生。 已有的成果主要覆盖三个方面：

(1)集中式数据库上的Skyline查询处理：包括BNL算法(Block  Nested Loop)、SFS算法(Sort Filter Skyline)、分治算法(Divide  and Conquer)、位图算法(Bitmap)、索引算法(Index)[5]、NN算 法(Nearest Neighbor)、BBS(Branch and Bound Skyline)[3]等。

(2)分布式数据库上的Skyline查询处理：包括针对普通分布 式环境下的Skyline计算、特殊分布式环境下的Skyline计算、对等网 络上的Skyline计算等。

(3)其它计算模型下的Skyline查询处理：包括Skyline结果集 大小及计算开销估算、在任意子空间上的Skyline查询处理、在所有 子空间上的Skyline查询处理以及在数据流上的Skyline查询处理等。

虽然传统定义下的Skyline算法已经相对成熟，但依然有很多方 面需要仍需改进。最为突出的一点是在很多应用场景下经由Skyline 查询反馈回来的Skyline点的数目过大，以至于其无法很好地服务于 多目标决策。

为了解决这个问题,林学民等人于2007年首次提出了“代表性 Skyline(Top-k representative Skyline，简称TRS)”概念,即从 Skyline点集中选出k个Skyline点作为“代表性Skyline点”，而选出 的k个节点需要满足以下条件：选出的k个Skyline点所支配 (dominate)的数据集中的点的个数要大于或等于从Skyline点集中 任意选取k个Skyline点所能支配(dominate)的数据集中点的个数。 其中支配(dominate)的含义如下：给定两个d维坐标的点 x＝(x1,x2,…,xd)和y＝(y1,y2,…,yd),如果对于任意的整数i∈ [1,d]，都有xi≤yi，且存在一个i使得xi<yi，则称点x支配点y。类 似地，陶宇飞等人于2009年提出了“基于距离的代表性Skyline (Distance-based Representative Skyline)”的策略，其定义为： 选出的k个点满足Er(κ,S)代表Skyline点集 中所有非代表性skyline点到离其最近的代表性skyline点所能取得 的最大距离值,然后通过动态规划算法求解得到最终的代表性 Skyline点集，称为DRS算法。其中，κ表示“代表性Skyline”的点 集，S指的是数据集中所有节点集合。本专利将主要采用基于距离的 代表性Skyline的定义。

以上算法中，TRS算法有一个明显的缺点，即选出的“代表性 Skyline点”有一定的偏向性，往往偏向于数据集中点相对密集的地 方，同时它的时间复杂度(O(km²+nlog(m)))太高，其中的n表示数据 集的点的个数，m表示Skyline点的个数。因此，在数据规模很大以及 数据分布集中的场景下TRS的有效性将很难保证。基于DRS算法虽然很 好地解决了TRS不能很好地代表整个Skyline点集的缺陷，但时间复杂 度仍然过高(O(|D|.log(m)+m²(k-2)))，其中|D|代表数据集的大小，这 严重制约了算法的适用范围。

发明内容

本发明提供了一种新的基于距离的求解二维空间中代表性 Skyline节点集的算法，算法时间复杂度为O(k²log³m)，远低于DRS算 法的时间复杂度。

本发明通过以下技术手段实现：

一种基于距离的求解二维空间中代表性节点集的算法，包含以下 步骤：

S1，输入数据集，用BNL算法计算数据集中的Skyline点集Q；对点集Q 排序后求出初始点到其它任意Skyline点的曼哈顿距离值并存储；

S2，求出Skyline点集中的k个代表性Skyline点；首先引入

Testing(B)算法判断是否存在k个半径不大于B的圆环所能覆盖的区域 能够包含整个Skyline点集，如果是，返回正确,否则返回错误；然后 设定S共k个下标，其中S₀＝1令1≤i≤k-1；满足 Testing(radius(S_i-1,S_i))为错误且Testing(radius(S_i-1,S_i+1))为正确，则 令B_opt＝Er(κ,S)，其中，κ代表“代表性 Skyline点”集合，是输入值，S代表数据集中所有节点集合，||p,p′||表 示点p与p′之间的欧式距离；

S3,将B_opt带入Testing(B_opt)中，返回k个代表性Skyline点。

其中，在所述的数据集中求区域[i,j]覆盖的多个Skyline点 {p_i,....p_j}的中心点center(i,j)以及覆盖圆以中心点为圆心的最小半径 radius(i,j)，1≤i≤j≤m，其中m为Skyline点集的元素个数；定义 centre(i,j)＝p_u，满足$\mathrm{radius}(i,j)=\underset{u=i}{\overset{j}{\min }}\left\{\max \right\{\left|\right|p_i,p_u\left|\right|,\left|\right|p_u,p_j\left|\right|\left\}\right\}.$

在二维空间中，NDRS算法所求解的代表性Skyline能够准确地代 表Skyline点集的整体情况，通过反馈k个“代表性Skyline”点给决 策者，再对决策者选定的“代表性Skyline点”对应区间展开，对区 间内的Skyline点进行二次决策，完美解决了Skyline点集过大不利于 决策者决策的难题，使Skyline技术更好地服务于多目标决策。在 Skyline点集已知的情况下，相比于DRS算法，本发明的算法时间复杂 度为O(k²log³m)，远低于DRS算法的时间复杂度。

附图说明

图1为本发明算法过程示意图；

图2为点集示意图；

图3一个区域[i,j]所覆盖的多个Skyline点示意图

图4为区间[3,6]及区间[5,6]的覆盖圆环

图5为区间[1,5]的radius(i,j)随着center(i,j)的不同取值的改变情 况。

具体实施方式

以下将结合附图对本发明的实施过程进行详细说明。

一种基于距离的求解二维空间中代表性节点集的算法，采用二分 参数搜索技术，引入一个Testing函数，用于测试距离的可行性，并 重新设计了一个新的计算半径的算法，使得程序执行时间大幅度减 少。如图1所示，具体过程如下：

一、预处理

(1)计算数据集中对应的Skyline点集

在给定的数据集中，采用BNL算法，求出能够覆盖整个数据集的 Skyline点集。

该算法的大体框架如下

输入：数据集G＝(x,y)

输出：Skyline点集

1.1对数据集中的所有点按照x值从大到小进行排序；

1.2将排序好的数据集的第一个节点加入到Skyline点集 中；

2按顺序对比当前点的y值和Skyline点集中y值最大的 Skyline点对比，如果大于那个最大的Skyline点，则将当前点加 入到Skyline点集中去，否则不加。循环此项操作，直至所有点都 已搜索完毕。

3对Skyline点集排序并输出。

该预处理算法可以在O(nlogn)的时间复杂度内完成。

(2)求被一个区域[i,j]所覆盖的多个Skyline点{p_i,....p_j}的中心 点center(i,j)以及覆盖圆以中心点为圆心的最小半径radius(i,j)，其中m 为Skyline点集的元素个数，1≤i≤j≤m。定义centre(i,j)＝p_u，满足 $\mathrm{radius}(i,j)=\underset{u=i}{\overset{j}{\min }}\left\{\max \right\{\left|\right|p_i,p_u\left|\right|,\left|\right|p_u,p_j\left|\right|\left\}\right\}.$

算法大体框架如下：

输入：下标i,j；

输出：center(i,j)、radius(i,j)；

1.1如果i＝j,center(i,j)＝i,radius(i,j)＝0；

1.2否则,令left＝i,right＝j；当left<right.

1.2.1令

mid1＝(left+right)/2,FR＝||p_j,p_mid1||,FL＝||p_mid1,p_i||；

1.2.2如果FR<FL，right＝mid1；

1.2.3否则

1.2.3.1如果FR>FL,left+＝mid1

1.2.3.2否则center(i,j)＝mid1,radius(i,j)＝||p_j,p_mid1||；

1.3Mid1＝right；

1.4如果

1.4.1mid1＝mid1-1；

1.4.2否则mid1不变

1.5返回center(i,j)＝mid1,radius(i,j)＝||p_j,p_mid1||；

求被区域[i,j]所覆盖的多个Skyline点{p_i,....p_j}的中心点 )以radius(i,j)可以在O(log(m))的时间复杂度内完成。

二、由已知Skyline点集求解k个代表性Skyline点。

(1)引入Testing(B)算法判断是否存在k个当1≤i≤j≤m， radius(i,j)<＝B时由半径为radius(i,j)的圆环所能覆盖的区域能够包含整 个Skyline点集，如果是，返回正确,否则返回错误。

算法大体框架如下：

输入：B,排好序的Skyline点集(包含m个元素)、下标S_i其 中1≤i≤m。

输出：正确or错误

1.1其中1≤i≤m初始化p＝0；

1.2当p<k-1

1.2.1二分搜索BiNSRCH(S_i+1,j,S_i+1)直至 max(radius(S_i+1,S_i+1))<＝B。同时在此过程中存储 centre(S_i+1,S_i+1)做为B下的代表性Skyline，令p+＝1；

1.3如果radius(S_k-1+1,S_k)<＝B，返回正确，否则返回 错误.

(2)为了求解满足的Er(κ，S)，先设定 共k个下标，其中S₀＝1令1≤i≤k-1满足 Testing(radius(S_i-1,S_i))为错误且Testing(radius(S_i-1,S_i+1))为正确，则 然后以此返回对应的k个代表性Skyline 点。

该算法应用了Distance-Testing策略，即RSP算法，算法大体框 架如下：

输入：排好序的Skyline点集(包含m个元素)、center(i,j)， radius(i,j)当1≤i≤j≤m

输出：k个代表性Skyline点，B_opt。

1.1设{S₀,S₁,....S_k-1}，其中其中S₀＝1

1.2for b<-1to P-1执行

1.2.1ilow<-S_b-1；ihigh<--m；

1.2.2当ilow<ihigh执行

imid<-(ilow+ihigh)/2；

1.2.3B<-radius(S_i-1,S_i+1)

1.2.4如果Testing(B)then

Ihigh<-imid；

1.2.5否则

ilow<-imid+1；

1.2.6S_k-1<-ihigh；

1.2.7B_k-1<-radius(S_k-1+1,S_k-2)

B_P<-radius(S_p-1,m)

1.3Return$B_{\mathrm{opt}}=\underset{i=1}{\overset{k-1}{\min }}\left\{\mathrm{radius}(S_{i-1},S_i+1)\right\}.$k个代表性 Skyline点；

NDRS算法主要应用了Distance-Testing技术，它主要是在 Skyline点集已知的情况下求解代表性Skyline点(简称“RSP”)的 方案，并称之为DisBase算法。

DisBase算法主要思路是先从排好序的m个Skyline点对应下标 中选共k个下标，这些下标满足如下条件：当 1≤i≤k-1时有radius(1,S₁)＜B_opt＜raidus(1,S₁+1),且 radius(S_i+1,S_i+1)＜B_opt＜raidus(S_i+1,S_i+1+1)

而最终的这部分的时间复杂度为 O(klogm.logm),然后由Testing(B_opt)返回最终的k个代表性Skyline点 (即RSP)，这部分的时间复杂度为O(k.logm)，故算法的时间复杂度为 O(k²log³m)。

以下是NDRS算法的具体思路及其正确性证明。

定理1:当B≥B_opt时，Testing(B)为正确.

证明:假设当B≥B_opt时，Testing(B)为错误,说明不存在任何由k 个半径不大于B的圆能够完全覆盖整个Skyline点集，而B≥B_opt，那么 也不可能存在任何由k个半径不大于B_opt的圆能够完全覆盖整个 Skyline点集，即Testing(B_opt)为错误,与事实不符，由此可证定理1 成立。

定理2:令B_opt为k个半径不大于B_opt的圆能完全覆盖Skyline点集 的最小取值，则$B_{\mathrm{opt}}=\underset{i=1}{\overset{k-1}{\min }}\left\{\mathrm{radius}(S_{i-1}+1,S_i+1)\right\}.$

证明:由{S₀,S₁,....S_k-1}本身定义可知，对于任意1≤i≤k-1，都满足 Testing(radius(S_i-1+1,S_i+1))为正确.那我们只需证明B_opt存在于 ,之S中1即)可，即只需证明对第1个圆C₁所覆盖的第一个 Skyline点的下标为1，除1以外的第i个圆C_i所覆盖的第一个Skyline 点的下标为S_i-1+1。因为radius(1,S₁)＜B_opt,所以对于{2，...S₁}不可能为 B_opt所对应圆覆盖的第一个Skyline点的下标，同理可证，对任意 {S_i+2,S_i+1}不可能为B_opt所对应圆覆盖的第一个Skyline点的下标，由 此，定理2得证。

在现有技术中，求解Skyline的技术已经相对完善。在预处理生 成Skyline点集的基础上，本发明通过NDRS算法进一步搜索出k个代表 性Skyline点，大大降低了决策者的决策范围。

现在以图2中的点集为例，进一步说明算法的实施过程。

目的：求出k＝3个代表性Skyline点。

一、预处理

1.1计算数据集中对应的Skyline点集

在给定的数据集{p₁,p₂,...,p₁₂}中，采用BNL算法，求出能够覆盖 整个数据集的Skyline点集{p₁,p₂...,p₆}。

1.2求被一个如图3所示区域[i,j]所覆盖的多个Skyline点 {p_i,....p_j}的中心点center(i,j)以及radius(i,j)可用如下方法，这里是在线 算法，非离线算法。

求被区域[i,j]所覆盖的多个Skyline点{p_i,....p_j}的中心点 以radius(i,j)可以在O(log(m))的时间复杂度内完成。

图4.为区间[3,6]及区间[5,6]的覆盖圆环，图5为区间[1,5]的 radius(i,j)随着center(i,j)的不同取值的改变情况。易知可以通过比较 FR、FL的大小经由二分法很快可以求出radius(1,5)＝10，center(1,5)＝3。 二、由已知Skyline点集{p₁,p₂...,p₆}求解3个代表性Skyline点。

如图5所示，经过预处理阶段已经求出了Skyline点集{p₁,p₂...,p₆} 并可在O(1)的时间内求出任意两个Skyline点之间的距离。(这里 ||p₁,p₂||＝2，||p₂,p₃||＝4，||p₃,p₄||＝6，||p₄,p₅||＝4，||p₅,p₆||＝2)，设有下标 {S₀,...S_i},0＜i＜k，其中S₀＝1，这里，k＝3.则需要求出S₁,S₂的值，S₁,S₂满足Testing(radius(S_i-1,S_i))为错误且Testing(radius(S_i-1,S_i+1))为正确.

具体求解步骤如下：

1)用二分法求S₁,S₂，设ilow＝1,ihigh＝6； imid＝(ilow+ihigh)/2＝3；

2)判断Testing(radius(1,3))，调用1.2中方法求得 radi(u1s,3)，＝4令B＝4，Testing(B)可由二分法求解：

2.1)参考Testing算法伪代码，步骤如下：

1.设ilow2＝1,ihigh2＝6； imid2＝(ilow2+ihigh2)/2＝3；

2.radius(1,3)＝B，则ilow2＝4,ihigh2＝6；imid2＝5；

3.radius(4,5)＞B，此时ilow2＝4,ihigh2＝imid2-1＝4；

4.radius(5,6)＝2＜B，返回正确.

3)ilow＝1,ihigh＝imid＝4；

3.1)imid＝(ilow+ihigh)/2＝2；

Testing(imid)＝Testing(2),同2.1)方法可得Testing(2)为错 误,由此可得S₁＝2.

1)ilow＝3,ihigh＝6,同理可得S₂＝3.

2)由Testing(B_opt)可返回对应center(i,j)作 为代表性skyline点，求得代表性Skyline点为{p₂,p₄,p₅}。