PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy-Punctured Bloom Filters for Memory-Efficient Machine Learning

John Cartmell, Mihaela Cardei, Ionut Cardei

arXiv:2609.14187v1cs.LGcs.AI

TL;DR

Regression use of Bloom Filter encodings under explicit memory constraints remains underexplored, despite storage and bandwidth limits on raw feature access. The paper introduces entropy-based puncturing of low-variability bits and finds that Bloom Filter encodings remain competitive while puncturing generally improves storage-normalized predictive efficiency.

  • Problem

    Bloom Filter encodings for regression under explicit memory constraints remain largely unexplored, even as storage and bandwidth constraints limit access to raw features.

    Source: §I · p. 1

  • Method

    The method compresses fixed-length Bloom Filter feature encodings by removing low-variability bit positions identified through empirical entropy.

    Source: §I · p. 1, §VII · p. 9

  • Results

    Across diverse regression datasets, Bloom Filter encodings remain competitive with classical dimensionality reduction, and entropy-guided puncturing generally improves predictive efficiency relative to encoded size.

    Source: §VII · p. 9

  • Takeaways & Limitations

    Entropy-punctured Bloom Filters offer a practical representation-level compression approach for combining fixed-length feature encoding with structural compression under memory constraints.

    Source: §VII · p. 9

    Entropy is an unsupervised marginal measure rather than target mutual information, so puncturing may remove low-entropy positions that remain predictive.

    Source: §VI · p. 8

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper examines Bloom Filter feature encodings for regression under memory constraints and proposes entropy-guided removal of low-variability bits. It frames predictive efficiency as a storage-aware complement to predictive fidelity.

I. INTRODUCTION

  • Bloom Filter regression under explicit memory constraints remains underexplored, while storage and bandwidth limits can restrict access to raw features.Accuracy alone does not capture the trade-off between predictive performance and representation size.Source: §I · p. 1
  • Predictive efficiency measures R2 relative to encoded representation size per sample, summarizing predictive signal retained per unit storage.The paper also investigates how entropy-ranked removal and Bloom Filter folding affect predictive fidelity and representation size.Source: §I · pp. 1–2
  • Entropy-punctured Bloom Filters remove low-variability bit positions to reduce redundancy while preserving predictive structure.The method preferentially removes near-constant positions and retains positions that vary more across samples.Source: §I · p. 1
  • Across diverse regression datasets and three model families, Bloom Filter variants maintain predictive fidelity while substantially improving predictive efficiency.Evaluation compares against raw features and classical compression methods using leakage-free protocols and approximately matched representation sizes.Source: §I · p. 1

II. RELATED WORK

  • Prior Bloom Filter encoding work has emphasized classification or privacy-utility trade-offs, whereas this work studies structural compression for regression.The related-work discussion also treats marginal entropy as an indicator of near-constant bits, not a measure of target relevance.Source: §II · p. 2

III. METHODS

The method first maps engineered feature symbols into fixed-length Bloom Filter vectors, then punctures positions using training-set marginal entropy. The retained mask is applied unchanged to validation data.

A. Bloom Filter Feature Encoding

  • Numeric features are discretized, categorical features used directly, and text tokenized before symbols are mapped into an m-bit vector with k hashing operations.Temporal datasets may use lagged features and separate segment encodings concatenated into one fixed-length representation.Source: A. Bloom Filter Feature Encoding · p. 2

B. Entropy-Based Puncturing

  • Entropy-guided puncturing retains bit positions whose empirical marginal entropy meets threshold τ, producing a representation containing only those positions.The entropy of each bit is computed from its activation probability across training samples.Source: B. Entropy-Based Puncturing · p. 2
  • Marginal entropy identifies near-constant positions but does not measure whether a bit is predictive of the target.A low-entropy bit may still mark a rare predictive event, so entropy is a label-independent indicator rather than a guarantee of predictive relevance.Source: B. Entropy-Based Puncturing · p. 3
  • Entropy statistics are computed from each training fold and its resulting mask is applied unchanged to validation data to prevent information leakage.Source: B. Entropy-Based Puncturing · p. 3

C. Parameters

The encoding is controlled by four parameters, selected through a lightweight heuristic intended to find stable operating regimes without exhaustive sweeps.

