kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Aleph Filter: To Infinity in Constant Time
University of Toronto, Canada.
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8430-2441
BARC, University of Copenhagen Denmark.
2024 (English)In: Proceedings of the VLDB Endowment, E-ISSN 2150-8097, Vol. 17, no 11, p. 3644-3656Article in journal, Meeting abstract (Other academic) Published
Abstract [en]

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 prob lem 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.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2024. Vol. 17, no 11, p. 3644-3656
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-354655DOI: 10.14778/3681954.3682027ISI: 001416287900017Scopus ID: 2-s2.0-85205372083OAI: oai:DiVA.org:kth-354655DiVA, id: diva2:1904551
Conference
50th International Conference on Very Large Data Bases, VLDB 2024, Guangzhou, China, Aug 24 2024 - Aug 29 2024
Note

QC 20250303

Available from: 2024-10-09 Created: 2024-10-09 Last updated: 2025-03-17Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Bercea, Ioana

Search in DiVA

By author/editor
Bercea, Ioana
By organisation
Theoretical Computer Science, TCS
In the same journal
Proceedings of the VLDB Endowment
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 29 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf