期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 30, 期 4, 页码 1674-1688出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2022.3147204
关键词
Estimation; Throughput; Frequency modulation; Registers; Memory management; Internet; IEEE transactions; Cardinality estimation; bitmap; morphing
类别
资金
- NSF [CNS-1719222, CSR-1909077]
This paper proposes a self-morphing bitmap as a new solution for estimating the cardinality of a data stream. It combines operational simplicity with structural dynamics, automatically adapting to different stream sizes. The theoretical and experimental evaluation demonstrates its significant improvement over previous techniques.
Estimating the cardinality of a data stream is a fundamental problem underlying numerous applications such as traffic monitoring in a network or a datacenter and query optimization of Internet-scale P2P data networks. Existing solutions suffer from high processing/query overhead or memory in-efficiency, which prevents them from operating online for data streams with very high arrival rates. This paper takes a new solution path different from the prior art and proposes a self-morphing bitmap, which combines operational simplicity with structural dynamics, allowing the bitmap to be morphed in a series of steps with an evolving sampling probability that automatically adapts to different stream sizes. We further generalize the design of self-morphing bitmap. We evaluate the self-morphing bitmap theoretically and experimentally. The results demonstrate that it significantly outperforms the prior art.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据