Flajolet–Martin, AMS moments, DGIM, decaying windows, real-time analytics platforms and two case studies.
This chapter completes Unit III. It covers algorithms that summarise a stream in very little memory — counting distinct elements, estimating moments, counting ones in a window and decaying windows — and then real-time analytics platforms and two case studies. Each section includes a step-by-step numerical example.
8.1 Counting distinct elements in a stream – Flajolet–Martin
The count-distinct problem asks how many different elements have appeared in a stream — for example, the number of unique visitors to a website in a month — without storing every element seen. The Flajolet–Martin (FM) algorithm answers it approximately with very little memory. Each element a is hashed to a bit string h(a), and the tail length r(a), the number of trailing zeros in h(a), is computed. The algorithm keeps only R, the largest tail length seen so far, and estimates the number of distinct elements as 2^R. The idea is that a hash value ends in r zeros with probability 2^(−r), so seeing a tail of length R suggests that about 2^R different values have been hashed. Repeated occurrences of the same element hash to the same value, so duplicates never change R. A single estimate is very rough, so in practice many hash functions are used: their estimates are divided into groups, the average is taken within each group, and the median of the group averages is the final answer.
Worked example. Stream: 1, 3, 2, 1, 2, 3, 4, 3, 1, 2, 3, 1. Hash function h(x) = (6x + 1) mod 5.
| x | h(x) | Binary | Trailing zeros r |
|---|---|---|---|
| 1 | (6 + 1) mod 5 = 2 | 010 | 1 |
| 2 | (12 + 1) mod 5 = 3 | 011 | 0 |
| 3 | (18 + 1) mod 5 = 4 | 100 | 2 |
| 4 | (24 + 1) mod 5 = 0 | 000 | 0 (by convention) |
- The largest tail length is R = 2 (from element 3).
- Estimate = 2^R = 2² = 4 distinct elements.
- The true number of distinct elements is 4 ({1, 2, 3, 4}), so the estimate is exact here; on larger streams it is close on average.
8.2 Estimating moments – Alon–Matias–Szegedy
If element i appears mᵢ times in a stream, the k-th frequency moment is the sum over all distinct elements of (mᵢ)^k. The 0th moment is the number of distinct elements (estimated by FM); the 1st moment is the length of the stream; and the 2nd moment, Σ mᵢ², called the surprise number, measures how uneven the distribution is — it is large when a few elements dominate. The Alon–Matias–Szegedy (AMS) algorithm estimates the 2nd moment with little memory. It picks several random positions in the stream; for each position it creates a variable X recording the element found there and a count X.value that starts at 1 and increases by 1 each time that element appears again later. Each variable gives the estimate n × (2 · X.value − 1), where n is the stream length, and the final answer averages these estimates (or takes the median of group averages). For infinite streams, the positions are maintained by reservoir sampling so that they stay uniformly spread as n grows.
Worked example. Stream: a, b, c, b, d, a, c, d, a, b, d, c, a, a, b (n = 15).
- True counts: a = 5, b = 4, c = 3, d = 3. True 2nd moment = 5² + 4² + 3² + 3² = 25 + 16 + 9 + 9 = 59.
- Choose positions 3, 8 and 13. Position 3 holds c, which appears at positions 3, 7 and 12, so X₁.value = 3. Position 8 holds d, at positions 8 and 11, so X₂.value = 2. Position 13 holds a, at positions 13 and 14, so X₃.value = 2.
- Estimates: 15 × (2 × 3 − 1) = 15 × 5 = 75; 15 × (2 × 2 − 1) = 45; 15 × (2 × 2 − 1) = 45.
- Average = (75 + 45 + 45) / 3 = 55, close to the true value 59. More variables give a more accurate estimate.
8.3 Counting ones in a window – DGIM algorithm
The DGIM algorithm (Datar, Gionis, Indyk and Motwani) answers the question "how many 1s are in the last N bits of a binary stream?" using only O(log² N) bits of memory instead of N. It divides the window into buckets, each recording two things: the timestamp of its most recent 1, and its size — the number of 1s it contains. The buckets obey four rules: (1) the right end of every bucket is a 1; (2) every bucket size is a power of 2; (3) there are one or two buckets of each size; and (4) sizes never decrease as we move back in time, and buckets do not overlap. When a new 1 arrives, a new bucket of size 1 is created; if there are now three buckets of size 1, the two oldest are merged into one bucket of size 2, which may in turn cause a merge of size-2 buckets, and so on. Buckets whose timestamp falls outside the window are dropped. To estimate the count, add the sizes of all buckets except the oldest, and add half the size of the oldest bucket, because only part of it may lie in the window. The error is at most 50%, and it can be reduced by allowing more buckets of each size.
Worked example 1 – estimating the count. The buckets in the window, from newest to oldest, have sizes 1, 1, 2, 4, 4, 8.
- Sum of all except the oldest = 1 + 1 + 2 + 4 + 4 = 12.
- Half of the oldest = 8 / 2 = 4.
- Estimate = 12 + 4 = 16 ones. The true value lies between 12 + 1 = 13 and 12 + 8 = 20, so the error is bounded.
Worked example 2 – updating when a 1 arrives.
- Before: 1, 1, 2, 4, 4, 8. A new 1 arrives, giving 1, 1, 1, 2, 4, 4, 8 — three buckets of size 1.
- Merge the two oldest size-1 buckets into a size-2 bucket: 1, 2, 2, 4, 4, 8.
- There are now two buckets of size 2, which is allowed, so no further merging is needed.
Read more on the blog: DGIM Algorithm · DGIM Live Visualizer.
8.4 Decaying window
A sliding window treats every element inside it equally and forgets older elements completely. A decaying window (exponentially decaying window) instead gives every element a weight that shrinks smoothly with age, so recent elements matter most but history is not cut off abruptly. For a stream a₁, a₂, …, aₜ and a small constant c (for example 10⁻⁶), the decayed sum at time t is:
The sum is very cheap to maintain: when a new element arrives, multiply the current sum by (1 − c) and add the new element. A common application is finding the most popular items — trending movies, hashtags or products. A score is kept for each item: on each arrival, every score is multiplied by (1 − c), 1 is added to the score of the item that arrived, and any item whose score falls below a threshold (for example ½) is dropped. Because the total of all scores can never exceed 1/c, the number of items with a score of at least ½ is at most 2/c, so memory stays bounded.
Worked example. Use c = 0.1 (a large value, so the effect is visible). The stream of movie views is A, B, A, A, B.
| Time | Arrival | Score of A | Score of B |
|---|---|---|---|
| 1 | A | 0 × 0.9 + 1 = 1.000 | 0 |
| 2 | B | 1 × 0.9 = 0.900 | 0 × 0.9 + 1 = 1.000 |
| 3 | A | 0.9 × 0.9 + 1 = 1.810 | 1 × 0.9 = 0.900 |
| 4 | A | 1.81 × 0.9 + 1 = 2.629 | 0.9 × 0.9 = 0.810 |
| 5 | B | 2.629 × 0.9 = 2.366 | 0.81 × 0.9 + 1 = 1.729 |
After five views, A is the most popular (2.366). Plain counts would give A = 3 and B = 2; the decayed scores also reflect that B's views are more recent.
Practice: Question Set – Decaying Window.
8.5 Real-time Analytics Platform (RTAP) applications
A Real-time Analytics Platform (RTAP) collects, processes and analyses data as it is generated and delivers results within milliseconds to seconds, so that action can be taken while it still matters. A typical RTAP has layers for ingestion (Kafka, Flume or Kinesis receive events), stream processing (Storm, Flink or Spark Streaming filter, aggregate and join them), fast storage (Cassandra, Redis or HBase hold recent state), analytics and model scoring (machine-learning models score each event), and delivery (dashboards, alerts and automated actions). Platforms include Apache Storm, Apache Flink, Spark Streaming, Amazon Kinesis, Google Cloud Dataflow, IBM Streams and Azure Stream Analytics.
| Domain | RTAP application |
|---|---|
| Banking | Card-fraud detection while the transaction is in progress |
| E-commerce | Real-time recommendations and dynamic pricing |
| Telecom | Network monitoring, call-drop alerts |
| Healthcare | ICU patient-vital monitoring and early warning |
| Transport | Live traffic routing, ride-hailing demand matching |
| Manufacturing / IoT | Predictive maintenance from sensor streams |
| Social media | Trending topics, real-time sentiment |
| Cyber security | Intrusion detection from network logs |
Worked example – a latency budget for card-fraud detection. The bank must approve or decline a card payment within 300 ms of the swipe.
- Ingestion through Kafka: 20 ms.
- Stream processing (look up the card's recent activity in Redis, compute features such as spend in the last hour): 60 ms.
- Model scoring: 30 ms.
- Decision and response to the payment terminal: 90 ms.
- Total = 20 + 60 + 30 + 90 = 200 ms, leaving 300 − 200 = 100 ms of headroom. A batch system that scored transactions every hour could never stop a fraudulent payment before it completed.
8.6 Case studies – real-time sentiment analysis and stock market prediction
Case study 1 – Real-time sentiment analysis. A company wants to know, minute by minute, how the public feels about a product launch. Posts mentioning the product or its hashtags are streamed from the social-media API into Kafka. Each post is cleaned (URLs, stop words and punctuation removed, emojis converted to words, text tokenised and lemmatised) and classified as positive, negative or neutral, either with a sentiment lexicon such as VADER or with a trained model such as Naïve Bayes, an SVM or a transformer. Counts are aggregated over one-minute tumbling windows or a decaying window, trending words are tracked, and a live dashboard shows the result. An alert fires when negative sentiment rises sharply, so that the support team can respond while the issue is still small.
Worked example. In a normal minute, 1,200 posts arrive: 300 positive, 600 neutral and 300 negative, so the negative share is 300 / 1,200 = 25% and the net sentiment is (300 − 300) / 1,200 = 0. The alert threshold is a negative share above 40%. In the next minute, 1,200 posts include 540 negative: 540 / 1,200 = 45% > 40%, so an alert is raised. The top new words in negative posts are "battery" and "overheating", which tells the team exactly what to investigate.
Case study 2 – Stock market prediction. A trading system predicts short-term price movements from a live stream of price and volume ticks, combined with news and social-media feeds. Over sliding windows it computes features such as moving averages, the relative strength index (RSI), volatility, volume changes and news sentiment. A model — a time-series model such as ARIMA or GARCH, or a machine-learning model such as a random forest or LSTM network — scores each new window and generates buy, sell or hold signals, which algorithmic trading systems can act on within milliseconds. Because markets change constantly (concept drift), models are retrained often. Markets are noisy and partly random, so predictions are probabilities, not certainties, and must be combined with risk controls.
Worked example – a moving-average crossover signal. The last five closing prices are ₹100, ₹102, ₹101, ₹104 and ₹106.
- 5-day simple moving average (SMA₅) = (100 + 102 + 101 + 104 + 106) / 5 = 513 / 5 = ₹102.6.
- The 20-day SMA, computed the same way over 20 days, is ₹101.0.
- Yesterday SMA₅ was ₹100.8, below SMA₂₀; today SMA₅ (102.6) is above SMA₂₀ (101.0). The short-term average has crossed above the long-term one — a buy signal ("golden cross").
- The latest daily return = (106 − 104) / 104 = 1.92%. The system would place the order only if its risk model also allows it.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.