The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929453359169536 |
|---|---|
| author | Zhao, Fuheng Agrawal, Divyakant Abbadi, Amr El Mathieu, Claire Metwally, Ahmed de Rougemont, Michel |
| author_facet | Zhao, Fuheng Agrawal, Divyakant Abbadi, Amr El Mathieu, Claire Metwally, Ahmed de Rougemont, Michel |
| contents | In this paper, we present an advanced analysis of near optimal algorithms that use limited space to solve the frequency estimation, heavy hitters, frequent items, and top-k approximation in the bounded deletion model. We define the family of SpaceSaving$\pm$ algorithms and explain why the original SpaceSaving$\pm$ algorithm only works when insertions and deletions are not interleaved. Next, we propose the new Double SpaceSaving$\pm$, Unbiased Double SpaceSaving$\pm$, and Integrated SpaceSaving$\pm$ and prove their correctness. The three proposed algorithms represent different trade-offs, in which Double SpaceSaving$\pm$ can be extended to provide unbiased estimations while Integrated SpaceSaving$\pm$ uses less space. Since data streams are often skewed, we present an improved analysis of these algorithms and show that errors do not depend on the hot items. We also demonstrate how to achieve relative error guarantees under mild assumptions. Moreover, we establish that the important mergeability property is satisfied by all three algorithms, which is essential for running the algorithms in distributed settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_12623 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions Zhao, Fuheng Agrawal, Divyakant Abbadi, Amr El Mathieu, Claire Metwally, Ahmed de Rougemont, Michel Databases Data Structures and Algorithms In this paper, we present an advanced analysis of near optimal algorithms that use limited space to solve the frequency estimation, heavy hitters, frequent items, and top-k approximation in the bounded deletion model. We define the family of SpaceSaving$\pm$ algorithms and explain why the original SpaceSaving$\pm$ algorithm only works when insertions and deletions are not interleaved. Next, we propose the new Double SpaceSaving$\pm$, Unbiased Double SpaceSaving$\pm$, and Integrated SpaceSaving$\pm$ and prove their correctness. The three proposed algorithms represent different trade-offs, in which Double SpaceSaving$\pm$ can be extended to provide unbiased estimations while Integrated SpaceSaving$\pm$ uses less space. Since data streams are often skewed, we present an improved analysis of these algorithms and show that errors do not depend on the hot items. We also demonstrate how to achieve relative error guarantees under mild assumptions. Moreover, we establish that the important mergeability property is satisfied by all three algorithms, which is essential for running the algorithms in distributed settings. |
| title | The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2309.12623 |