.png){kind=icon}
返回
Distinct Counting With a Self-Learning Bitmap
.png){kind=icon}
OA
AI
DOI：10.1198/jasa.2011.ap10217.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Counting the number of distinct elements (cardinality) in a dataset is a fundamental problem in database management. In recent years, there has been significant interest to address the distinct counting problem in a data stream setting, where each incoming data can be seen only once and cannot be stored for long periods of time. Many probabilistic approaches based on either sampling or sketching have been proposed in the computer science literature that only require limited computing and memory resources. However, the performances of these methods are not scale invariant, in the sense that their relative root mean square estimation errors (RRMSE) depend on the unknown cardinalities. This is not desirable in many applications where cardinalities can be dynamic or inhomogeneous and many cardinalities need to be estimated. In this article, we develop a novel approach, called self-learning bitmap (S-bitmap) that is scale invariant for cardinalities in a specified range. S-bitmap uses a binary vector whose entries are updated from 0 to 1 by an adaptive sampling process for inferring the unknown cardinality, where the sampling rates are reduced sequentially as more and more entries change from 0 to I. We prove rigorously that the S-bitmap estimate is not only unbiased but scale invariant. We demonstrate that to achieve a small RRMSE value of E or less, our approach requires significantly less memory and uses similar or fewer operations than state-of-the-art methods for many common practice cardinality scales. Both simulation and experimental studies are reported.
Keyword:
Markov chain
Martingale
Sampling
Streaming data
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
J
IF:
3
论文数:
5.2K
被引数:
4.8W
机构
引用论文
.png){kind=icon}
分享收藏Molecular dynamics simulations of void effect of the copper nanocubes under triaxial tensions铜纳米立方体在三维拉伸条件下的空位效应分子动力学模拟
PREAI
分享收藏Kationische Carbonyliridium(III)‐Komplexe: [Ir(CO)6]3+ und [Ir(CO)5Cl]2+碳羰基化 (III)-复合物: [Ir(CO)6]3 und [Ir(CO)5Cl]2
PREAI
分享收藏分享收藏
查看更多内容