面向不确定数据流的近似ER-Topk查询处理

来源：计算机工程与应用杂志2017年第4期北京时间：

作者：刘 骁，刘辉平，金澈清

单位：华东师范大学 数据科学与工程研究院，上海 200062

摘要：随着移动互联网的快速发展以及信息技术的普遍应用，在许多应用中都产生了海量、不确定性数据，包括金融、军事、位置服务、医疗以及气象等。然而，传统的确定性数据管理方法很难管理不确定数据，亟需开发新型数据管理方法。可能世界模型被广泛用于为不确定数据建模，通过该模型可以衍生出诸多确定性的可能世界实例。不确定性数据流是指高速到达的海量不确定元组序列，因而不确定数据流管理比不确定性静态数据管理更具挑战性。面向于不确定数据流的ER-Topk查询是一个典型问题，但是处理复杂度高。提出一种近似算法来处理该查询，具有较小的空间复杂度；同时，还通过搜索策略优化来进一步提升查询处理效率。实验结果验证了所提方法的有效性和高效性。

关键词：数据流,不确定数据,查询优化