计算机应用 ›› 2010, Vol. 30 ›› Issue (10): 2605-2609.

• 数据库与数据挖掘 • 上一篇    下一篇

不确定数据库中概率top-k和排序查询算法

周帆,李树全,肖春静,吴跃   

  1. 电子科技大学
  • 收稿日期:2010-04-08 修回日期:2010-05-17 发布日期:2010-09-21 出版日期:2010-10-01
  • 通讯作者: 李树全
  • 基金资助:
    博士点基金资助项目;国家863计划项目

Probabilistic top-k and ranking query algorithms in uncertain databases

  • Received:2010-04-08 Revised:2010-05-17 Online:2010-09-21 Published:2010-10-01

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

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

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