Weighted Random Sampling over Data Streams

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

paper · pdf · doi:10.48550/arxiv.1012.0256

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