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

(19)中华人民共和国国家知识产权局

(12)发明专利说明书

(10)申请公布号CN104573036A

(43)申请公布日2015.04.29

(21)申请号CN201510021696.0

(22)申请日2015.01.16

(71)申请人深圳大学

地址518000广东省深圳市南山区南海大道3688号

(72)发明人李荣华蔡涛涛毛睿邱宇轩秦璐

(74)专利代理机构深圳市兴科达知识产权代理有限公司

代理人王翀

(51)Int.CI

G06F17/30

权利要求说明书说明书幅图

(54)发明名称

一种基于距离的求解二维空间中代

表性节点集的算法

(57)摘要

本发明提供了一种新的基于距离的

求解二维空间中代表性Skyl？ine节点集的

算法，输入数据集，用BNL算法计算数据

集中的Skyl？ine点集Q；对点集Q排序后

求出初始点到其它任意Skyl？ine点的曼哈

顿距离值并存储；求出Skyline点集中的k

个代表性Skyline点；返回k个代表性

Skyl？ine点。算法时间复杂度为O(k

法律状态

法律状态公告日法律状态信息法律状态

权利要求说明书

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

步骤：

S1，输入数据集，用BNL算法计算数据集中的Skyline点集Q；对点集Q

排序后求出初始点到其它任意Skyline点的曼哈顿距离值并存储；

S2，求出Skyline点集中的k个代表性Skyline点；首先引入Testing(B)算

法判断是否存在k个当1≤i≤j≤m，radius(i,j)＜＝B时由半径为radius(i,j)

的圆环所能覆盖的区域能够包含整个Skyline点集，如果是，返回正

确,否则返回错误；然后设定

{Ssub0/sub,Ssub1/sub,Ssubk-1/sub}，共k个下标，其中

Ssub0/sub＝1令1≤i≤k-1；满足Testing(radius(Ssubi-

1/sub,Ssubi/sub))为错误且Testing(radius(Ssubi-1/sub,Ssubi/sub+1))

为正确，则

mathsmathmrowmiEr/mimrowmo(/momikappa;/mimo,

/momiS/mimo)/mo/mrowmo=/momunderovermimin/mimr

owmii/mimo=/momn1/mn/mrowmrowmik/mimo-

/momn1/mn/mrow/munderovermo{/momiradius/mimrowm

o(/momsubmiS/mimrowmii/mimo-

/momn1/mn/mrow/msubmo,/momsubmiS/mimii/mi/m

submo+/momn1/mnmo)/mo/mrowmo}/momo,/mo/mro

w/math/maths令Bsubopt/sub＝Er(κ,S)，其中，κ代表“代

表性Skyline点”集合，是输入值，S代表数据集中所有节点集合，

||p,p′||表示点p与p′之间的欧式距离；

S3，将Bsubopt/sub带入Testing(Bsubopt/sub)中，返回k个代表性

Skyline点。

2.一种基于距离的求解二维空间中代表性节点集的算法，其特征在

于:在所述的数据集中求区域[i,j]覆盖的多个Skyline点

{psubi/sub,psubj/sub