Aleph Filter: To Infinity in Constant Time
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_ | 1866929569003470848 |
|---|---|
| author | Dayan, Niv Bercea, Ioana-Oriana Pagh, Rasmus |
| author_facet | Dayan, Niv Bercea, Ioana-Oriana Pagh, Rasmus |
| contents | Filter data structures are widely used in various areas of computer science to answer approximate set-membership queries. In many applications, the data grows dynamically, requiring their filters to expand along with the data. However, existing methods for expanding filters cannot maintain stable performance, memory footprint, and false positive rate (FPR) simultaneously. We address this problem with Aleph Filter, which makes the following contributions. (1) It supports all operations (insertions, queries, deletes, etc.) in constant time, no matter how much the data grows. (2) Given an estimate of how much the data will ultimately grow, Aleph Filter provides a memory vs. FPR trade-offs on par with static filters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04703 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Aleph Filter: To Infinity in Constant Time Dayan, Niv Bercea, Ioana-Oriana Pagh, Rasmus Databases Data Structures and Algorithms Filter data structures are widely used in various areas of computer science to answer approximate set-membership queries. In many applications, the data grows dynamically, requiring their filters to expand along with the data. However, existing methods for expanding filters cannot maintain stable performance, memory footprint, and false positive rate (FPR) simultaneously. We address this problem with Aleph Filter, which makes the following contributions. (1) It supports all operations (insertions, queries, deletes, etc.) in constant time, no matter how much the data grows. (2) Given an estimate of how much the data will ultimately grow, Aleph Filter provides a memory vs. FPR trade-offs on par with static filters. |
| title | Aleph Filter: To Infinity in Constant Time |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.04703 |