# On sampling from data with duplicate records

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2020.

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

- [UpLIF: An Updatable Self-Tuning Learned Index Framework](https://mlsanity.com/paper/2408.04113/) (2024)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)

## Abstract (arXiv)

Data deduplication is the task of detecting records in a database that correspond to the same real-world entity. Our goal is to develop a procedure that samples uniformly from the set of entities present in the database in the presence of duplicates. We accomplish this by a two-stage process. In the first step, we estimate the frequencies of all the entities in the database. In the second step, we use rejection sampling to obtain a (approximately) uniform sample from the set of entities. However, efficiently estimating the frequency of all the entities is a non-trivial task and not attainable in the general case. Hence, we consider various natural properties of the data under which such frequency estimation (and consequently uniform sampling) is possible. Under each of those assumptions, we provide sampling algorithms and give proofs of the complexity (both statistical and computational) of our approach. We complement our study by conducting extensive experiments on both real and synthetic datasets.