Academic CS in Production Code

Weighted Random Sampling over Data Streams

Pavlos S. Efraimidis
2010
2 references

Abstract

In this work, we present a comprehensive treatment of weighted random sampling (WRS) over data streams. More precisely, we examine two natural interpretations of the item weights, describe an existing algorithm for each case ([2, 4]), discuss sampling with and without replacement and show adaptations of the algorithms for several WRS problems and evolving data streams.

View Paper PDF
💾 Databases
2 repositories
2 references

Code References

â–¶ ClickHouse/ClickHouse
1 file
â–¶ src/Common/WeightedRandomSampling.h
1
/// The implementation uses the A-ES method from the paper https://arxiv.org/pdf/1012.0256
â–¶ cockroachdb/cockroach
1 file
â–¶ pkg/kv/kvserver/split/weighted_finder.go
1
// https://arxiv.org/pdf/1012.0256.pdf.
Link copied to clipboard!