# Distinct Sampling on Streaming Data with Near-Duplicates

arXiv: https://arxiv.org/abs/1810.12388 · HTML: https://mlsanity.com/paper/1810.12388/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2018.

## Built on by (most cited first, 1 of 1)

- [MaxSketch: Robust Distinct Counting in Streams via Random Projections](https://mlsanity.com/paper/2605.15571/) (2026)

## Abstract (arXiv)

In this paper we study how to perform distinct sampling in the streaming model where data contain near-duplicates. The goal of distinct sampling is to return a distinct element uniformly at random from the universe of elements, given that all the near-duplicates are treated as the same element. We also extend the result to the sliding window cases in which we are only interested in the most recent items. We present algorithms with provable theoretical guarantees for datasets in the Euclidean space, and also verify their effectiveness via an extensive set of experiments.