一种有效的不确定数据流Top-K查询算法

摘要

Top-K queries have always been a significant technique in the management of uncertain data streams.Based on the prevailing uncertain data model and possible world semantic model,in this paper,an uncertain model and its query semantics are defined.An algorithm for Top-K queries on uncertain data streams is designed and realized,which return k queries having maximum rank scores.Rank score of a query result is well-defined,depending on its possibility under the possible world.The extensive experiments demonstrate that compared to CSQ and SCSQ,this algorithm is more practical and efficient.%rop-K查询处理是不确定性数据管理中一项重要技术.本文在分析不确定性数据模型和可能世界模型的基础上,定义了不确定数据流元组的查询语义,提出了基于记录向量的Top-K查询算法,该算法根据K值,计算并返回分值最高前K个结果,其查询结果评价综合考虑了查询结果在可能世界语义下的概率大小.实验结果表明,与CSQ和SCSQ算法相比,本算法更具高效性和实用性.