BTreeU-Topk:基于二叉树的不确定数据上的Top-k查询算法

应用需求的发展衍生各种查询类型,Top-k查询是交互环境下一种重要查询类型.由于数据的不确定性,传统数据上的Top-k查询技术和方法不能直接应用于不确定数据查询.在已有不确定数据上Top-k查询算法的基础上,提出基于二叉树的不确定数据上Top-k查询算法BTreeU-Topk;为了提高算法执行效率,对二叉树进行修剪操作进而提出BTreeOPTU-Topk和BTreePU-Topk算法.实验结果表明,BTreeU-Topk,BTreeOPTU-Topk以及BTreePU-Topk算法在不同数据分布以及k值增长时均优于现有算法.

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

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