tag

#streaming

15 pages tagged

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.25 Case Studies

5.25 Case Studies Problem You need to see how hash-based structures behave in complete systems rather than isolated operations. Real performance and correctness issues usually appear only when hashing interacts with full workflows: streaming data, graphs, caches, and distributed systems. This section consolidates patterns from previous recipes into concrete end-to-end designs. Case Study 1: Frequency Analysis Pipeline You need to compute frequencies over a large stream of events. Design Use...
algorithms hashing case-studies systems streaming May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.13 Count-Min Sketch

5.13 Count-Min Sketch Problem You need approximate frequency counts for a large stream of keys, and an exact counting map would use too much memory. A counting map stores one entry per distinct key. This is exact, but memory grows with the number of distinct keys. In a large log stream, network trace, search query stream, or telemetry pipeline, the number of distinct keys may be too large to store...
algorithms hashing probabilistic data-structures streaming May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Top K

Streaming Top K Streaming Top K maintains the largest $k$ elements of a data stream. The input does not need to fit in memory, and the algorithm can update the answer after each new value. The standard method keeps a min heap of size $k$. The smallest value in the heap is the current cutoff for membership in the top $k$. Problem Given a stream of values $$ x_1, x_2,...
algorithms selection streaming top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Space Saving

Space Saving Algorithm Space Saving tracks frequent items in a stream using a fixed number of counters, similar to Misra Gries, but with better accuracy in practice. It maintains estimates for item frequencies and guarantees bounded error. Unlike Misra Gries, it does not decrement all counters. Instead, it replaces the smallest counter when needed. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ maintain approximate counts for the most...
algorithms streaming heavy-hitters approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Quantile Summary

Quantile Summary Quantile Summary maintains approximate quantiles of a stream using bounded memory. Instead of storing all values, it stores a compressed representation that allows queries such as median, percentiles, and rank estimates. The goal is to answer queries of the form: $$ \text{find } x \text{ such that } rank(x) \approx \phi n $$ for a given quantile $\phi \in (0,1)$. Problem Given a stream $$ x_1, x_2, \dots,...
algorithms streaming quantiles approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Heavy Hitters

Streaming Heavy Hitters Streaming Heavy Hitters finds items that occur frequently in a stream. The stream may be too large to store, so the algorithm keeps only a compact summary. The usual goal is to report all values whose frequency is above a threshold, or to estimate the most frequent values. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ find items whose frequency is large compared with $n$....
algorithms selection streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Stream Sort by Buffer

Stream Sort by Buffer Stream sort by buffer sorts incoming data in memory-sized batches. It reads a fixed number of elements, sorts that buffer, emits the sorted block, and repeats. You use it when the full input is too large or too delayed to sort all at once. Problem Given a stream of values and a buffer capacity ( B ), produce sorted chunks or sorted runs from the stream....
algorithms sorting streaming buffer external-memory
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Largest in Stream

Kth Largest in Stream Kth Largest in Stream maintains the k-th largest value of all values seen so far. It uses a min heap of size $k$. The heap stores the current top $k$ values. The smallest value in that heap is the k-th largest value overall. Problem Given a stream of values $$ x_1, x_2, \dots, x_n $$ support two operations: add(x): insert a new value query(): return the...
algorithms selection streaming heap
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Sliding Window Sort

Sliding Window Sort Sliding window sort maintains the elements inside a fixed-size moving window in sorted order. As each new element arrives, the oldest element leaves and the new element enters. You use it when sorted queries are needed over recent data, not over the full stream. Problem Given a stream ( x_1, x_2, \dots ) and a window size ( w ), maintain a sorted view of the active...
algorithms sorting streaming sliding-window online
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Weighted Reservoir Sampling

Weighted Reservoir Sampling Weighted Reservoir Sampling selects a random sample from a stream where each item has a weight. Higher weight items should be more likely to appear in the sample. A common method assigns each item a random priority derived from its weight, then keeps the $k$ items with the largest priorities. Problem Given a stream of weighted items: $$ (x_1, w_1), (x_2, w_2), \dots, (x_n, w_n) $$ where...
algorithms sampling streaming weighted randomized
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Greenwald Khanna Quantile

Greenwald Khanna Quantile Greenwald Khanna Quantile is a deterministic streaming algorithm for approximate quantile queries. It stores a compact ordered summary of the stream and guarantees that returned values have rank error at most $\epsilon n$. The algorithm is useful when the stream is too large to store but percentile queries must remain accurate. Problem Given a stream: $$ x_1, x_2, \dots, x_n $$ support quantile queries: query(phi): return an...
algorithms streaming quantiles greenwald-khanna
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Median Maintenance

Median Maintenance by Two Heaps Median Maintenance keeps track of the median as values arrive one by one. It uses two heaps to maintain a balanced partition of the data. A max heap stores the lower half A min heap stores the upper half The median is derived from the roots of these heaps. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ after each insertion, report the median...
algorithms streaming median heaps
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Misra Gries

Misra Gries Misra Gries is a deterministic streaming algorithm for finding frequent items with bounded memory. It keeps at most $k - 1$ counters and returns a small candidate set that contains every item whose frequency is greater than $n/k$. The algorithm may return extra candidates. A second pass gives exact frequencies and removes false positives. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ and an integer $k...
algorithms streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Count Min Sketch Query

Count Min Sketch Query Count Min Sketch is a probabilistic data structure for estimating item frequencies in a stream. It stores counts in a small two dimensional table and uses several hash functions to update and query the table. It gives approximate answers with one-sided error: the estimated count is never below the true count, but it may be above it because of hash collisions. Problem Given a stream $$...
algorithms streaming frequency count-min-sketch approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Reservoir Sampling

Reservoir Sampling Reservoir Sampling selects a uniform random sample from a stream without knowing the stream length in advance. It keeps only a fixed-size reservoir and updates it as new items arrive. The simplest version keeps one item. The general version keeps $k$ items. Problem Given a stream: $$ x_1, x_2, \dots, x_n $$ choose $k$ items uniformly at random from the stream, using only: $$ O(k) $$ memory. Algorithm...
algorithms sampling streaming randomized