一种基于逆支配点集的数据流Top-k计算方法

J4 ›› 2012, Vol. 34 ›› Issue (6): 59-64.

一种基于逆支配点集的数据流Top-k计算方法

甘亮1,2,于莉莉3,李润恒1,贾焰1,金鑫4

（1.国防科学技术大学计算机学院,湖南长沙 410073;2.第二炮兵指挥学院三系，湖北武汉 430012；
3.北京航空航天大学计算机学院,北京 100191;4.长沙民政职业技术学院软件学院,湖南长沙 410004)

收稿日期:2010-07-20 修回日期:2011-02-15 出版日期:2012-06-25 发布日期:2012-06-25
基金资助:
国家863计划资助项目（2006AA01Z451，2007AA01Z474）

A Reverse Dominant Point Set Based Algorithm for Top- k Queries in DSMS

GAN Liang1,2,YU Lili3,LI Runheng1,JIA Yan1,JIN Xin4

(1.School of Computer Science,National University of Defense Technology,Changsha 410073;
2.Department Three,The Second Artillery Command College,Wuhan 430012;
3.School of Computer Science and Engineering,Beihang University,Beijing 100191;
4.Changsha Social Work College,Changsha 410004,China)

Received:2010-07-20 Revised:2011-02-15 Online:2012-06-25 Published:2012-06-25

摘要/Abstract

摘要：

网格索引构造简单,常用于数据流系统计算top k和skyline。但是，网格索引结构粗略，查询过程可能访问大量非top k结点。为了提高网格索引计算top k查询的精确度，本文提出基于数据点逆支配点集性质的网格索引方法，将查询访问集缩小到网格索引的“k最大运算区域区域kMCA”中，有效地减少了网格索引存储量和查询计算开销。同时，给出了kMCA索引结构及适应于数据流计算的kMCA维护更新算法。理论分析和实验结果均验证了上述方法的有效性。

关键词: 偏好top-k查询, 网格索引, 逆支配点集, 数据流

Abstract:

Grid index is often used in the query of top k and skyline in DSMS, but it is coarsegrained. In this paper, we propose a Reverse Dominant Point Set ( RDPS ) algorithm which is based on grid index, and prune a number of cells in grid index using the characteristics of RDPS to improve the precision of top k queries, thus accessing the data set in queries is limited to the kmax calculating region . So, it reduces the memory usage of grid index and the overhead of queries. Analytical and experimental evidences show the efficiency of the proposed approaches.

Key words: preference topk queries;grid index;reserve dominant point set;data stream

甘亮1,2,于莉莉3,李润恒1,贾焰1,金鑫4. 一种基于逆支配点集的数据流Top-k计算方法[J]. J4, 2012, 34(6): 59-64.

GAN Liang1,2,YU Lili3,LI Runheng1,JIA Yan1,JIN Xin4. A Reverse Dominant Point Set Based Algorithm for Top- k Queries in DSMS[J]. J4, 2012, 34(6): 59-64.

[1]	李金熹, 尹首一, 魏少军, 胡杨. 基于MLIR的数据流模型[J]. 计算机工程与科学, 2024, 46(07): 1151-1157.
[2]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(06): 959-967.
[3]	丁滟, 王闯, 冯了了, 王锋, 常俊胜. 基于区块链监管的联盟数据可信流通[J]. 计算机工程与科学, 2022, 44(10): 1771-1780.
[4]	张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 基于Hellinger距离的不平衡漂移数据流Boosting分类算法[J]. 计算机工程与科学, 2022, 44(05): 788-799.
[5]	乔冠杰, 吕高锋, 谭靖, 莫露莎. 大规模数据流统计中冷热流替换策略优化[J]. 计算机工程与科学, 2021, 43(09): 1567-1573.
[6]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[7]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[8]	熊菊霞1,2,3,吴尽昭1,2,3. 异构复杂信息网络敏感数据流动态挖掘[J]. 计算机工程与科学, 2020, 42(04): 628-633.
[9]	张馨予, 安建成, 曹锐. 基于自适应随机森林的数据流分类算法[J]. 计算机工程与科学, 2020, 42(03): 543-549.
[10]	杨杰，张东月，周丽华，黄皓，丁海燕. 基于网格耦合的数据流异常检测[J]. 计算机工程与科学, 2020, 42(01): 25-35.
[11]	袁泉1,2,郭江帆1,赵学华1. 一种基于集成的不均衡数据流分类算法[J]. 计算机工程与科学, 2019, 41(08): 1519-1524.
[12]	李艺煌，马胜，郭阳，陈桂林，徐睿. 基于平铺数据流的可配置神经网络加速器[J]. 计算机工程与科学, 2019, 41(06): 963-972.
[13]	李易1，常成娟1，卢圣健1，江道忠2，范东睿1，叶笑春1. 面向数据流结构的指令映射优化方法[J]. 计算机工程与科学, 2019, 41(01): 9-13.
[14]	杨胜哲，于俊清,唐九飞. 数据流程序动态调度与优化[J]. 计算机工程与科学, 2017, 39(07): 1201-1210.
[15]	梁毅1，侯颖1，陈诚1，金翊2. 面向大数据流式计算的任务管理技术综述[J]. 计算机工程与科学, 2017, 39(02): 215-226.