Weighted Random Sampling over Data Streams

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.

Corrected minor typos. Infeasible items are now additionally called "overweight" items (WRS-N-P). Enriched the Introduction (Section 1) with more text and references to related work. Revised the description of sampling with a bounded number of replacements (Section 4.2)

Cited by in corpus (3)

• Learning Fine-grained Image Similarity with Deep Ranking
• Incremental Skip-gram Model with Negative Sampling
• Weighted Sampling Without Replacement from Data Streams