Abstract: Processing and querying on uncertain and probabilistic data has emerged as a new research area in both databases and data mining communities due to the generation of a huge amount of such data in applications such as sensor networks and RFID technology. Both top-k query and ranking query are important and useful tools for analyzing the large collection of uncertain data. Various algorithms of probabilistic top-k and ranking query on uncertain data were introduced and reviewed. The semantics and application scenarios of different querying processing algorithms were analyzed. The computation cost and querying semantics of the existing probabilistic top-k and ranking queries were also compared. Finally, the challenges and possible research directions of uncertain databases querying and processing were presented.

Key words: uncertain database, top-k query, rank query, probabilistic data

摘要： 传感器网络等技术的广泛应用产生了大量不确定数据。近年来,对于不确定数据的处理和查询成为数据库和数据挖掘领域研究的热点。其中,传统关系数据库中的top-k查询和排序查询怎样拓展到不确定数据是其中的焦点之一。研究近年来提出的不确定数据库上top-k查询和排序查询算法,归纳和比较目前各种不同查询算法所适应的语义世界和应用场景,并详细分析各种算法的执行效率和算法复杂度。另外,对于不确定数据top-k查询和排序查询所面临的挑战和可能的研究方向进行了总结。

关键词: 不确定数据库, top-k查询, 排序查询, 不确定性数据