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

在传感器网络、RFID等各种应用中会产生大量不确定性数据,有效的Top-K查询处理是不确定性数据管理中一项重要技术。针对已有的Top-K查询没有很好地结合元组的分值和不确定性,在分析不确定性数据模型和可能世界模型的基础上,定义了不确定数据流元组的查询语义。设计并实现了一种有效的Top-K查询算法。该算法按照元组的得分值进行降序排列,概率值最高的前K个元组集合就是Top-K的查询结果,实验结果表明,与CSQ和SCSQ算法相比,更具高效性和实用性。

An efficient algorithm for Top-K queries on uncertain data streams

Massive uncertain data streams are produced in many modern applications such as RFID technology and sensor networks. Efficient processing of Top-K queries has always been a significant technique in the management of uncertain data streams. Traditional Top-K queries do not process in conjunction with the score and uncertainty of tuples. Based on the prevailing uncertain data model and possible world semantic model, in this paper, a new semantics of Top-K queries for uncertain data is defined and an efficient algorithm for Top-K queries on uncertain data streams is designed and realized. The algorithm in this paper sorts the tuples in a descending order of score values and selects the k tuples with the highest probabilities from the sets of different numbers of the tuples. The extensive experiments demonstrate that compared to CSQ and SCSQ, this algorithm is more practical and efficient.