• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 13
    • 下载费用:30 金币  

    重庆时时彩开视频奖: 一种动态不完整数据SKYLINE查询算法.pdf

    关 键 词:
    一种 动态 完整 数据 SKYLINE 查询 算法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201610776990.7

    申请日:

    2016.08.30

    公开号:

    CN106354826A

    公开日:

    2017.01.25

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06F 17/30申请日:20160830|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 江苏名通信息科技有限公司
    发明人: 秦谦; 王宏志
    地址: 212000 江苏省镇江市京口区学府路118号京口高新技术创业中心6楼
    优先权:
    专利代理机构: 南京纵横知识产权代理有限公司 32224 代理人: 董建林
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201610776990.7

    授权公告号:

    |||

    法律状态公告日:

    2017.03.01|||2017.01.25

    法律状态类型:

    实质审查的生效|||公开

    摘要

    本发明公开了一种动态不完整数据skyline查询算法,其特征在于:所述算法输入的动态不完整数据集S通过桶插入算法、候选插入算法、全局更新算法以及滑动窗口和桶内容更新算法后,确定非候选点,减少候选点个数,在候选点中进行查询,得到动态不完整数据集S上的查询结果。本发明的优点在于:提升计算效率,快速有效获得不完整数据集上skyline查询结果。

    权利要求书

    1.一种动态不完整数据skyline查询算法,其特征在于:所述算法输入的动态不完整数
    据集S通过桶skyline插入算法、候选skyline插入算法、全局skyline更新算法以及滑动窗
    口和桶内容更新算法后,确定非候选skyline点,减少候选skyline点个数,在候选skyline
    点中进行skyline查询,得到动态不完整数据集S上的skyline查询结果;
    所述桶skyline插入算法用于判断输入的动态不完整数据集S中的全体skyline点是否
    是实点、虚点、阴影点,并进行划分得到候选skyline集合;
    所述候选skyline插入算法判断用于对候选skyline集合中的点的支配关系进行判断,
    删除被支配的点,得到候选skyline点;
    所述全局skyline更新算法用于更新全体skyline点,通过将候选skyline点与整体
    skyline点比较,排除非全体skyline点的候选skyline点,将不被支配的候选skyline点合
    并到全体skyline点集合中;
    所述滑动窗口和桶内容更新算法用于更新全体skyline集合。
    2.根据权利要求1所述的一种动态不完整数据skyline查询算法,其特征在于:所述桶
    skyline插入算法的输入是待插入的数据点p和点p待插入到的桶Bp,输出是一个布尔变量
    结果,isReal标记设置为布尔值true,isDominated标记设置false,其计算步骤包括:
    步骤(A1),判断点p是否被阴影skyline中的任何一个点所支配,如果存在一个点使得
    点p被支配则直接丢弃;
    步骤(A2),判断点p是否被桶Bp中的实点和阴影点支配,如果点p既不被桶Bp内的实点所
    支配,又不被桶Bp内的阴影点支配,将桶Bp中被点p支配的所有实点和阴影点从桶Bp中删除,
    然后将点p插入到桶Bp的实点集合中;
    步骤(A3),判断点p是否只被桶Bp内虚点集合中的点支配,如果是则桶Bp内阴影skyline
    点中被点p支配的点删除,并将桶Bp的阴影点集合更新标记为true;
    步骤(A4),将点p插入到桶Bp的阴影skyline点集合中。
    3.根据权利要求2所述的一种动态不完整数据skyline查询算法,其特征在于:所述候
    选skyline插入算法的计算步骤包括:
    步骤(B1),设置一个被支配标记isDominated并设置为假,用布尔变量false形式,表示
    点p未被候选skyline集合中的任意一个点所支配;
    步骤(B2),逐个遍历候选skyline集合中的的点cp并计算点p与cp的公共非缺失维度k,
    判断如果k等于0,以跳过对该点p的处理;
    步骤(B3),判断如果点p支配点cp,则将cp从候选skyline点中删除,并将点p作为桶Bcp
    的虚点插入到该桶中,同时将桶Bcp中被点p支配的实点删除;
    步骤(B4),判断如果点cp支配点p,则将被支配标记设置为true,将点cp作为桶Bp的虚点
    插入到桶Bcp内,然后删除桶Bp内被点cp支配的那些点;
    步骤(B5),判断点p是否被标记为false,如果是false,则将点p插入到候选skyline点
    集合中,成为候选skyline。
    4.根据权利要求3所述的一种动态不完整数据skyline查询算法,其特征在于:所述全
    局skyline更新算法的计算步骤包括:
    步骤(C1),遍历全局skyline点gp和候选skyline点cp;
    步骤(C2),判断gp和cp是否存在公共非空缺维度,否则跳过内部循环,选择下一个可比
    较数据点进行比较;
    步骤(C3),判断全局skyline点gp和候选skyline点cp是否被支配,将被支配的点支配
    标记设置为true;
    步骤(C4),分别将全局skyline点gp和候选skyline点cp中被支配标记为true的点删
    除;
    步骤(C5),对于阴影skyline标记为true的桶进行处理,对标记为true的阴影skyline
    点集合中的点与全局skyline点gp和候选skyline点cp的比较,在比较结束后将候选
    skyline点和全局skyline点中被支配的点删除,将候选skyline点集合更新标记为false;
    步骤(C6),将候选skyline集合与全局skyline集合合并中,并更新全局skyline集合。
    5.根据权利要求4所述的一种动态不完整数据skyline查询算法,其特征在于:所述滑
    动窗口和桶内容更新算法的输入为最新到达的数据点Vw+i、最早到达的数据点Vw和窗口元
    素集合DW,其计算步骤为:
    步骤(D1),计算数据点Vw所在的桶Bvw中被点Vw所支配的点的集合Tvw;
    步骤(D2),判断Tvw是否为空,为将该点删除,不为空,将最新到达的数据点Vw+i加入到Tvw
    集合中;
    步骤(D3),进行桶skyline插入处理,判断当前点是否是桶内skyline点,是则进行候选
    skyline插入处理;
    步骤(D4),新全局skyline集合。
    6.基于权利要求1-5所述的一种动态不完整数据skyline查询算法,其特征在于:还包
    括算法框架,所述算法框架的输入是动态数据集S和滑动窗口W,其具体算法步骤为;
    步骤(E1),初始化全局skyline点集合、候选skyline点集合,设置当前窗口元素集合DW
    为空;
    步骤(E2),判断当前窗口集合中元素个数是否小于窗口大小W,小于则读取下一个新的
    元素;
    步骤(E3),判断新到达的数据点对应的桶是否存在,否则创建一个以新到达数据点位
    图模式为桶的位图模式的新桶;
    步骤(E4),将新到达的数据点插入到对应的桶中;
    步骤(E5),判断点是否是该桶内的局部skyline点,将点p插入到候选skyline集合中;
    步骤(E6),判断当前窗口集合中元素个数,当达到窗口限制W时停止读取新元素,更新
    全局skyline;用Vw+i表示最新到达的数据点,用Vw表示最早到达的数据点;
    步骤(E7),更新当前窗口元素和对应的桶中元素,返回全局skyline集合。

    说明书

    一种动态不完整数据skyline查询算法

    技术领域

    本发明属于移动设备查询系统技术领域,特别涉及一种动态不完整数据skyline
    查询算法。

    背景技术

    随着基于面向位置服务LBS技术的发展,人们越来越多地利用移动设备享受方便
    的服务,skyline查询是LBS上的一种重要查询,例如手机用户会对自己周围距离最近,价格
    最合理,食物最美,服务最周到的餐厅感兴趣,skyline查询能够根据用户当前的位置进行
    合理的查询和推荐。

    重庆时时彩单双窍门 www.4mum.com.cn 同时满足如下特征的数据集我们称之为动态不完整数据集:数据集是不完整的,
    即存在属性值空缺问题,我们用符号“-”表示空缺值;数据集是动态变化的,即我们在查询
    处理的开始无法获得全部数据项,随着时间增加,可能有新的数据项到达,也可能有到达时
    间早的数据项失效,因此数据规模是无界的;数据集是具有时序性的,即动态数据集中的数
    据点是按时间次序到达的,本发明中我们给每个数据项都带有一个时间戳标记,表示该点
    的到达时间。由于本发明采用基于时间戳计数的滑动窗口模型,窗口大小决定据项的有效
    性,因此不用知道数据点的失效时间。给定属性空间为D的动态不完整数据集S,在任意时刻
    T,对S中当前有效数据点进行skyline查询,我们称该问题为动态不完整数据集上的
    skyline查询问题。查询得到的点成为动态不完整数据集上的skyline点。对于不完整数据
    流上的skyline查询问题,目前研究成果还很少,仅有的方法解决的是k-支配问 题,直接对
    不完整数据进行k-支配关系计算,这样得到的skyline查询结果和k值有很大关系,并不能
    充分挖掘出符合用户偏好的skyline数据点。

    发明内容

    发明目的:本发明提供一种动态不完整数据skyline查询算法,充分考虑动态数据
    集的变化特征,在分析传统滑动窗口模型的基础上提出了基于滑动窗口的分桶策略,使用
    桶对数据进行划分,通过对桶内数据点进行实点、虚点、阴影点的划分,从而提早确定非候
    选skyline点,因而减少候选skyline点个数,从而提升计算效率,快速有效获得不完整数据
    集上skyline查询结果,以解决现有技术中的问题。

    技术方案:为实现上述目的,本发明采用的技术方案为:

    一种动态不完整数据skyline查询算法,所述算法输入的动态不完整数据集S通过
    桶skyline插入算法、候选skyline插入算法、全局skyline更新算法以及滑动窗口和桶内容
    更新算法后,确定非候选skyline点,减少候选skyline点个数,在候选skyline点中进行
    skyline查询,得到动态不完整数据集S上的skyline查询结果;

    所述桶skyline插入算法用于判断输入的动态不完整数据集S中的全体skyline点
    是否是实点、虚点、阴影点,并进行划分得到候选skyline集合;

    所述候选skyline插入算法判断用于对候选skyline集合中的点的支配关系进行
    判断,删除被支配的点,得到候选skyline点;

    所述全局skyline更新算法用于更新全体skyline点,通过将候选skyline点与整
    体skyline点比较,排除非全体skyline点的候选skyline点,将不被 支配的候选skyline点
    合并到全体skyline点集合中;

    所述滑动窗口和桶内容更新算法用于更新全体skyline集合。

    进一步,所述桶skyline插入算法的输入是待插入的数据点p和点p待插入到的桶
    Bp,输出是一个布尔变量结果,isReal标记设置为布尔值true,isDominated标记设置
    false,其计算步骤包括:

    步骤(A1),判断点p是否被阴影skyline中的任何一个点所支配,如果存在一个点
    使得点p被支配则直接丢弃;

    步骤(A2),判断点p是否被桶Bp中的实点和阴影点支配,如果点p既不被桶Bp内的实
    点所支配,又不被桶Bp内的阴影点支配,将桶Bp中被点p支配的所有实点和阴影点从桶Bp中
    删除,然后将点p插入到桶Bp的实点集合中;

    步骤(A3),判断点p是否只被桶Bp内虚点集合中的点支配,如果是则桶Bp内阴影
    skyline点中被点p支配的点删除,并将桶Bp的阴影点集合更新标记为true;

    步骤(A4),将点p插入到桶Bp的阴影skyline点集合中。

    进一步。所述候选skyline插入算法的计算步骤包括:

    步骤(B1),设置一个被支配标记isDominated并设置为假,用布尔变量false形式,
    表示点p未被候选skyline集合中的任意一个点所支配;

    步骤(B2),逐个遍历候选skyline集合中的点cp并计算点p与cp的公共非缺失维度
    k,判断如果k等于0,以跳过对该点p的处理;

    步骤(B3),判断如果点p支配点cp,则将cp从候选skyline点中删除, 并将点p作为
    桶Bcp的虚点插入到该桶中,同时将桶Bcp中被点p支配的实点删除;

    步骤(B4),判断如果点cp支配点p,则将被支配标记设置为true,将点cp作为桶Bp
    的虚点插入到桶Bcp内,然后删除桶Bp内被点cp支配的那些点;

    步骤(B5),判断点p是否被标记为false,如果标记为false,则将点p插入到候选
    skyline点集合中,成为候选skyline点。

    进一步,所述全局skyline更新算法的计算步骤包括:

    步骤(C1),遍历全局skyline点gp和候选skyline点cp;

    步骤(C2),判断gp和cp是否存在公共非空缺维度,否则跳过内部循环,选择下一个
    可比较数据点进行比较;

    步骤(C3),判断全局skyline点gp和候选skyline点cp是否被支配,将被支配的点
    支配标记设置为true;

    步骤(C4),分别将全局skyline点gp和候选skyline点cp中被支配标记为true的点
    删除;

    步骤(C5),对于阴影skyline标记为true的桶进行处理,对标记为true的阴影
    skyline点集合中的点与全局skyline点gp和候选skyline点cp的比较,在比较结束后将候
    选skyline点和全局skyline点中被支配的点删除,将候选skyline点集合更新标记为
    false;

    步骤(C6),将候选skyline集合与全局skyline集合合并中,并更新全局skyline集
    合。

    进一步,所述滑动窗口和桶内容更新算法的输入为最新到达的数据点Vw+i、最早到
    达的数据点Vw和窗口元素集合DW,其计算步骤为:

    步骤(D1),计算数据点Vw所在的桶Bvw中被点Vw所支配的点的集合Tvw;

    步骤(D2),判断Tvw是否为空,为将该点删除,不为空,将最新到达的数据点Vw+i加入
    到Tvw集合中;

    步骤(D3),进行桶skyline插入处理,判断当前点是否是桶内skyline点,是则进行
    候选skyline插入处理;

    步骤(D4),新全局skyline集合。

    进一步,还包括算法框架,所述算法框架的输入是动态数据集S和滑动窗口W,其具
    体算法步骤为;

    步骤(E1),初始化全局skyline点集合、候选skyline点集合,设置当前窗口元素集
    合DW为空;

    步骤(E2),判断当前窗口集合中元素个数是否小于窗口大小W,下于则读取下一个
    新的元素;

    步骤(E3),判断新到达的数据点对应的桶是否存在,否则创建一个以新到达数据
    点位图模式为桶的位图模式的新桶;

    步骤(E4),将新到达的数据点插入到对应的桶中;

    步骤(E5),判断点是否是该桶内的局部skyline点,将点p插入到候选skyline集合
    中;

    步骤(E6),判断当前窗口集合中元素个数,当达到窗口限制W时停 止读取新元素,
    更新全局skyline;用Vw+i表示最新到达的数据点,用Vw表示最早到达的数据点;

    步骤(E7),更新当前窗口元素和对应的桶中元素,返回全局skyline集合。

    有益效果:与现有技术相比,本发明具有以下优点:

    1、数据规模无限制,既可以用于解决无明确大小限制约定的动态数据流数据,也
    适合解决大规模静态数据集;

    2、节省存储空间,能够设定窗口大小,防止过多数据点同时计算导致效率低;有效
    防止数据点个数过少导致结果为空的情况;对每个点在桶中的存储采取指针形式,只有在
    滑动窗口中才保存数据的全部内容,可以有效减少内存消耗;

    3、高效性,通过对桶内数据点进行几部分划分,使得候选skyline个数较少,本质
    上是减少了桶之间的比较次数,不完整数据桶的个数与数据规模成指数次方变化,因此通
    过减少桶之间的比较次数,能够大大提高算法的运行速度;

    4、在减少候选skyline点的同时,减少候选skyline点之间两两比较过程中属性之
    间的比较次数,从而进一步提高整体算法性能。

    具体实施方式

    一种动态不完整数据skyline查询算法,所述算法输入的动态不完整数据集S通过
    桶skyline插入算法、候选skyline插入算法、全局skyline更新算法以及滑动窗口和桶内容
    更新算法后,确定非候选skyline点,减少候选 skyline点个数,在候选skyline点中进行
    skyline查询,得到动态不完整数据集S上的skyline查询结果;

    所述桶skyline插入算法用于判断输入的动态不完整数据集S中的全体skyline点
    是否是实点、虚点、阴影点,并进行划分得到候选skyline集合;

    所述候选skyline插入算法判断用于对候选skyline集合中的点的支配关系进行
    判断,删除被支配的点,得到候选skyline点;

    所述全局skyline更新算法用于更新全体skyline点,通过将候选skyline点与整
    体skyline点比较,排除非全体skyline点的候选skyline点,将不被支配的候选skyline点
    合并到全体skyline点集合中;

    所述滑动窗口和桶内容更新算法用于更新全体skyline集合。

    前述桶skyline插入算法的输入是待插入的数据点p和点p待插入到的桶Bp,输出
    是一个布尔变量结果,isReal标记设置为布尔值true,isDominated标记设置false,其计算
    步骤包括:

    步骤(A1),判断点p是否被阴影skyline中的任何一个点所支配,如果存在一个点
    使得点p被支配则直接丢弃;

    步骤(A2),判断点p是否被桶Bp中的实点和阴影点支配,如果点p既不被桶Bp内的实
    点所支配,又不被桶Bp内的阴影点支配,将桶Bp中被点p支配的所有实点和阴影点从桶Bp中
    删除,然后将点p插入到桶Bp的实点集合中;

    步骤(A3),判断点p是否只被桶Bp内虚点集合中的点支配,如果是则桶Bp内阴影
    skyline点中被点p支配的点删除,并将桶Bp的阴影点集合 更新标记为true;

    步骤(A4),将点p插入到桶Bp的阴影skyline点集合中。

    前述候选skyline插入算法的计算步骤包括:

    步骤(B1),设置一个被支配标记isDominated并设置为假,用布尔变量false形式,
    表示点p未被候选skyline集合中的任意一个点所支配;

    步骤(B2),逐个遍历候选skyline集合中的的点cp并计算点p与cp的公共非缺失维
    度k,判断如果k等于0,以跳过对该点p的处理;

    步骤(B3),判断如果点p支配点cp,则将cp从候选skyline点中删除,并将点p作为
    桶Bcp的虚点插入到该桶中,同时将桶Bcp中被点p支配的实点删除;

    步骤(B4),判断如果点cp支配点p,则将被支配标记设置为true,将点cp作为桶Bp
    的虚点插入到桶Bcp内,然后删除桶Bp内被点cp支配的那些点;

    步骤(B5),判断点p是否被标记为false,如果为false,则将点p插入到候选
    skyline点集合中,成为候选skyline点。

    前述全局skyline更新算法的计算步骤包括:

    步骤(C1),遍历全局skyline点gp和候选skyline点cp;

    步骤(C2),判断gp和cp是否存在公共非空缺维度,否则跳过内部循环,选择下一个
    可比较数据点进行比较;

    步骤(C3),判断全局skyline点gp和候选skyline点cp是否被支配,将被支配的点
    支配标记设置为true;

    步骤(C4),分别将全局skyline点gp和候选skyline点cp中被支配标记为true的点
    删除;

    步骤(C5),对于阴影skyline标记为true的桶进行处理,对标记为true的阴影
    skyline点集合中的点与全局skyline点gp和候选skyline点cp的比较,在比较结束后将候
    选skyline点和全局skyline点中被支配的点删除,将候选skyline点集合更新标记为
    false;

    步骤(C6),将候选skyline集合与全局skyline集合合并中,并更新全局skyline集
    合。

    前述滑动窗口和桶内容更新算法的输入为最新到达的数据点Vw+i、最早到达的数
    据点Vw和窗口元素集合DW,其计算步骤为:

    步骤(D1),计算数据点Vw所在的桶Bvw中被点Vw所支配的点的集合Tvw;

    步骤(D2),判断Tvw是否为空,为将该点删除,不为空,将最新到达的数据点Vw+i加入
    到Tvw集合中;

    步骤(D3),进行桶skyline插入处理,判断当前点是否是桶内skyline点,是则进行
    候选skyline插入处理;

    步骤(D4),新全局skyline集合。

    前述,还包括算法框架,所述算法框架的输入是动态数据集S和滑动窗口W,其具体
    算法步骤为;

    步骤(E1),初始化全局skyline点集合、候选skyline点集合,设置当前窗口元素集
    合DW为空;

    步骤(E2),判断当前窗口集合中元素个数是否小于窗口大小W,下于则读取下一个
    新的元素;

    步骤(E3),判断新到达的数据点对应的桶是否存在,否则创建一个以新到达数据
    点位图模式为桶的位图模式的新桶;

    步骤(E4),将新到达的数据点插入到对应的桶中;

    步骤(E5),判断点是否是该桶内的局部skyline点,将点p插入到候选skyline集合
    中;

    步骤(E6),判断当前窗口集合中元素个数,当达到窗口限制W时停止读取新元素,
    更新全局skyline;用Vw+i表示最新到达的数据点,用Vw表示最早到达的数据点;

    步骤(E7),更新当前窗口元素和对应的桶中元素,返回全局skyline集合。

    下面结合实施例对本发明作更进一步的说明。

    我们的算法是使用桶对数据进行划分,通过对桶内数据点进行实点、虚点、阴影点
    的划分,从而提早确定非候选skyline点,因而减少候选skyline点个数,从而提升计算效
    率。

    首先,在该模型中我们给每个数据点附加一个时间标签,表示该数据点的到达时
    间。这里我们采取基于数据点到达的时间先后顺序进行计数的方法,通过限制滑动窗口大
    小,计算最近N个数据点中的skyline点。这种方法的特点是:

    (1)数据规模无限制。既可以用于解决无明确大小限制约定的动态数据 流数据,
    也适合解决大规模静态数据集。

    (2)节省存储空间。该算法能够认为设定窗口大小,防止过多数据点同时计算导致
    效率低,同时有效防止数据点个数过少导致结果为空的情况。同时我们对每个点在桶中的
    存储采取指针形式,只有在滑动窗口中才保存数据的全部内容,这样可以有效减少内存消
    耗。

    (3)高效性。通过对桶内数据点进行几部分划分,使得候选skyline个数较少,本质
    上是减少了桶之间的比较次数,不完整数据桶的个数与数据规模成指数次方变化,因此通
    过减少桶之间的比较次数,能够大大提高算法的运行速度。同时我们能够采在减少候选
    skyline点的同时,减少候选skyline点之间两两比较过程中属性之间的比较次数,从而进
    一步提高整体算法性能。

    算法执行过程:


    算法框架的伪代码如算法1所示,该算法的输入是动态数据集S和滑 动窗口W,输
    出结果是随着时间变化和输入数据点的动态变化而变化的。算法第一次运行首先初始化全
    局skyline点集合global_skyline、候选skyline点集合candidate_skyline和当前窗口元
    素集合DW为空(第1行)。程序开始运行时,如果当前窗口集合中元素个数小于窗口大小W,则
    读取下一个新的元素。如果新到达的数据点对应的桶不存在,则创建一个以新到达数据点
    位图模式为桶的位图模式的新桶(第5-6行)。然后将新到达的数据点插入到对应的桶中(第
    7行),如果该点是该桶内的局部skyline点,则将isReal标记设置为布尔值true,并将点p插
    入到候选skyline集合中(第8-9行)。当前窗口集合中元素个数达到窗口限制W时停止读取
    新元素,更新全局skyline(第10行)。如果当前窗口中元素已经达到最大窗口限制,则我们
    用Vw+i表示最新到达的数据点,用Vw表示最早到达的数据点。然后更新当前窗口元素和对应
    的桶中元素(第14行)。并返回全局skyline集合。

    上述框架包含四个核心算法:分别是桶skyline插入算法、候选skyline插入算法、
    全局skyline更新算法和滑动窗口以及滑动窗口和桶内容更新算法。以下对每个算法具体
    实现展开叙述。



    桶skyline插入算法伪代码如算法2所示,该算法输入是待插入的数据点p和点p待
    插入到的桶Bp,输出是一个布尔变量结果,它表示点p能否成为该桶内的skyline点。对于每
    一个新到达的数据点p,我们将其插入点p位图模式对应的桶Bp中,则点p要么被插入到桶Bp
    的实点集合中,要么被插入到桶Bp的阴影点集合中,或者直接被删除。局部skyline点被分
    割为实点和阴影点,实点是指不被桶内虚点支配的局部skyline点,阴影点是被桶内虚点支
    配的局部skyline点,即实点和阴影点构成了桶内局部skyline点。因此我们首先判断点p是
    否被阴影skyline中的任何一个点所支配,如果存在一个点使得点p被支配则直接丢弃。否
    则判断点p是否被桶Bp中的实点和阴影点支配,如果点p既不被桶Bp内的实点所支配,又不被
    桶Bp内的阴影点支配,那么我们将桶Bp中被点p支配的所有实点和阴影点从桶中删除,然后
    将点p插入到桶Bp的实点集合中(第1-3行),然后返回true(第4-6行)。值得指出的是被删除
    的局部skyline点可能在桶Bp的实点集合中,也可能在桶Bp的阴影点集合中,因此统一用
    Bp·localskyline表示。如果点p只被桶Bp内虚点集合中的点支配,那么将桶Bp内阴影
    skyline点中被点p支配的点 删除,并将桶Bp的阴影点集合更新标记为true(第8-9行)。然
    后将点p插入到桶Bp的阴影skyline点集合中(第10行),最后返回false,表明点p被桶内实
    点或虚点点支配(第11行)。


    候选skyline插入算法伪代码如算法3所示,首先设置一个被支配标记
    isDominated并设置为假,我们用布尔变量false形式,表示点p未被候选skyline集合中的
    任意一个点所支配(第1行)。然后逐个遍历候选skyline集合中的点cp并计算点p与cp的公
    共非缺失维度k,如果k等于0,则说明它们之间不存在公共属性,可以跳过对该点的处理(第
    3-5行)。如果点p支配点cp,则将cp从候选skyline点中删除,并将点p作为桶Bcp的虚点插入
    到该桶中,同时将桶Bcp中被点p支配的实点删除(第6-9行)。如果点cp支 配点p,则将被支配
    标记设置为true,将点cp作为桶Bp的虚点插入到桶Bcp内,然后删除桶Bp内被点cp支配的那
    些点(第10-13行)。最后如果被支配标记为false,表明点p不被候选skyline集合中的点支
    配,将点p插入到候选skyline点集合中,成为候选skyline点(第14-15行)。

    全局skyline更新算法伪代码如算法4所示,该算法主要完成更新全体skyline点,
    通过将候选skyline点与整体skyline点比较,排除非全局skyline点的候选skyline点,将
    不被支配的候选skyline点合并到全局skyline点集合中去。首先遍历全局skyline点gp和
    候选skyline点cp(第1-2行),如果它们不存在公共非空缺维度,则跳过内部循环,选择下一
    个可比较数据点进行比较(第3-5行)。如果全局skyline集合中点或候选skyline集合中的
    点被支配,则将被支配的点支配标记设置为true(第6-9行)。然后分别将整体skyline点和
    候选skyline点中被支配标记为true的点从中删除(第10-12行)。接着对于阴影skyline标
    记update为true的桶进行处理,该过程完成标记为true的阴影skyline点集合中的点与全
    局skyline点和候选skyline点的比较,并在比较结束后将被支配的候选skyline点和全局
    skyline点删除,将候选skyline点集合更显标记update设置为false(第13-19行)。最后将
    候选skyline集合与全局skyline集合合并中,并更新全局skyline集合(第20行)。



    其中第一个双重循环(第1-9行)仅仅是为了找出所有全局skyline点集合中被候
    选skyline点支配的点,同时找出所有候选skyline点中被全局skyline点支配的点,之所以
    对被支配点设置标记而没有直接删除,是因为被支配的点可能会支配那些不被其他点支配
    的点,因此并没有直接将被支配的数据点直接删除,而是先设置标记,然后在第二个单重循
    环中将被支配的点删除。

    第二个双重循环(第13-19行)是为了进一步排除候选skyline点和全局skyline点
    中可能存在的非全局的skyline点,对于阴影skyline更新标记为true的桶,它们中可能增
    加了新的元素,这些元素可能来自全局skyline集合,也可能来自候选skyline集合,来自全
    局skyline集合的点是在 global_skyline与candidate_skyline集合中点比较过程中被
    candidate_skyline集合中点支配的点,这些点可能会支配在它从数据集中删除时没有与
    之比较过的候选skyline点,而来自候选skyline集合中的点则是比较过程中被global_
    skyline集合中的点所支配的点,这些点可能会支配在它被删除时还未与之比较过的全局
    skyline集合中的点。因此该比较过程可以确保最终得到的全局skyline集合中没有错误元
    素。


    滑动窗口和桶更新算法伪代码如算法5所示,该算法的输入时最新到达的数据点
    Vw+i、最早到达的数据点Vw和窗口元素集合DW。该算法首先计算数据点Vw所在桶Bvw中被点Vw
    所支配的点的集合Tvw(第1行)。如果Tvw为空则说明数据点Vw无法支配当前窗口中任何一个
    点,则可以将该点直接删除(第2-3行)。如果集合Tvw不为空,则将最新到达的数据点Vw+i加入
    到Tvw集合中,将它们一并处理(第5-6行)。首先进行桶skyline插入处理(第7行),如果当前
    点是桶内skyline点,则进行候选skyline插入处理(第8-9 行),最后更新全局skyline集合
    (第10行)。

    以上所述仅是本发明的优选实施方式,应当指出:对于本技术领域的普通技术人
    员来说,在不脱离本发明原理的前提下,还可以做出若干改进和润饰,这些改进和润饰也应
    视为本发明的?;し段?。

    关于本文
    本文标题:一种动态不完整数据SKYLINE查询算法.pdf
    链接地址://www.4mum.com.cn/p-6027128.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 腾讯分分分彩在线计划软件下载 北京pk10技巧群 免费彩票计划软件苹果版 内蒙古时时奖金对 幸运飞艇走势技巧论坛 北京pk赛车直播开奖视频 黑马计划账号怎么注册 全天时时彩最准计划 炸金花透视300一天 大乐透质合走势图表图 1分快三怎么玩稳赚 900注大底计划软件 秒速时时开挂软件 大小单双技巧 时时彩 大乐透预测一注 北京时时开奖软件