tag

#sampling

4 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Floyd Sampling

Floyd Sampling Floyd Sampling selects $k$ distinct integers uniformly from the range $0$ to $n - 1$. It avoids building and shuffling the full range, so it is useful when $k$ is much smaller than $n$. The algorithm inserts one value per iteration into a set. Each insertion preserves uniformity over all subsets of the processed range. Problem Given integers $n$ and $k$ with: $$ 0 \le k \le n...
algorithms sampling randomized sets
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 ›

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 ›

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