Virtual self-adaptive bitmap for online cardinality estimation. Issue 114 (March 2023)

• Record Type: Journal Article
• Authors: Lu, Jie; Chen, Hongchang; Zhang, Jianpeng; Hu, Tao; Sun, Penghao; Zhang, Zhen
• Is Part Of: Information systems. Issue 114(2023)
• Publication Date: 2023-03
• Subjects: Cardinality estimation -- Data streams -- Sketch -- Online processing; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2022.102160
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Cardinality estimation is the task of obtaining the number of distinct items in a data stream, which plays an important role in many application domains. However, when dealing with high-speed data streams, it remains a significant challenge to estimate cardinality considering record/query overhead and memory efficiency. This paper proposes a virtual self-adaptive bitmap estimator to support online cardinality estimation, which reduces the record overhead to one hash per item for the first time. By logically adding virtual bits, our estimator automatically adapts its sampling probability to different stream sizes. We evaluate the virtual self-adaptive bitmap theoretically and experimentally. The experimental results show that our estimator significantly improves over the existing work in terms of record throughput, query throughput and estimation accuracy.