Entropy-Punctured Bloom Filters for Memory-Efficient Machine Learning

John Cartmell; Mihaela Cardei; Ionut Cardei

cs.LGSep 12, 2026

Entropy-Punctured Bloom Filters for Memory-Efficient Machine Learning

Authors: John Cartmell, Mihaela Cardei, Ionut Cardei

Organizations: Department of Electrical Engineering and Computer Science Florida Atlantic University Boca Raton, FL, USA

Abstract

Memory-efficient feature representations are increasingly important in machine learning settings where storage, transmission cost, bandwidth, or privacy constraints limit access to raw data. Bloom Filter (BF) encodings provide compact probabilistic representations of engineered features, but their behavior under structural compression and their applicability to regression tasks remain underexplored. In this work, we propose entropy-punctured Bloom Filters, a memory-aware encoding strategy that removes low-variability bit positions identified using empirical entropy. Starting from fixed-length BF encodings of quantized features, the proposed approach produces reduced representations that preserve predictive structure while improving predictive efficiency relative to encoded representation size. We evaluate the approach on diverse regression datasets, comparing raw features, Principal Component Analysis (PCA), Random Projection (RP), and Bloom Filter variants under leakage-free evaluation protocols and approximately matched representation sizes. Performance is assessed using ridge regression, XGBoost, and neural networks, with predictive efficiency measured as R2 relative to encoded representation size per sample. Results show that Bloom Filter encodings remain competitive with classical compressed representations while achieving substantial storage savings. Entropy-based puncturing further reduces representation size with minimal loss in predictive fidelity, yielding improved predictive efficiency. These findings demonstrate that entropy-punctured Bloom Filters provide an effective representation-level compression approach for memory-constrained machine learning.

Figures & tables

Dataset	Type	Samples	Features	Raw Size (bytes per sample)
Abalone	Tabular	4,177	8	64
Airline	Time series	144	12	96
Allstate	Tabular	188,318	130	170
Bike	Time series	17,379	24	192
Boston	Tabular	506	13	104
California	Tabular	20,640	8	64

TABLE I: Summary of Datasets

Dataset	$m$ Bytes	$k$ Hashes	$\tau$ Threshold
Abalone	32	3	0.30
Airline	192	3	0.05
Allstate	256	2	0.10
Bike	108	2-3	0.15
Boston	32	3	0.30
California	64	2	0.10

TABLE II: Bloom Filter Encoding Parameters Used for Each Dataset

Dataset	Raw	Non-BF	PBF
Abalone	0.593	0.627	0.591
Airline	0.994	0.990	0.879
Allstate	0.567	0.521	0.558
Bike	0.943	0.938	0.912
Boston	0.882	0.785	0.819
California	0.852	0.795	0.764

TABLE III: Best predictive performance (

R^{2}

) achieved for each representation type across datasets.

Dataset	Non-BF	PBF	Best
Abalone	0.0203	0.0293	PBF
Airline	0.0309	0.0898	PBF
Allstate	0.0027	0.0093	PBF
Bike	0.0085	0.0084	RP
Boston	0.0082	0.0380	PBF
California	0.0124	0.0449	PBF

TABLE IV: Predictive efficiency measured as

R^{2}

relative to encoded representation size per sample.

Fig. 1: Effect of varying Bloom Filter size ( $m$ ) and hash count ( $k$ ) on XGBoost $R^{2}$ performance for the California Housing dataset.

Fig. 2: Bit occupancy as a function of Bloom Filter size and hash count.

Fig. 3: Entropy behavior under varying Bloom Filter size and hash count.

Fig. 4: Predictive fidelity ( $R^{2}$ ) as a function of entropy puncturing threshold for the Parkinson’s dataset.

Fig. 5: Predictive efficiency as a function of entropy puncturing threshold for the Parkinson’s dataset.

Fig. 6: Predictive fidelity ( $R^{2}$ ) as a function of the fraction of Bloom Filter bits removed under different removal strategies.

Fig. 7: Predictive efficiency under different Bloom Filter bit removal strategies.

Keep Ratio	Bytes	$R^{2}$	$R^{2}$ /Byte
1.00	64	0.8824	0.0138
0.90	58	0.8828	0.0152
0.80	52	0.8819	0.0170
0.70	45	0.8809	0.0196
0.60	39	0.8752	0.0224
0.50	32	0.8807	0.0275

TABLE V: Effect of Bloom Filter folding on predictive fidelity and predictive efficiency for the Parkinson’s dataset using XGBoost.

Dataset	Method	$R^{2}$	Bytes	PE
California	PBF	0.7622	23.6	0.0323
	FH	0.0844	24.0	0.0035
Parkinson’s	PBF	0.8830	32.4	0.0273
	FH	0.3654	32.0	0.0114

TABLE VI: Storage-matched comparison with feature hashing.

Communication Complexity of Universal Features
Oct 19, 2026Lunjia Hu, Anish Jayant, Peter Li +2Representation Learning Communication Complexity
Northeastern University · Georgia Institute of Technology · Harvard University
An Introduction to Compression-Based Machine Learning
Sep 18, 2026John Hurwitz, Edward Raff, Charles K. NicholasMinimum Description Length
University of Maryland, Baltimore County · CrowdStrike · Syracuse University
Efficient Learned Image Compression without Entropy Coding
May 22, 2026Hao Cao, Wenqi Guo, Zhijin Qin +1Learned Image Compression Vector Quantization
Department of Electronic Engineering, Tsinghua University · Department of Automation, Tsinghua University · State Key Laboratory of Space Network and Communications +1

Oct 19, 2026J/K move · Enter open · S save

Communication Complexity of Universal Features

Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor+1

Northeastern University · Georgia Institute of Technology · Harvard University

Representation Learning Communication Complexity Shared Representation Learning

Open paper AskPDF arXiv

Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes

X\sim D

and produces a finite encoding before a task

f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}

is specified. For each task, a decoder must predict

f(X)

with error at most

\varepsilon

under

D

. We construct an encoder that outputs a representation with

O(d^{*}\log(1/\varepsilon))

bits, where

d^{*}

is the dual VC dimension of

\mathcal{F}

. Our encoder greedily selects

O((d^{*}/\varepsilon)\log(1/\varepsilon))

functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every

d^* \ge 1

and

\varepsilon < 1/4

up to a universal constant factor, and instance-wise optimal for every family

\mathcal{F}

up to an

O(\log(1/\varepsilon))

factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.

Abstract

Explore similar work

Communication Complexity of Universal Features

An Introduction to Compression-Based Machine Learning

Efficient Learned Image Compression without Entropy Coding