|
A Unified Framework for Dynamic Bit-level Counter Allocation in Sketches (IEEE TKDE, Under Review)
|
Sketches have been widely used in large-scale data stream processing. However, popular algorithms such as Elastic Sketch rely on fixed-size counters, which often require large initial allocations to handle the high skewness of real-world data streams, leading to significant memory waste. To address this, we propose BitMatcher, a unified framework for dynamic bit-level counter allocation. BitMatcher is a fast global adjustment algorithm that automatically resizes counters within each bucket to match the distribution of the data stream. The counter allocation states are determined based on a pre-defined state transition table. During stream processing, when a counter overflows, BitMatcher dynamically expands or shrinks individual counters in a fine-grained manner based on the transition table and updates the corresponding bucket flags. BitMatcher also incorporates cuckoo hashing to relocate discarded items during state transitions, preserving potential hot items and achieving global load balancing. Through these mechanisms, BitMatcher precisely manipulates allocated bits, maximizing memory utilization. Experimental results show that BitMatcher maintains high throughput while improving accuracy by up to four orders of magnitude compared to SOTA methods. We further apply the framework to enhance multiple existing sketches, consistently achieving superior performance. Additionally, we deploy BitMatcher on FPGA and Redis platforms, demonstrating its excellent scalability across both software and hardware environments.
2025.6.6: The source code of extended BitMatcher for TKDE (i.e., BitMatcher_TKDE_V1.0.zip) has been uploaded.
|
BitMatcher: Bit-level Counter Adjustment for Sketches (IEEE ICDE, 2024)
|
Sketch has been widely used in the field of large-scale data stream processing. However, common fixed-counter algorithms such as Count-Min Sketch have to allocate larger counters, which wastes a lot of memory due to the high skewness of real-world data streams. To reduce memory usage, we propose to dynamically adjust the counter size that matches the distribution of the data stream. We introduce BitMatcher, a fast global-adjusting algorithm that automatically adjusts the counter to the optimal size to match the data stream. During stream processing, BitMatcher identifies items hashed into a bucket based on isolated fingerprints. If it overflows, BitMatcher changes the flag bits in the bucket and dynamically increases or shrinks the size of some counters in a fine-grained manner. BitMatcher can also relocate a cold item in the bucket with the idea of cuckoo hashing to preserve the potential hot item while achieving global load balancing. Through the above way of dealing with overflow caused by skewed data, BitMatcher precisely manipulates allocated bits and maximizes the use of memory. The experiments show that BitMatcher has high throughput and can outperform SOTA by up to 4 orders of magnitude in terms of accuracy. We also deployed BitMatcher on several platforms, showing its good software and hardware scalability.
2025.6.6: The source code V1.1 of BitMatcher (i.e., BitMatcher_ICDE_V1.1.zip) has been uploaded, and the issue of data file reading has been fixed in this version.
2024.6.1: The conference slides of BitMatcher has been uploaded.
2023.12.1: BitMatcher has been accepted by IEEE ICDE 2024.
2023.6.1: The source code V1.0 of BitMatcher has also been uploaded at GitHub (https://github.com/wenjunpaper/BitMatcher).
2023.6.1: The website of BitMatcher is under construction and will be finished soon.
E-mail: wenjunli@pku.org.cn, wenjun0816@qq.com.