Neural Sync Active

Streaming Algorithms

Registry Synced

Streaming Algorithms

133 words

1 min read

Reading compass

Now · 9.1 Reservoir Sampling

Streaming Algorithms

9.1 Reservoir Sampling

Sample

k

elements uniformly from a stream of unknown length:


python
import numpy as np
def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = np.random.randint(0, i+1)
            if j < k:
                reservoir[j] = item
    return reservoir

9.2 Count-Distinct (HyperLogLog)

Estimate the number of distinct elements using

O(\log \log n)

space. Idea: Hash each element, track the longest run of leading zeros. If the max run is

R

, estimate

n \approx 2^R

9.3 Heavy Hitters (Misra-Gries)

Find all elements that occur more than

n/k

times using

O(k)

space. Algorithm: Maintain

k-1

counters. For each element, increment if tracked, else decrement all. Elements with positive counters at end are heavy hitter candidates. Join Discord PreviousFrequency EstimationNextHyperLogLog