Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Reservoir_sampling> ?p ?o. }
Showing items 1 to 26 of
26
with 100 items per page.
- Reservoir_sampling abstract "Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory. The most common example was labelled Algorithm R by Jeffrey Vitter in his paper on the subject.This simple O(n) algorithm as described in the Dictionary of Algorithms and Data Structures consists of the following steps (assuming that the arrays are one-based, and that the number of items to select, k, is smaller than the size of the source array, S):array R[k]; // resultinteger i, j;// fill the reservoir arrayfor each i in 1 to k do R[i] := S[i]done;// replace elements with gradually decreasing probabilityfor each i in k+1 to length(S) do j := random(1, i); // important: inclusive range if j <= k then R[j] := S[i] fidoneThe algorithm creates a "reservoir" array of size k and populates it with the first k items of S. It then iterates through the remaining elements of S until S is exhausted. At the ith element of S, the algorithm generates a random number j between 1 and i. If j is less than k, the jth element of the reservoir array is replaced with the ith element of S. In effect, for all i, the ith element of S is chosen to be included in the reservoir with probability k/i. Similarly, at each iteration the jth element of the reservoir array is chosen to be replaced with probability 1/k * k/i, which simplifies to 1/i. It can be shown that when the algorithm has finished executing, each item in S has equal probability (i.e. k/length(S)) of being chosen for the reservoir.".
- Reservoir_sampling wikiPageID "25190127".
- Reservoir_sampling wikiPageRevisionID "604303240".
- Reservoir_sampling hasPhotoCollection Reservoir_sampling.
- Reservoir_sampling subject Category:Algorithms.
- Reservoir_sampling subject Category:Analysis_of_algorithms.
- Reservoir_sampling subject Category:Probabilistic_complexity_theory.
- Reservoir_sampling type Abstraction100002137.
- Reservoir_sampling type Act100030358.
- Reservoir_sampling type Activity100407535.
- Reservoir_sampling type Algorithm105847438.
- Reservoir_sampling type Algorithms.
- Reservoir_sampling type Event100029378.
- Reservoir_sampling type Procedure101023820.
- Reservoir_sampling type PsychologicalFeature100023100.
- Reservoir_sampling type Rule105846932.
- Reservoir_sampling type YagoPermanentlyLocatedEntity.
- Reservoir_sampling comment "Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory.".
- Reservoir_sampling label "Reservoir sampling".
- Reservoir_sampling label "水塘抽樣".
- Reservoir_sampling sameAs m.09g7w75.
- Reservoir_sampling sameAs Q7315334.
- Reservoir_sampling sameAs Q7315334.
- Reservoir_sampling sameAs Reservoir_sampling.
- Reservoir_sampling wasDerivedFrom Reservoir_sampling?oldid=604303240.
- Reservoir_sampling isPrimaryTopicOf Reservoir_sampling.