面向属性级不确定数据的U-Topk查询优化算法的研究

作者：于洋; 赵志滨; 鲍玉斌; 于戈

来源：计算机研究与发展, 2013, S1: 125-132.

• 不确定性数据
• 属性级不确定性
• 可能世界模型
• U-Topk
• 查询处理 uncertain data
• attribute-level uncertain
• possible world
• U-Topk
• query processing

U-Topk是基于不确定性数据可能世界模型而提出的一种查询语义.随着不确定性数据集的增大,可能世界的实例数量指数增长,这为U-Topk查询处理提出了重大挑战.针对属性级不确定性的UTopk查询处理算法展开研究,提出了U-Topk查询处理优化算法APT4U-Topk.首先通过预处理来确定必然进入最终结果集的元组,从而实现k值的压缩.然后,依次读取后续元组,计算可能世界模型聚合概率,并判断此时刻是否为可能世界模型聚合概率的阈值.当到达阈值时算法停止.此时概率最大的聚合可能世界模型就是U-Topk查询结果.最后,通过实验对APT4U-Topk算法进行了时空效率的验证.实验结果表明,在数据集和k值增大的情况下,APT4U-Topk算法要优于此前提出的OptU-Topk算法.

• 单位
  东北大学