C. Parameters

  • Bloom Filter size m, hash count k, quantization-bin count b, and entropy threshold τ jointly control representation capacity, collisions, sparsity, and compression.Source: C. Parameters · p. 3
  • A lightweight heuristic selects candidate Bloom Filter sizes, hash counts, and entropy thresholds to balance fidelity and compression without exhaustive parameter sweeps.Candidate sizes depend on dataset dimensionality and target representation size; hash counts aim for moderate occupancy.Source: C. Parameters · p. 3
  • Within each fold, parameter selection and the entropy mask use only the training partition, while validation data is reserved for out-of-sample evaluation.Representations share data splits and downstream model configurations.Source: C. Parameters · p. 3

D. Structural Analysis

The structural analysis probes how removal, permutation, and folding alter Bloom Filter representations. The broader experiments compare predictive fidelity, efficiency, and structural robustness across representations and regression models.

D. Structural Analysis

  • Random bit removal and high-entropy bit removal are compared with entropy-based puncturing to assess where predictive signal is concentrated.Source: D. Structural Analysis · p. 3
  • Randomly permuting bit positions tests whether predictive performance depends on positional structure or aggregate activation patterns.Source: D. Structural Analysis · p. 3
  • Folding combines pairs of bit positions with logical OR, reducing Bloom Filter size by about half while increasing collisions through superposition.Source: D. Structural Analysis · p. 3

IV. EXPERIMENTS

  • Experiments compare raw features, classical dimensionality reduction, and Bloom Filter encodings across datasets and regression model families.The evaluation considers predictive fidelity, predictive efficiency, and structural robustness.Source: §IV · p. 3

A. Datasets

The evaluation spans heterogeneous regression datasets and uses shared, leakage-free procedures to compare representations. Bloom Filter settings are selected with a lightweight heuristic, and predictive performance is reported as stable across moderate parameter variations.

A. Datasets

  • The testbed covers tabular, time-series, biomedical sensor, and sparse text regression datasets.Source: A. Datasets · p. 3

B. Evaluation Protocol

  • Preprocessing is fitted on training partitions and applied unchanged to held-out data, with shared partitions and folds across representations.Source: B. Evaluation Protocol · pp. 3–4

C. Bloom Filter Configuration

D. Regression Models

The experiments use linear and nonlinear regression learners, compare Bloom Filter encodings with raw and dimension-reduced features, and probe structural and entropy-based changes to the encodings.

D. Regression Models

  • Ridge regression, XGBoost, and neural networks test whether Bloom Filter encodings preserve predictive structure across linear and nonlinear learners.Source: D. Regression Models · p. 4

E. Baseline Feature Representations

F. Bloom Filter Structural Experiments

G. Entropy-Based Puncturing Experiments

H. Structural Robustness Experiments

The section tests robustness to bit-vector transformations and defines how predictive fidelity and storage cost are assessed. Predictive efficiency is a storage-normalized measure interpreted alongside fidelity, not across unrelated datasets.

H. Structural Robustness Experiments

I. Evaluation Metrics

  • Predictive fidelity is measured by R2, and representation cost is the bytes needed to store one encoded sample.Source: §I · p. 5
  • Predictive efficiency divides R2 by encoded bytes per sample and is interpreted jointly with R2, not as a universal cross-dataset measure.Source: §I · p. 5
  • Table III summarizes best predictive performance (R2) across representation types and datasets.Source: Table III · p. 5

V. RESULTS

Punctured Bloom Filters lead predictive efficiency in most datasets while remaining competitive in the remaining case. They also maintain competitive predictive fidelity against raw and classical compressed representations, and larger filters with moderate hash counts provide the strongest reported structural trade-off.

B. Best Raw vs. Best Compressed vs. Punctured Bloom Filters

  • Across datasets, Punctured Bloom Filters maintain competitive predictive performance against raw features and classical dimensionality reduction despite substantially smaller representations.Source: B. Best Raw vs. Best Compressed vs.… · p. 5

A. Evaluation Perspective

C. Predictive Efficiency: R2 Relative to Encoded Representation Size

D. Bloom Filter Parameter Sensitivity Analysis

E. Impact of Entropy Threshold on Predictive Efficiency

Moderate entropy thresholds reduce Bloom Filter size with limited fidelity loss, while structural experiments show that removal strategy and compression method affect the fidelity-efficiency trade-off.

