What's hot and what's not: tracking most frequent items dynamically
What's hot and what's not: tracking most frequent items dynamically
复制标题
DOI：
10.1145/773153.773182
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Graham Cormode;S. Muthukrishnan
中科院分区：
文献类型：
--
作者：
Graham Cormode;S. Muthukrishnan
大多数数据库管理系统都维护基础关系的统计信息。重要的统计数据之一是关系中的“热门项目”：那些出现多次的统计数据（最频繁，或超过某些阈值）。例如，最终偏置直方图将热门项目作为直方图的一部分保持，并用于选择性估计中。热门项目用作数据挖掘中的简单异常值，在网络应用程序中的异常检测中用作异常检测。我们提出了一种新算法，用于在关系中随时动态确定热门项目，该算法正在进行删除操作以及插入。我们的算法保持了一个小的空间数据结构，该结构可以监视关系上的交易，并在需要时快速输出所有热门项目，而无需重新撤销数据库中的关系。使用用户指定的概率，它可以报告所有热门项目。我们的算法依赖于“小组测试”的想法，非常易于实施，并且具有可证明的质量，时空保证。以前针对此问题具有相似质量和性能保证的算法无法处理删除，而处理删除的算法则不能在不撤销数据库的情况下提供相似的保证。我们使用真实和合成数据的实验表明，我们的算法在动态跟踪与插入和缺失率无关的热门项目中非常准确。
Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the "hot items" in the relation: those that appear many times (most frequently, or more than some threshold). For example, end-biased histograms keep the hot items as part of the histogram and are used in selectivity estimation. Hot items are used as simple outliers in data mining, and in anomaly detection in networking applications.We present a new algorithm for dynamically determining the hot items at any time in the relation that is undergoing deletion operations as well as inserts. Our algorithm maintains a small space data structure that monitors the transactions on the relation, and when required, quickly outputs all hot items, without rescanning the relation in the database. With user-specified probability, it is able to report all hot items. Our algorithm relies on the idea of "group testing", is simple to implement, and has provable quality, space and time guarantees. Previously known algorithms for this problem that make similar quality and performance guarantees can not handle deletions, and those that handle deletions can not make similar guarantees without rescanning the database. Our experiments with real and synthetic data shows that our algorithm is remarkably accurate in dynamically tracking the hot items independent of the rate of insertions and deletions.