Data Stream Mining

Ma Mahalakshmi V Updated 14 Nov 2026
6 min read ·Lesson 94 of 140

Every algorithm covered elsewhere in this series implicitly assumes the full dataset is available to look at repeatedly — an association-rule miner can scan the transaction table as many times as it needs, a clustering algorithm can revisit every point. Data stream mining removes that assumption entirely: the data arrives continuously, is effectively unbounded (a stock ticker or a network traffic feed has no defined "last row"), and in most designs can only be looked at once, since storing the entire history defeats the purpose. This single-pass, bounded-memory constraint is the same one covered from a device-level angle in the lesson on ubiquitous data mining (a sensor with limited memory computing a running mean via Welford's algorithm); this lesson covers the techniques that constraint demands at the stream level — sampling, windowing, and detecting when the stream's underlying pattern has changed.

Fixed Windows vs. Sliding Windows

Since a stream can't be stored in full, most stream algorithms operate on a window — a bounded, recent slice of the stream — rather than the whole history. A fixed window processes the stream in non-overlapping chunks: readings 1–100, then 101–200, computing a fresh result for each chunk independently. A sliding window instead maintains a constant-size view that moves forward one item at a time — after processing reading 101, a window of size 100 drops reading 1 and now covers readings 2–101. The practical difference matters: a fixed window can miss a pattern that straddles a chunk boundary (a spike that happens across readings 95–105 gets split and diluted across two separate chunks), while a sliding window catches it because every possible 100-reading span eventually gets evaluated — at the cost of recomputing statistics far more often.

Maintaining a Random Sample: Reservoir Sampling

The vague-sounding "store some data for later" requirement raises a genuinely hard question when the stream's total length is unknown in advance: how do you keep a fair, unbiased random sample of a fixed size k from a stream that might stop after 100 items or after 100 million? Reservoir sampling (Algorithm R) answers this with a surprisingly simple rule: fill a reservoir of size k with the first k items; for every item after that, at position i (counting the very first item as position 0), generate a random integer j between 0 and i inclusive, and if j < k, replace the reservoir slot at index j with the new item — otherwise discard the new item.

Tracing this through a 5-item stream (A, B, C, D, E) with a reservoir of size k = 2:

Fill:     reservoir = [A, B]                     (positions 0, 1)

i = 2 (item C): draw j in {0,1,2}. Say j = 1 (< 2) -> replace slot 1
                reservoir = [A, C]

i = 3 (item D): draw j in {0,1,2,3}. Say j = 3 (not < 2) -> discard D
                reservoir = [A, C]

i = 4 (item E): draw j in {0,1,2,3,4}. Say j = 0 (< 2) -> replace slot 0
                reservoir = [E, C]

The algorithm never needed to know the stream would stop at 5 items, and never stored more than k items plus whichever new item just arrived. The guarantee this algorithm provides is precise and checkable: every item that has passed through the stream has exactly a k/n probability of being in the final reservoir, where n is the total stream length. Verifying this for item A in the trace above: A survives only if it is never selected for replacement at steps i = 2, 3, 4. At each step i ≥ k, the probability that a replacement event lands specifically on A's current slot is 1/(i+1), so the probability A survives step i is i/(i+1):

P(A survives) = (2/3) × (3/4) × (4/5)
              = (2×3×4) / (3×4×5)
              = 24 / 60
              = 0.4  =  2/5  =  k/n

The middle terms cancel exactly (a telescoping product), leaving k/n — confirming the algorithm's guarantee holds precisely for this example, not just approximately. This is the actual mechanism behind "keep a representative sample of the data seen so far" for a stream whose length is never known in advance.

Detecting Concept Drift

A model trained once on historical data can quietly become wrong as the stream's underlying pattern shifts over time — a phenomenon called concept drift. A simple, illustrative version of drift detection compares a recent window's statistics against an established baseline: suppose a fraud model's baseline, built from the first 1,000 transactions, shows an average transaction amount of $45. If the most recent window of 100 transactions shows an average of $210 — more than four times the baseline — that shift itself is a signal worth investigating, independent of whether any single transaction was individually flagged as an outlier. Formal algorithms built on this same basic idea, such as DDM (Drift Detection Method), which monitors a classifier's error rate for a statistically significant increase, and ADWIN (Adaptive Windowing), which maintains a variable-size window and shrinks it automatically when it detects the older and newer portions no longer look like they come from the same distribution, are the production-grade versions of this comparison — precise enough to distinguish a genuine shift from ordinary random fluctuation, which a naive fixed threshold like the one above cannot reliably do on its own. Once drift is detected, the usual response is retraining the model on recent data, discarding the assumption that the pattern learned last month still holds today.

Ensemble Methods Applied to Streams

Combining multiple models to improve reliability — covered in full depth in the lesson on bagging and boosting — applies to streams with one added twist: because the stream never stops, an ensemble used for stream mining typically retires and replaces its weakest-performing member model periodically, rather than training a fixed ensemble once and using it forever. This is a direct consequence of concept drift: a model that was one of the strongest members last week can become the weakest once the underlying pattern shifts, so streaming ensembles are evaluated and pruned continuously rather than trained once.

Where This Fits Among the Rest of This Series

The application areas most associated with stream mining — real-time fraud detection, network intrusion detection, IoT sensor monitoring — are covered with their own worked examples in the lesson on data mining applications and the lesson on ubiquitous data mining; what distinguishes this lesson is the specific machinery (bounded windows, reservoir sampling, drift detection) that real-time analysis actually depends on, rather than a second pass through the same application list.

0 Comments

Reviewed before they appear

No comments yet.

Data Mining
Introduction to Data Mining Data Mining Techniques Data Mining Implementation Process Data Mining Architecture KDD: Knowledge Discovery in Databases History of Data Mining Data Mining Tools Data Mining vs. Machine Learning Facebook Data Mining Social Media Data Mining Methods Clustering in Data Mining Text Data Mining Bagging vs Boosting Data Mining vs Data Warehousing Social Media Data Mining Data Mining: Bayesian Classifiers Data Mining: World Wide Web Different Types of Clustering Bitcoin Mining and Blockchain Data Mining Orange Data Mining Data Mining vs Big Data Decision Tree Induction Educational Data Mining Data Mining in Healthcare Apriori Algorithm Data Integration in Data Mining Difference Between Data Mining and Text Mining Discretization in Data Mining Redundancy and Correlation in Data Mining Classification of Data Mining Systems Data Mining Models Difference Between Data Mining and Data Science Difference Between Data Mining and Statistics Difference Between Data Mining and Web Mining Difference Between Data Mining and Data Analysis Difference Between Business Intelligence and Data Mining Difference Between Data Mining and Data Visualization Data Mining vs Data Analytics Types of Data Mining Difference Between Data Profiling and Data Mining Predictive Analytics vs Data Mining Difference Between Data Mining and OLAP Descriptive and Predictive Data Mining Difference Between Spatial and Temporal Data Mining Difference Between Classification and Clustering in Data Min Hierarchical Clustering in Data Mining Density-Based Clustering in Data Mining What Is Aggregation in Data Mining? Regression in Data Mining What Is an Outlier in Data Mining? Data Cleaning in Data Mining Data Processing in Data Mining Classification and Prediction in Data Mining Data Mining Task Primitives Web Content Mining, Web Structure Mining, and Web Usage Mini Binning in Data Mining KDD vs. Data Mining Noise in Data Mining BIRCH in Data Mining Stemming in Data Mining Feature Transformation in Data Mining Visual and Audio Data Mining Class Comparison Methods in Data Mining Data Selection in Data Mining Tasks and Functionalities of Data Mining Ubiquitous and Invisible Data Mining Entity Identification Problem in Data Mining Numerosity Reduction in Data Mining Market Basket Analysis in Data Mining Multimedia Data Mining Correlation Analysis in Data Mining Data Mining Services Trends in Data Mining Data Harvesting vs Data Mining Data Mining vs Artificial Intelligence Data Mining vs Data Exploration Data Mining vs Process Mining Web Scraping vs Data Mining Data Wrangling Boosting in Data Mining What Is Forecasting in Data Mining? What Is CRISP in Data Mining? FP-Growth Algorithm in Data Mining Weka Data Mining Association Rule Mining in Data Mining Characteristics of Data Mining Classification by Backpropagation in Data Mining Data Mining Applications Challenges of Data Mining What "Data Mining" Actually Means Data Mining Operators Data Mining Query Language (DMQL) Data Preprocessing Techniques in Data Mining Data Stream Mining Grid-Based Methods in Data Mining Categories of Functions in Data Mining Interestingness of Patterns in Data Mining Strategic Value of Data Mining Data Mining for Business Intelligence Data Mining Projects Evaluation of Clustering in Data Mining Major Issues in Data Mining Partition Algorithm in Data Mining Partitioning Methods in Data Mining Rule-Based Classification in Data Mining Types of Attributes in Data Mining Use of Data Mining What is Association in Data Mining? What is the Goal of Data Mining? Data Mining Algorithms Data Mining: Concepts and Techniques Data Mining Examples The Data Mining Process: From Raw Data to Deployed Model Normalization in Data Mining Preprocessing in Data Mining: Data Quality and Feature Selec Association Analysis in Data Mining Attribute Selection Measures in Data Mining Support and Confidence in Data Mining Tree Pruning in Data Mining Classification Algorithms in Data Mining Data Generalization in Data Mining Importance of Data Mining Data Quality in Data Mining Mining Frequent Patterns in Data Mining Data Warehouse and OLAP Technology for Data Mining Need for Data Mining Pattern Evaluation Methods in Data Mining Logarithms and Exponents in Complexity Analysis Time Series Clustering What is the C4.5 Algorithm and How Does It Work? Expanding Contractions in Text Mining Cosine Similarity in Data Mining Lazy Learning in Data Mining Neural Networks in Data Mining Building a Text Normalizer Shallow Parsing Data Pipeline Orchestration Big Data vs Small Data Myths of Data Mining Data Reduction in Data Mining
Ask about this post
AI Ask about this post

Ask questions about Data Stream Mining and get answers drawn from it.

Signed-in readers only.