按年被提到
20202020 · 2 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:2002.03057 · cs.DS

The Bloom Tree

Lum Ramabaja, Arber Avdullahu · 2020
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2020-02-11 · 最近 2021-07-31
3不同的人
2活跃月份
3讨论串
3被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We introduce a data structure that allows for efficient (probabilistic) presence proofs and non-probabilistic absence proofs in a bandwidth efficient and secure way. The Bloom tree combines the idea of Bloom filters with that of Merkle trees. Bloom filters are used to verify the presence, or absence of elements in a set. In the case of the Bloom tree, we are interested to verify and transmit the presence, or absence of an element in a secure and bandwidth efficient way to another party. Instead of sending the whole Bloom filter to check for the presence, or absence of an element, the Bloom tree achieves efficient verification by using a compact Merkle multiproof.

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

HN 书评

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

“You still need one hash for every non-leaf node, so 30-40 hashes of 256 bits each. What this algorithm saves is 30-40 indices, which is 11 bits each for a 1000-leaf tree. Even aligning to 16 bits it's doesn't seem a great optimization. Unless I misunderstood something and we are not trying to minimize the size of whole proof, but just its structure - but…”

The Compact Merkle Multiproof原评论 ↗
评论sitkack · 2021-07

“I realize I wasn't clear. I used 2 sqlite databases just to store the article titles and offsets into binary files (<2GB) that had chunks of compressed data. Each chunk contained 10s-100s of stories, so that the decompressed around was around 20megs I believe. I had planned to store everything in sqlite, but there were too many issues. The FTS extension t…”

Show HN: Static.wiki – read-only Wikipedia using a 43GB SQLite file原评论 ↗
被提交为 story · 1 次