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

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

作　　者：甘亮[1,2] 于莉莉[3] 李润恒[1] 贾焰[1] 金鑫[4] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]第二炮兵指挥学院三系,湖北武汉430012 [3]北京航空航天大学计算机学院,北京100191 [4]长沙民政职业技术学院软件学院,湖南长沙410004

出　　处：《计算机工程与科学》2012年第6期59-64,共6页Computer Engineering & Science

基　　金：国家863计划资助项目(2006AA01Z451;2007AA01Z474)

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

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]