E. Impact of Entropy Threshold on Predictive Efficiency

  • Thresholds between approximately 0.15 and 0.35 remove a large fraction of low-variability positions, while higher thresholds eventually reduce capacity and predictive fidelity.At low thresholds, puncturing highly saturated or inactive bits substantially reduces representation size with minimal fidelity loss.Source: E. Impact of Entropy Threshold on… · pp. 6–7
  • R2 = 0.8830 ± 0.0083 at τ = 0.15 on Parkinson’s with XGBoost, while representation size fell from 64 bytes to approximately 32 bytes per sample.The result is reported across cross-validation folds.Source: Figure 5 · p. 7

F. Structural Robustness Experiments

  • Removing higher-entropy positions is more damaging than removing lower-entropy or randomly selected positions in the evaluated representation.The structural comparison evaluates fidelity across fractions of bits removed under the three strategies.Source: Figure 7 · p. 7, F. Structural Robustness Experiments · p. 7
  • Under low-entropy removal, predictive efficiency increases over moderate removal levels as representation size falls while fidelity remains relatively stable.The reported behavior reflects the storage-performance trade-off summarized by predictive efficiency.Source: F. Structural Robustness Experiments · p. 7
  • Reducing the representation from 64 bytes to 32 bytes preserves nearly identical predictive performance, but more aggressive folding can increase collisions and degrade fidelity.OR-based folding combines bit positions and increases collision rates through bit superposition.Source: F. Structural Robustness Experiments · pp. 7–8

G. Storage-Matched Feature Hashing Comparison

At nearly matched storage budgets, PBF retained greater predictive fidelity and efficiency than standard signed feature hashing in the focused comparison. The discussion frames this result alongside broader compression findings and qualifications on entropy-based puncturing.

VI. DISCUSSION

  • Across diverse regression datasets, Bloom Filter encodings remained competitive with classical dimensionality-reduction methods and generally improved predictive efficiency relative to encoded representation size.The focused comparison on California Housing and Parkinson’s Telemonitoring also found substantially greater predictive fidelity than standard signed feature hashing, without establishing general superiority.Source: §VI · p. 8

G. Storage-Matched Feature Hashing Comparison

  • At nearly identical storage budgets, PBF retained substantially greater predictive fidelity and predictive efficiency than standard signed feature hashing.This focused comparison does not establish general superiority over feature hashing.Source: Table VI · p. 8, G. Storage-Matched Feature Hashing… · p. 8

VI. DISCUSSION

  • Entropy-guided puncturing removes low-variability positions; structural experiments found their removal less damaging than removing higher-entropy or randomly selected positions over moderate compression levels.Entropy is not a direct measure of target relevance.Source: §VI · p. 8
  • Predictive efficiency complements R2 as a descriptive, within-dataset measure of model performance relative to representation cost, not as an information-theoretic quantity or replacement for R2.Source: §VI · p. 8
  • Collisions can obscure fine-grained distinctions under aggressive compression; parameter choices depend on dataset characteristics, sparsity, and tokenization, and low-entropy bits may still predict the target.The lightweight heuristic does not guarantee globally optimal configurations.Source: §VI · p. 8

VII. CONCLUSION

The conclusion presents entropy-based puncturing as a way to compress Bloom Filter feature representations for regression while retaining useful predictive fidelity. Across the evaluated datasets, puncturing generally improved storage-relative predictive efficiency, though more aggressive compression eventually reduced fidelity.

VII. CONCLUSION

  • The method removes low-variability bit positions using statistics estimated from training data, reducing encoded representation size while preserving predictive fidelity.Source: §VII · p. 9
  • Across diverse regression datasets, Bloom Filter encodings remained competitive with classical dimensionality-reduction methods, and entropy-guided puncturing generally improved predictive efficiency relative to encoded representation size.Moderate puncturing removed substantial redundancy with limited performance degradation, while more aggressive compression eventually reduced predictive fidelity.Source: §VII · p. 9
  • Entropy-punctured Bloom Filters offer a practical approach to fixed-length feature encoding with structural compression under memory constraints.Future work includes supervised bit selection, adaptive parameter selection, alternative tokenization, and distributed or privacy-sensitive learning settings.Source: §VII · p. 9
Loading 2609.14187v1…