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

作者：甘亮; 于莉莉; 李润恒; 贾焰; 金鑫

来源：计算机工程与科学, 2012, (06): 59-64.

• 偏好top-k查询
• 网格索引
• 逆支配点集
• 数据流 preference top-k queries
• grid index
• reserve dominant point set
• data stream

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

• 单位
  中国人民解放军陆军炮兵防空兵学院; 中国人民解放军国防科学技术大学; 北京航空航天大学