Computing rarity on uncertain data  

作　　者：JIN CheQing ZHOU MinQi ZHOU AoYing 

机构地区：[1]Shanghai Key Laboratory of Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai 200062, China

出　　处：《Science China(Information Sciences)》2011年第10期2028-2039,共12页中国科学（信息科学）（英文版）

基　　金：supported by the Key Program of National Natural Science Foundation of China (Grant No.60933001);the National Natural Science Foundation of China (Grant No.60803020);the Natural Science Foundation of China (Grant No.61021004);Shanghai Leading Academic Discipline Project (Project No.B412);The research of Aoying Zhou was supported by the National Science Foundation for Distinguished Young Scholars (Grant No.60925008)

摘　　要：The essence of uncertain data management has been well adopted since data uncertainty widely exists in lots of applications, such as Web, sensor networks, etc. Most of the uncertain data models are based on the possible world semantics. Because the number of the possible worlds will blowup exponentially with the growth of the data set, it is much more challenging to handle uncertain data than deterministic data. In this paper, we take the first attempt to study the rarity, an important statistic that describes the proportion of items with the same frequency, upon uncertain data. We have proposed three novel solutions, including an exact method and an approximate method to compute the rarity of a given frequency respectively, and a method to find the frequency of the maximum rarity. Analysis in theorem and extensive experimental results demonstrate the effectiveness and efficiency of the proposed solutions.The essence of uncertain data management has been well adopted since data uncertainty widely exists in lots of applications, such as Web, sensor networks, etc. Most of the uncertain data models are based on the possible world semantics. Because the number of the possible worlds will blowup exponentially with the growth of the data set, it is much more challenging to handle uncertain data than deterministic data. In this paper, we take the first attempt to study the rarity, an important statistic that describes the proportion of items with the same frequency, upon uncertain data. We have proposed three novel solutions, including an exact method and an approximate method to compute the rarity of a given frequency respectively, and a method to find the frequency of the maximum rarity. Analysis in theorem and extensive experimental results demonstrate the effectiveness and efficiency of the proposed solutions.

关 键 词：RARITY uncertain data possible world 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O571.3[自动化与计算机技术—控制科学与工程]