# sublinear algorithms

Published articles for sublinear algorithms.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Hashing to Estimate the Size of a Stream

DevFeed: [Hashing to Estimate the Size of a Stream](<https://devfeed.tech/articles/hashing-to-estimate-the-size-of-a-stream-40394.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2016/01/04/hashing-to-estimate-the-size-of-a-stream/>)

Published: 2016-01-04T09:00:37Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [hashing](<https://devfeed.tech/topics/hashing.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [data](<https://devfeed.tech/topics/data.md>), [Python](<https://devfeed.tech/topics/python.md>), [parallel](<https://devfeed.tech/topics/parallel.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [data](<https://devfeed.tech/tags/data.md>), [hashing](<https://devfeed.tech/tags/hashing.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [sublinear-algorithms](<https://devfeed.tech/tags/sublinear-algorithms.md>)

### AI overview

This article explains how random hash functions can estimate the number of distinct items in a data stream that is too large to fit in memory. It presents a Python implementation using minimum hash values and parallel hashes to reduce variance, and states approximation guarantees for the estimate.

### Source excerpt

Problem: Estimate the number of distinct items in a data stream that is too large to fit in memory. Solution: (in python) import random def randomHash(modulus): a, b = random.randint(0,modulus-1), random.randint(0,modulus-1) def f(x): return (a*x + b) % modulus return f def average(L): return sum(L) / len(L) def numDistinctElements(stream, numParallelHashes=10): modulus = 2**20 hashes = [randomHash(modulus) for _ in range(numParallelHashes)] minima = [modulus] * numParallelHashes currentEstimate = 0 for i in stream: hashValues = [h(i) for h in hashes] for i, newValue in enumerate(hashValues): if newValue < minima[i]: minima[i] = newValue currentEstimate = modulus / average(minima) yield currentEstimate Discussion: The technique used here is to use random hash functions.