blocked-bloom-filter · shipping · also Cache-local Bloom filter

Blocked Bloom filter

A Bloom-filter layout that confines the bit probes for a key to one selected block to improve memory locality.

Uneven block occupancy changes false-positive behavior; total fill alone is insufficient. Multiple-choice variants change both placement and lookup. [1]

Parquet uses a specific split-block design: eight 32-bit words per block, with one selected bit per word. This is not an arbitrary set of independent addresses in a block. [2]

Hesela's finite examples explicitly model uniform one-block selection, not a production implementation. [3]

Relations

related

bloom-filter, partitioned-filter, sstable

Citations

1. Johanna Elena Schmitz, Jens Zentgraf and Sven Rahmann. Blocked Bloom Filters with Choices. SEA 2025, article 25, sections 3-4. DOI: 10.4230/LIPIcs.SEA.2025.25. (accessed 2026-10-17)
2. Apache Parquet: Bloom Filter, Technical Approach. (accessed 2026-10-17)
3. Hesela: finite Bloom probabilities and block load. (accessed 2026-10-17)

JSON: /data/terms/blocked-bloom-filter.json