tag

#approximate

4 pages tagged

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 ›

Sample Sort Selection

Sample Sort Selection Sample Sort Selection uses random sampling to approximate the position of the k-th element, then narrows the search to a smaller subarray. The idea is to avoid full partitioning of the entire array by first estimating where the target lies. Problem Given an array $A$ of length $n$ and an index $k$, find the k-th smallest element. Algorithm Take a random sample, sort it, and use it...
algorithms selection sampling approximate
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