Weighted Random Sampling over Data Streams

2010/12/01 by Pavlos S. Efraimidis, Efraimidis, Pavlos S. · 3 citations
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Stream Mining Techniques #cs.DS

paper · pdf · doi:10.48550/arxiv.1012.0256

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)

arxiv created 2015/07/28 · arxiv updated 2015/07/29

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.

Cited by

• Incremental Skip-gram Model with Negative Sampling
• Enhancing Foveated Rendering with Weighted Reservoir Sampling
• Learning Fine-grained Image Similarity with Deep Ranking

Related

• Weighted Reservoir Sampling With Replacement from Data Streams
• Weighted Reservoir Sampling from Distributed Streams
• Weighted Sampling Without Replacement from Data Streams
• An asymptotically optimal, online algorithm for weighted random sampling with replacement
• Communication-Efficient (Weighted) Reservoir Sampling from Fully Distributed Data Streams