有效的子空间支配查询算法——Ranking-k

来源：计算机应用杂志2015年第1期北京时间：

作者：李秋生, 吴亚东, 林茂松, 王松, 王海洋, 冯鑫淼

单位：1. 西南科技大学 计算机科学与技术学院, 四川 绵阳621010;2. 西南科技大学 信息工程学院, 四川 绵阳621010;3. 中国工程物理研究院 电子工程研究所, 四川 绵阳621010

摘要：针对Top-k dominating查询算法需要较高的时空消耗来构建属性组合索引,并且在相同属性值较多情况下的查询结果准确率低等问题,提出一种通过B+-trees和概率分布模型相结合的子空间支配查询算法——Ranking-k算法.首先,采用B+-trees为待查找数据各属性构建有序列表;然后,采取轮询调度算法读取skyline准则涉及到的有序列表,生成候选元组并获得k组终结元组;其次,根据生成的候选元组和终结元组,采用概率分布模型计算终结元组支配分数.迭代上述过程优化查询结果,直到满足条件为止.实验结果表明:Ranking-k与基本扫描算法(BSA)相比,查询效率提高了94.43%;与差分算法(DA)相比,查询效率提高了7.63%;与早剪枝Top-k支配(TDEP)算法、BSA和DA相比,查询结果更接近理论值.

关键词：Top-k dominating,子空间,Ranking-k算法,有序列表,轮询调度算法

基金资助：国家自然科学基金资助项目(61303127);国家科技支撑计划项目(2013BAH32F02,2013BAH32F03);国防重点学科实验室项目(13zxnk12);四川省教育厅重点项目(13ZA0169);四川省苗子工程资助项目(2014-043);西南科技大学研究生创新基金资助项目(14ycx057).