按年被提到
20212024 · 1 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:2109.01892 · cs.DS

Fast Succinct Retrieval and Approximate Membership using Ribbon

Peter C. Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, Stefan Walzer · 2021
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-05-22 · 最近 2025-05-02
2不同的人
2活跃月份
2讨论串
18被引(OpenAlex)
arXiv 摘要(候选层不写导读)

A retrieval data structure for a static function $f:S\rightarrow \{0,1\}^r$ supports queries that return $f(x)$ for any $x \in S$. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ), i.e., a Bloom filter alternative, with false positive rate $2^{-r}$. The information-theoretic lower bound for both tasks is $r|S|$ bits. While succinct theoretical constructions using $(1+o(1))r|S|$ bits were known, these could not achieve very small overheads in practice because they have an unfavorable space--time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below 1\,\% while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead $\geq 44\,\%$). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We additionally describe homogeneous ribbon filter AMQs, which are even simpler and faster at the price of slightly larger space overhead.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论judofyr · 2024-05

“Very interesting and I'll have to read more to understand how it fully works, but _initially_ the space requirements doesn't seem too impressive? Am I missing something here? Is my calculation/assumption completely off? Maybe the solution here is more flexible? One alternative approach for many of these problems is to start with a perfect minimal hash fu…”

Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)原评论 ↗
评论f_devd · 2025-05

“Also based on Ribbon, the BuRR filters: https://arxiv.org/pdf/2109.01892 which seem to get very close to the theoretical optimum, 0.1%-0.5% overhead comparatively”

Bloom Filters原评论 ↗