QPOPSS: Query and Parallelism Optimized Space-Saving for Finding Frequent Stream Elements
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916380047048704 |
|---|---|
| author | Jarlow, Victor Stylianopoulos, Charalampos Papatriantafilou, Marina |
| author_facet | Jarlow, Victor Stylianopoulos, Charalampos Papatriantafilou, Marina |
| contents | The frequent elements problem, a key component in demanding stream-data analytics, involves selecting elements whose occurrence exceeds a user-specified threshold. Fast, memory-efficient $ε$-approximate synopsis algorithms select all frequent elements but may overestimate them depending on $ε$ (user-defined parameter). Evolving applications demand performance only achievable by parallelization. However, algorithmic guarantees concerning concurrent updates and queries have been overlooked. We propose Query and Parallelism Optimized Space-Saving (QPOPSS), providing concurrency guarantees. The design includes an implementation of the \emph{Space-Saving} algorithm supporting fast queries, implying minimal overlap with concurrent updates. QPOPSS integrates this with the distribution of work and fine-grained synchronization among threads, swiftly balancing high throughput, high accuracy, and low memory consumption. Our analysis, under various concurrency and data distribution conditions, shows space and approximation bounds. Our empirical evaluation relative to representative state-of-the-art methods reveals that QPOPSS's multi-threaded throughput scales linearly while maintaining the highest accuracy, with orders of magnitude smaller memory footprint. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | QPOPSS: Query and Parallelism Optimized Space-Saving for Finding Frequent Stream Elements Jarlow, Victor Stylianopoulos, Charalampos Papatriantafilou, Marina Distributed, Parallel, and Cluster Computing The frequent elements problem, a key component in demanding stream-data analytics, involves selecting elements whose occurrence exceeds a user-specified threshold. Fast, memory-efficient $ε$-approximate synopsis algorithms select all frequent elements but may overestimate them depending on $ε$ (user-defined parameter). Evolving applications demand performance only achievable by parallelization. However, algorithmic guarantees concerning concurrent updates and queries have been overlooked. We propose Query and Parallelism Optimized Space-Saving (QPOPSS), providing concurrency guarantees. The design includes an implementation of the \emph{Space-Saving} algorithm supporting fast queries, implying minimal overlap with concurrent updates. QPOPSS integrates this with the distribution of work and fine-grained synchronization among threads, swiftly balancing high throughput, high accuracy, and low memory consumption. Our analysis, under various concurrency and data distribution conditions, shows space and approximation bounds. Our empirical evaluation relative to representative state-of-the-art methods reveals that QPOPSS's multi-threaded throughput scales linearly while maintaining the highest accuracy, with orders of magnitude smaller memory footprint. |
| title | QPOPSS: Query and Parallelism Optimized Space-Saving for Finding Frequent Stream Elements |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2409.01749 |