Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.09607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910410310942720 |
|---|---|
| author | Belazzougui, Djamal Kucherov, Gregory Walzer, Stefan |
| author_facet | Belazzougui, Djamal Kucherov, Gregory Walzer, Stefan |
| contents | We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact solutions to this problem are based on error-correcting coding techniques and suffer from a large decoding time. Existing probabilistic solutions based on Invertible Bloom Lookup Tables (IBLTs) are time-efficient but offer insufficient success guarantees for many applications. Here we propose a tunable trade-off between the two approaches combining the efficiency of IBLTs with exponentially decreasing failure probability. The proof relies on a refined analysis of IBLTs proposed in (Baek Tejs Houen et al. SOSA 2023) which has an independent interest. We also propose a modification of our algorithm that enables telling apart the elements of each set in the symmetric difference. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09607 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Better space-time-robustness trade-offs for set reconciliation Belazzougui, Djamal Kucherov, Gregory Walzer, Stefan Data Structures and Algorithms We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact solutions to this problem are based on error-correcting coding techniques and suffer from a large decoding time. Existing probabilistic solutions based on Invertible Bloom Lookup Tables (IBLTs) are time-efficient but offer insufficient success guarantees for many applications. Here we propose a tunable trade-off between the two approaches combining the efficiency of IBLTs with exponentially decreasing failure probability. The proof relies on a refined analysis of IBLTs proposed in (Baek Tejs Houen et al. SOSA 2023) which has an independent interest. We also propose a modification of our algorithm that enables telling apart the elements of each set in the symmetric difference. |
| title | Better space-time-robustness trade-offs for set reconciliation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.09607 |