Approaching 100% Confidence in Stream Summary through ReliableSketch
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911898662862848 |
|---|---|
| author | Wu, Yuhan Wu, Hanbo Liu, Xilai Zhao, Yikai Yang, Tong Yang, Kaicheng Wang, Sha Miao, Lihua Xie, Gaogang |
| author_facet | Wu, Yuhan Wu, Hanbo Liu, Xilai Zhao, Yikai Yang, Tong Yang, Kaicheng Wang, Sha Miao, Lihua Xie, Gaogang |
| contents | To approximate sums of values in key-value data streams, sketches are widely used in databases and networking systems. They offer high-confidence approximations for any given key while ensuring low time and space overhead. While existing sketches are proficient in estimating individual keys, they struggle to maintain this high confidence across all keys collectively, an objective that is critically important in both algorithm theory and its practical applications. We propose ReliableSketch, the first to control the error of all keys to less than $Λ$ with a small failure probability $Δ$, requiring only $O(1 + Δ\ln\ln(\frac{N}Λ))$ amortized time and $O(\frac{N}Λ + \ln(\frac{1}Δ))$ space. Furthermore, its simplicity makes it hardware-friendly, and we implement it on CPU servers, FPGAs, and programmable switches. Our experiments show that under the same small space, ReliableSketch not only keeps all keys' errors below $Λ$ but also achieves near-optimal throughput, outperforming competitors with thousands of uncontrolled estimations. We have made our source code publicly available. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00376 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approaching 100% Confidence in Stream Summary through ReliableSketch Wu, Yuhan Wu, Hanbo Liu, Xilai Zhao, Yikai Yang, Tong Yang, Kaicheng Wang, Sha Miao, Lihua Xie, Gaogang Data Structures and Algorithms Databases To approximate sums of values in key-value data streams, sketches are widely used in databases and networking systems. They offer high-confidence approximations for any given key while ensuring low time and space overhead. While existing sketches are proficient in estimating individual keys, they struggle to maintain this high confidence across all keys collectively, an objective that is critically important in both algorithm theory and its practical applications. We propose ReliableSketch, the first to control the error of all keys to less than $Λ$ with a small failure probability $Δ$, requiring only $O(1 + Δ\ln\ln(\frac{N}Λ))$ amortized time and $O(\frac{N}Λ + \ln(\frac{1}Δ))$ space. Furthermore, its simplicity makes it hardware-friendly, and we implement it on CPU servers, FPGAs, and programmable switches. Our experiments show that under the same small space, ReliableSketch not only keeps all keys' errors below $Λ$ but also achieves near-optimal throughput, outperforming competitors with thousands of uncontrolled estimations. We have made our source code publicly available. |
| title | Approaching 100% Confidence in Stream Summary through ReliableSketch |
| topic | Data Structures and Algorithms Databases |
| url | https://arxiv.org/abs/2406.00376 |