Sketch Disaggregation Across Time and Space
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915202905145344 |
|---|---|
| author | Langlet, Jonatan Chen, Peiqing Mitzenmacher, Michael Basat, Ran Ben Liu, Zaoxing Antichi, Gianni |
| author_facet | Langlet, Jonatan Chen, Peiqing Mitzenmacher, Michael Basat, Ran Ben Liu, Zaoxing Antichi, Gianni |
| contents | Streaming analytics are essential in a large range of applications, including databases, networking, and machine learning. To optimize performance, practitioners are increasingly offloading such analytics to network nodes such as switches. However, resources such as fast SRAM memory available at switches are limited, not uniform, and may serve other functionalities as well (e.g., firewall). Moreover, resource availability can also change over time due to the dynamic demands of in-network applications.
In this paper, we propose a new approach to disaggregating data structures over time and space, leveraging any residual resource available at network nodes. We focus on sketches, which are fundamental for summarizing data for streaming analytics while providing beneficial space-accuracy tradeoffs. Our idea is to break sketches into multiple `fragments' that are placed at different network nodes. The fragments cover different time periods and are of varying sizes, and are combined to form a network-wide view of the underlying traffic. We apply our solution to three popular sketches (namely, Count Sketch, Count-Min Sketch, and UnivMon) and demonstrate we can achieve approximately a 75% memory size reduction for the same error for many queries, or a near order-of-magnitude error reduction if memory is kept unchanged. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sketch Disaggregation Across Time and Space Langlet, Jonatan Chen, Peiqing Mitzenmacher, Michael Basat, Ran Ben Liu, Zaoxing Antichi, Gianni Networking and Internet Architecture Streaming analytics are essential in a large range of applications, including databases, networking, and machine learning. To optimize performance, practitioners are increasingly offloading such analytics to network nodes such as switches. However, resources such as fast SRAM memory available at switches are limited, not uniform, and may serve other functionalities as well (e.g., firewall). Moreover, resource availability can also change over time due to the dynamic demands of in-network applications. In this paper, we propose a new approach to disaggregating data structures over time and space, leveraging any residual resource available at network nodes. We focus on sketches, which are fundamental for summarizing data for streaming analytics while providing beneficial space-accuracy tradeoffs. Our idea is to break sketches into multiple `fragments' that are placed at different network nodes. The fragments cover different time periods and are of varying sizes, and are combined to form a network-wide view of the underlying traffic. We apply our solution to three popular sketches (namely, Count Sketch, Count-Min Sketch, and UnivMon) and demonstrate we can achieve approximately a 75% memory size reduction for the same error for many queries, or a near order-of-magnitude error reduction if memory is kept unchanged. |
| title | Sketch Disaggregation Across Time and Space |
| topic | Networking and Internet Architecture |
| url | https://arxiv.org/abs/2503.13515 |