模式识别与人工智能
2025年4月5日 星期六   首 页     期刊简介     编委会     投稿指南     伦理声明     联系我们                                                                English
模式识别与人工智能  2015, Vol. 28 Issue (3): 239-246    DOI: 10.16451/j.cnki.issn1003-6059.201503007
研究与应用 最新目录| 下期目录| 过刊浏览| 高级检索 |
Skyline代表点的选择*
杨立龙,董一鸿,何贤芒,钱江波
宁波大学 信息科学与工程学院 宁波315211
Selection of Skyline Representative Point
YANG Li-Long, DONG Yi-Hong, HE Xian-Mang, QIAN Jiang-Bo
College of Information Science and Engineering, Ningbo University, Ningbo 315211

全文: PDF (470 KB)   HTML (1 KB) 
输出: BibTeX | EndNote (RIS)      
摘要 Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
杨立龙
董一鸿
何贤芒
钱江波
关键词 Skyline查询Skyline代表点集中式环境动态规划    
Abstract:Skyline query plays an important role in multi-decision and data mining. However, with the growth of data dimension, Skyline set becomes very large. Skyline representative point query is studied to overcome this shortcoming. A new evaluation function is proposed to improve the score-computing of Skyline points so as to select k representative Skyline points. A dynamic programming based algorithm(DPBA) in two-dimensional space is presented. The Eulerian distance between representative point and non-representative point is determined by the cover circle. k representative points are got by computing the evaluation function iteratively. In high-dimensional space, an approximate solution based on aR-tree index is proposed to solve the NP-hard problem. The index tree is traversed to judge whether it is dominated by the candidate Skyline sets. If it is dominated, it should be pruned to reduce the computation cost. The experiments of synthetic and real data show that the proposed algorithms are effective and efficient.
Key wordsSkyline Query    Skyline Representative Point    Centralized Environment    Dynamic
Programming
  
收稿日期: 2013-11-05     
ZTFLH: TP391.4  
基金资助:国家自然科学基金项目(No.61202007)、浙江省自然科学基金项目(No.LY13F020040)、宁波市自然科学基金项目(No.2013A610063)资助
作者简介: 杨立龙,男,1988年生,硕士研究生,主要研究方向为数据库、数据挖掘.E-mail:yllong1988@163.com.董一鸿(通讯作者),男,1969年生,博士,教授,主要研究方向为移动数据库、大数据、人工智能.E-mail:dongyihong@nbu.edu.cn.何贤芒,男,1982年生,博士,讲师,主要研究方向为数据挖掘、隐私保护.钱江波,男,1974年生,博士,教授,主要研究方向为大数据、数据挖掘.
引用本文:   
杨立龙,董一鸿,何贤芒,钱江波. Skyline代表点的选择*[J]. 模式识别与人工智能, 2015, 28(3): 239-246. YANG Li-Long, DONG Yi-Hong, HE Xian-Mang, QIAN Jiang-Bo. Selection of Skyline Representative Point. , 2015, 28(3): 239-246.
链接本文:  
http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201503007      或     http://manu46.magtech.com.cn/Jweb_prai/CN/Y2015/V28/I3/239
版权所有 © 《模式识别与人工智能》编辑部
地址:安微省合肥市蜀山湖路350号 电话:0551-65591176 传真:0551-65591176 Email:bjb@iim.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn