Finding frequent items in probabilistic data
Finding frequent items in probabilistic data
复制标题
DOI：
10.1145/1376616.1376698
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Qin Zhang;Feifei Li;K. Yi
中科院分区：
文献类型：
--
作者：
Qin Zhang;Feifei Li;K. Yi
概率数据的统计信息计算最近吸引了大量的关注，因为从广泛的数据源生成的数据本质上是模糊的或不确定的。本文研究了概率数据的一个重要统计查询：频繁项查找。识别概率数据集中频繁项的一种直接方法是简单地计算项的预期频率，并决定它是否超过整个数据集的预期大小的某个分数。然而，这个简单的定义忽略了关于概率数据的内部结构和所有不确定实体之间的相互作用的重要信息。因此，我们提出了一个新的定义的基础上的可能世界的语义，已被广泛采用的许多查询类型在不确定的数据管理，试图找到所有的项目可能是频繁的随机生成的可能世界。我们的方法自然也会导致基于置信度对频繁项进行排名的研究。在概率数据中找到可能的频繁项要困难得多。我们首先提出精确算法离线数据的二次或三次时间。接下来，我们设计了新的基于采样的流数据算法，以找到所有近似可能的频繁项，理论上保证了高概率和准确性。我们的采样方案消耗亚线性内存并具有出色的可扩展性。最后，我们使用真实的和合成的数据集进行了广泛的实验评估，验证了我们的算法的有效性和效率。
Computing statistical information on probabilistic data has attracted a lot of attention recently, as the data generated from a wide range of data sources are inherently fuzzy or uncertain. In this paper, we study an important statistical query on probabilistic data: finding the frequent items. One straightforward approach to identify the frequent items in a probabilistic data set is to simply compute the expected frequency of an item and decide if it exceeds a certain fraction of the expected size of the whole data set. However, this simple definition misses important information about the internal structure of the probabilistic data and the interplay among all the uncertain entities. Thus, we propose a new definition based on the possible world semantics that has been widely adopted for many query types in uncertain data management, trying to find all the items that are likely to be frequent in a randomly generated possible world. Our approach naturally leads to the study of ranking frequent items based on confidence as well. Finding likely frequent items in probabilistic data turns out to be much more difficult. We first propose exact algorithms for offline data with either quadratic or cubic time. Next, we design novel sampling-based algorithms for streaming data to find all approximately likely frequent items with theoretically guaranteed high probability and accuracy. Our sampling schemes consume sublinear memory and exhibit excellent scalability. Finally, we verify the effectiveness and efficiency of our algorithms using both real and synthetic data sets with extensive experimental evaluations.