Skyline代表点的研究

来源 :宁波大学 | 被引量 : 0次 | 上传用户:whisperings
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Skyline查询返回数据集合中不被任意对象支配的对象,描述了数据集的轮廓,在多目标决策、偏好查询等领域具有重要应用。目前 Skyline查询受到了学者的极大关注,在集中式环境和分布式环境下开展了卓有成效的工作。然而,Skyline查询存在一个不足,即随着数据属性维度的增大,Skyline查询返回的结果集大小无法控制,最坏情况下可能接近原数据集,从而无法为用户的决策提供有效的支持。基于这个背景,在 Skyline集中选择有代表性的点显得日益重要。本文在集中式和分布式环境下研究了选择 k个skyline代表点的问题,它同时考虑得分与距离两个因素,返回了更具代表的skyline点。本文的主要贡献包括:  (1)集中式环境下,定义了新的评价函数作为Skyline代表点的衡量尺度,选取具有 k个最大评价函数值的Skyline作为Skyline代表点。新的评价函数兼顾了得分与距离双重属性,满足体现 Skyline集分布特性,同时又具有高支配能力的k个数据点的集合,最大化代表点的得分和非代表点与它最近的代表点之间距离的乘积。在二维空间提出了基于动态规划的解决方案,在高维空间采用aR-tree的索引结构存储数据,给出了近似的解决算法。算法维持一个访问列表,每次迭代先计算访问列表中得分与代表距离乘积最大的条目,再判断其是否被支配。若条目被支配则将其剪枝且终止当前迭代;若不被支配则继续迭代,选择条目中得分与代表距离最大的子条目继续计算。  (2)分布式环境下,提出了一个适用于分布式的评价函数。提出了 FDRA算法,算法利用反馈方法降低了计算开销。分布子节点每次只发送局部最大评价 F值的点到中心服务器,服务器再选取具有最大评价值和最小评价值的点 pa和 pb发送到分布子节点比较剪枝。若 pa不被任意点支配剪枝,则返回 pa作为一个skyline代表点输出并把被 pa支配的点剪枝;同时若分布节点内局部代表点的评价函数值值比 pb小,则剪枝整个分布节点,因为该分布节点内的点不可能成为代表点。算法尽早地最大限度地剪枝不可能成为skyline代表的点,大大地降低了通信开销,而且具有很好的渐进性。  (3)将提出的集中式和分布式下的算法与已有的解决算法进行了对比实验。集中式环境下,从评价函数值、代表错误以及运行时间等方面对算法的性能进行了分析验证;分布式环境下,从元组转移数目、评价函数值等方面进行评估,实验结果显示了新算法的有效性。
其他文献
对象技术和组件技术是当前计算机发展的热点。J2EE标准作为应用程序开发和运行平台,综合了面向对象技术、软件体系结构理论、组件技术、分布式对象技术等多方面的研究成果,为
机器人足球比赛是近年来国际上兴起的一种高科技竞赛活动。足球机器人是集机器人学、智能控制、数据融合、计算机技术、无线通讯、图像处理、机械学等多种学科和技术于一体的
随着科学技术的发展,人体动作识别逐渐成为人工智能和机器视觉领域一个重要的研究方向,具有广阔的发展前景和很强的实用价值。可应用于日常的视频监控、智能医疗、运动分析、
随着移动通信技术、计算机技术、网络技术的迅猛发展,现代移动通信技术已迈入3G(3rd Generation)时代。第三代移动通信系统是现代通信技术、网络技术以及计算机技术融合的产
近几年随着无线通信技术、传感器技术、信息采集和处理技术的飞速发展,出现了低成本、低功耗、多功能的微型无线传感器结点。这些微型无线传感器结点在目标环境中构筑成网络,通
网络化制造是企业在网络环境支持下,开展其业务的一种先进制造模式,是提高行业和区域核心企业及企业群体综合竞争力的重要手段。网络化制造集成平台是网络化制造系统的控制与
随着信息技术的飞速发展,信息安全成为21世纪初期信息产业发展的焦点。数字水印技术作为一种新型的信息安全技术,在数字产品版权保护、原始数据的真伪鉴别、数据侦测与跟踪等
经过多年的信息化之后,很多机构都积累了大量的历史数据,这些数据往往被闲置起来,没有的到充分的利用;另外人们对计算机的数据处理能力也提出了更高的需求,不再满足于传统的事务型
基于非接触式IC卡的校园“一卡通”系统是IC卡在教育领域的一个重要应用。读卡器是“一卡通”系统中最主要设备之一,读卡器本身一般带有RS-232接口或者标准RS-485接口,可支持
移动终端逐渐成为人们的日常生活和工作中不可或缺的一部分,越来越多的移动终端接入互联网,网络资源的共享跨越了时空的限制,信息安全问题暴露的越来越多。随着人们消费观念的改