content-based-sampling · research · also Fingerprint-based sampling, Deduplication estimation

Content-based sampling (deduplication)

Content-based sampling selects blocks by a predicate on their content fingerprints so identical blocks share the same sampling decision.

Estimation: Scan every block fingerprint, retain selected distinct identities and scale their total bytes by the inverse selection probability. A small retained sample does not remove the initial full scan. Xie et al. use a modulo filter and adapt its selectivity as the sample grows. [1]

Units: For a fixed divisor M, unique payload is estimated as M times the selected distinct bytes. Variable-size blocks require byte weighting. The paper calls unique bytes divided by original bytes a deduplication ratio; a reduction factor uses the reciprocal, and saved fraction subtracts that share from one. [1]

Uncertainty: Accuracy relies on fingerprint uniformity, negligible collisions and enough selected distinct content. Taking a reciprocal of an unbiased unique-byte estimate does not make the reduction-factor estimate unbiased. A zero sample cannot establish that no unique data exists. [1] [2]

Worked example: For six equal blocks A,A,A,A,B,C, averaging the within-sample saved fraction over every two-position sample gives 20%, while the full population saves 50%. This demonstrates a naive extrapolation error, not a measured backup workload. [2]

Position sampling has another limit: different full populations can yield identical probability laws for a small sampled frequency histogram, despite different unique-byte totals. This concerns inference from sampled positions, not the full fingerprint scan used above. Hesela provides an exact two-position example and a three-position control. [3]

Relations

related
Deduplication ratio, Sparse indexing (deduplication), Sampling design, Duplication-frequency histogram

Citations

  1. Xie, Condict and Shete. Estimating Duplication by Content-based Sampling. USENIX ATC 2013, pp. 181-186. (accessed 2026-11-22)
  2. Hesela: exact occurrence-sampling and fixed-probability content-sampling examples, method and tests. (accessed 2026-11-22)
  3. Hesela: identical sample histogram laws, different deduplication savings; exact derivation and executable controls. (accessed 2026-11-22)
Sources & caveats
  • Primary-paper source review; the online system and reported performance were not reproduced. [1]
  • The exact example uses independent identity selection at fixed probability 1/2, not the paper's adaptive algorithm, a hash implementation or a confidence-interval estimator. [2]

JSON: /data/terms/content-based-sampling.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Content-based sampling (deduplication). Hesela. 2026-11-22. https://hesela.dev/terms/content-based-sampling/