Low-Memory Online Feature Selection for High-Dimensional Data Streams: Scalable Algorithms and Implementation Tips

Introduction

Working with high-dimensional data streams forces a trade-off between memory and predictive performance. In practice, you may not have the luxury of storing full feature matrices or running batch feature selection. This article explores practical, low-memory online feature selection strategies for high-dimensional streams, with scalable algorithms and hands-on implementation tips. Expect concrete examples, code snippets, and design patterns that you can adapt to real-world pipelines.

Problem setup and constraints

Imagine a data stream where new samples arrive continuously and features can be in the order of hundreds of thousands or more. Typical constraints include:

Memory budget: only a few megabytes to a few hundred megabytes for feature metadata and model parameters.
Single-pass requirement: each example is processed once or few times.
Concept drift: feature relevance may change over time.
Sparse inputs: many features are zero for a given example.

Key strategies at a glance

Feature hashing to bound memory usage of the vector representation.
Sketching and count-min style summaries for approximate feature statistics.
Online regularized learners that induce sparsity (truncated gradient, FTRL, FOBO S).
Budgeted selection keeping a fixed-size set of active features updated by importance.
Sliding windows or decay factors to handle drift without storing history.

Algorithms and patterns

Below are practical algorithms that fit strict memory limits, with intuition and implementation hints.

1. Feature hashing + online linear models

Feature hashing maps an unbounded vocabulary into a fixed-size vector. Combine it with an online linear model such as SGDClassifier with L1-style regularization or FTRL for sparse weights. Pros: constant memory for vectorization and model weights. Cons: collisions can blur feature interpretability.

2. Count-min sketches for frequency and co-occurrence

Use count-min sketches to maintain approximate feature frequencies or simple joint statistics. These sketches use sublinear memory and are suitable for prioritizing features by estimated information content. Tune width and depth according to error tolerance.

3. Truncated gradient and model-driven selection

Compute online gradients and periodically truncate small weights to zero. Keep only top-k nonzero weights. This pattern moves the selection problem into the model update; memory is proportional to the active features maintained in a sparse map.

4. Reservoir-style top-k selection with decay

Maintain a bounded priority structure of features ranked by a score (absolute weight, mutual information estimate, or frequency). When the budget is full, evict the lowest scored feature. Apply exponential decay to scores to adapt to drift.

Concrete streaming pipeline (example)

The following pattern is easy to implement and memory efficient for text or sparse categorical streams:

Use HashingVectorizer to convert tokens to a fixed-length sparse vector.
Train an online classifier with partial_fit and an L1-friendly optimizer.
Periodically prune weights to keep only top-k nonzero coefficients.
Monitor performance on a sliding window and adjust budget or hash size as needed.

from sklearn.feature_extraction.text import HashingVectorizer
from sklearn.linear_model import SGDClassifier
import numpy as np
from scipy.sparse import csr_matrix

# fixed memory: hash_size controls vector dimension
hash_size = 2 ** 16  # tune according to budget
vec = HashingVectorizer(n_features=hash_size, alternate_sign=False, norm=None)

# online classifier that supports partial_fit
clf = SGDClassifier(loss='log', penalty='l1', alpha=1e-4, warm_start=True)

# keep track of active features (sparse dict of index -> weight)
active_budget = 5000

def topk_prune(coef, k):
    # coef is 1D numpy array
    idx = np.argpartition(np.abs(coef), -k)[-k:]
    mask = np.zeros_like(coef, dtype=bool)
    mask[idx] = True
    pruned = np.where(mask, coef, 0.0)
    return pruned

# stream loop (pseudo)
classes = [0, 1]
for text, label in stream_generator():  # stream_generator yields (text, label)
    x = vec.transform([text])  # sparse vector
    clf.partial_fit(x, [label], classes=classes)
    # prune periodically
    if should_prune():
        w = clf.coef_.ravel()
        clf.coef_ = np.reshape(topk_prune(w, active_budget), clf.coef_.shape)

This example uses hashing and online updates to bound memory. The pruning operation keeps the model sparse and under control. For multiclass problems adapt shapes accordingly.

Memory-saving data structures

Choose structures that store only nonzero entries and small summaries:

Sparse CSR/CSC matrices for batched updates.
Dict of feature -> weight for coordinate updates when active set is small.
Count-min sketch for frequency summaries with fixed size.
Bloom filters to detect novelty without storing entire vocabularies.
Heap or bounded sorted list for top-k features by score.

Practical tips and trade-offs

Choose hash size by memory budget. Collisions cost accuracy but reduce memory. Run small experiments to find the sweet spot.
Prefer sparse updates. Avoid materializing dense vectors in the inner loop.
Use decay rather than storing timestamps for drift adaptation. Multiply scores by a factor 0<<1 periodically.
Batch updates when possible. Accumulate small micro-batches to amortize overhead without blowing memory.
Monitor effective feature count. Keep a running count of active features to control pruning frequency.
Profile memory. Measure resident set size on representative loads to validate assumptions.

Evaluation in streaming settings

Offline cross-validation is less relevant. Use streaming-friendly metrics:

Prequential evaluation: predict then learn for each incoming instance.
Sliding window metrics to reflect recent accuracy and recall.
Memory-accuracy curve: plot accuracy versus budgeted memory to justify choices.

When to pick each approach

Quick guidance:

Text or very high-cardinality categorical: hashing + online learner.
When frequency matters: count-min for candidates, then model-driven pruning.
When interpretability matters: bounded dictionary with eviction and low collision techniques, accepting higher memory.
When drift is heavy: small sliding windows or aggressive decay on scores.

Advanced ideas

Consider these refinements if your pipeline allows a bit more complexity:

Feature grouping: hash groups instead of individual features to preserve some semantics.
Ensemble of small models: a bank of lightweight experts that each monitor a subset of features; combine predictions.
Adaptive budgets: allocate more memory to features with high volatility or predictive value.
Sketch-based PCA: Frequent Directions for low-rank approximation when you need dense latent features.

Common pitfalls

Aggressive hashing without testing can destroy signal via collisions.
Pruning too frequently may prevent the model from recovering after brief spikes in importance.
Using dense operations in the hot path causes memory spikes despite a small nominal budget.
Ignoring evaluation on recent data hides degradation due to drift.

Checklist before production

Set a hard memory budget and verify with profiling on realistic loads.
Choose hashing size and pruning budget based on a small grid search with streaming emulation.
Instrument per-feature memory and count metrics; log eviction events.
Implement simple rollback or switch to previous parameters in case of sudden drop in performance.

Final thought: building low-memory online feature selection is a balancing act. Small, measurable changes to vectorization, model sparsity, and eviction policy often yield the largest gains. Start with hashing plus an L1-capable online learner, add sketches for candidate scoring, and iterate with careful profiling.