一种更新k-支配轮廓的算法-论文.pdf

《一种更新k-支配轮廓的算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第14卷第22期2014年8月科学技术与工程Vo1．14No．22Aug．2014l671—1815(2014)22—0235—05ScienceTechnologyandEngineering⑥2014Sci．Tech．Engrg．一种更新-支配轮廓的算法董雷刚，崔晓微刘国华。(大庆师范学院计算机科学与信息技术学院，大庆163712；东华大学信息科学与技术学院，上海201620)摘要一支配轮廓查询技术在计算高维空间数据集时，解决了查询结果集合过大的问题，更有利于用户决策；然而，现有的算法都是针对静态k值设计的，不适合值动态变化的情况。为了解决此问题，提出一种思路，即当k值改变以后，以现有的

2、查询结果为基础，通过对可能发生身份变化的数据点进行判断，得到新的k-支配轮廓。在此基础上分别针对值增大和k值减小这两种情况提出了相应的更新算法。通过理论分析和实验，算法能快速完成运算并返回正确查询结果。关键词一支配轮廓查询高维空间动态变化更新中图法分类号TP312；文献标志码A轮廓查询(skylinequery)¨技术适用于多标让其上下场。考虑的属性个数不同，得出的结论也准决策，数据挖掘，市场数据分析等，以帮助用户在就不同，因此，后值的每次变化都会导致原有后．支配海量的数据中获得所需的有效信息，因此越来越受轮廓失效，也就需要重新计算一支配轮廓。目前的到人们的关注。算法都是针对静态k值设计的，

3、当k值发生变化时，对于一个有限的d维数据集D(P，P，⋯一P)，如果直接用这些算法重新求解，会造成大量的冗余轮廓由符合下列条件的每个对象P组成：在D中找计算，浪费时间。为了有效解决此问题，提出一种全不到数据点g，使g在各维上的值都比P优越。比新思路，即当k值改变以后，以现有查询结果为基如，奔驰公司为了提高产品销售量，要选择在多种媒础，找出可能发生身份变化的数据点并对其进行判体上投放广告，因为不同的媒体所需的费用和产生断，从而得到新的查询结果。的效应都不同，所以可能会考虑①广告时段；②广告1相关工作费用；③广告地点；④人群覆盖范围。若要在备选的媒体中选取自己满意媒体投放广告，可以将各因素自从B

4、orzsonyi等人提出轮廓¨(skyline)的操量化后，运用轮廓查询，将比较“优秀”的媒体纳入作之后，越来越多的轮廓查询算法依次出现。人们到轮廓查询结果中，从而很大程度上降低了可选数开始考虑有关skyline查询的各种因素，比如．支配据的数据量，为用户提供了方便，不在轮廓查询结果轮廓查询]，子空问轮廓查询佗]，动态轮廓查中的那些数据不会对用户的最终选择产生影响。询¨，H]，不确定数据上的轮廓查询¨，]，top．k轮廓但是，当数据集的元组数目和维度非常大时，使查询等。所有的上述查询操作都是为了在海用轮廓查询返回的结果集和也会随之增大，当结果量的多维数据集中获取到比较中意的数据信息，但集很大

5、时，同样不利于用户的决策。基于此，一支配有关k值变化时的．支配轮廓更新问题，在上述文轮廓查询技术的提出和应用，在计算过程中可章中并未提到。以去掉更多的点，返回结果集自然变小。但在实际2基本概念应用中，用户可能会不断改变k值来查看返回结果。例如，假设用5个属性来描述一个NBA篮球运动员定义1支配(dominate)¨给定一个空问集S=的得分，即篮板，盖帽，助攻，抢断，防守。当评价一{s，s，⋯，S}和对应的数据点集D={P，P：，P，位中锋的优秀程度时，教练可能会考察他的助攻、篮⋯，P}，点P支配点p，，当且仅当：V∈S，Pis≥板以及盖帽这三个因素，也可能会考察他的助攻、篮，Sk且]“∈SP

6、ist>PiSt。板、盖帽和防守这四个因素，以便在最合适的情况下定义2轮廓(skyline)⋯由数据集中每一个不被其他任何点支配的点组成。2014年3月10日收到黑龙江教育厅科技项目(12523004)资助定义3．支配(k-dominate)在d维空间数第一作者简介：董雷刚(1982一)，男，博士研究生，讲师。研究方向：嵌入式计算、智能信息处理。E-mail：lgdongO10@163．com。据集D(p，P：，⋯，P)空间集S={s，s，⋯，s}，点P一支配点p，当且仅当：]ss，I．sl=k，V∈科学技术与工程14卷S，Pis≥Pis且st∈S，Pist>Pjst。I尺I=IDl，一支配

7、轮廓不再随k值增大而变化。3．1．1KIncrease定义4．支配轮廓(k-dominateskyline)k-～—Skyline算法KIncrease支配轮廓是由所有不被其他任意点七一支配的点——Skyline算法的主要思想是在原有组成。支配轮廓的基础上进行更新。给定空间数据点集性质1如果Pk+1一支配Pi，则Pi一定k一支配D及其一支配轮廓R，当k增大时至k，根据定理1Pi[可知，原有R中的点不用再参与运