|
|||||
|
|
| 不确定性数据上聚合查询的近似算法 | |
| 引用本文： | 陈东辉,陈岭,王俊凯,吴勇,王敬昌.不确定性数据上聚合查询的近似算法[J].清华大学学报(自然科学版),2018(3). |
| 作者姓名： | 陈东辉 陈岭 王俊凯 吴勇 王敬昌 |
| 作者单位： | 浙江大学计算机科学与技术学院;浙江鸿程计算机系统有限公司; |
| 摘 要： | 随着大数据时代的到来,不确定性数据上的聚合查询面临形式多样、计算复杂等挑战。该文将不确定性数据上聚合查询的结果定义为所有可能的值以及对应的概率。基于动态规划思想的求解"和"的分布(distribution sum,DSUM)精确算法,提出贪心的"和"的分布(greedy distribution sum,GDSUM)和折半合并的"和"的分布(binary merge distribution sum,BMDSUM)的近似算法,这2种算法都能应用于元组级不确定性模型和属性级不确定性模型;并通过理论分析,给出算法的时间和空间复杂度以及最终结果的误差范围。实验结果表明:误差设定为1%时,2种近似算法分别能缩短执行时间15%~21%和22%~32%。 |
| 本文献已被 CNKI 等数据库收录！ | |