Synthetic lookup / no device measurements

Duplicate lookup coverage: four synthetic cases

A fixed five-chunk query illustrates missed duplicates with no shared hooks or a one-manifest budget, compared with complete membership.

JSON, inputs and hashes / Model code / Research explanation

Method

Use older manifest [4,5,6], newer manifest [8,9,10] and query [4,5,8,9,11], with 4096 bytes per chunk. Choose hooks using ID modulo sampleModulo = 0. Repeatedly select the manifest covering most uncovered query hooks, breaking ties toward the later manifest, until the budget or positive scores run out. Count exact query matches in selected manifests. Compare with a complete set-membership baseline. All four existing duplicates are the missed-fraction denominator.

Five distinct 4 KiB query chunks: four already stored and one new. 1 KiB = 1024 bytes. A dash means not applicable, not zero cost.

Reproduce

The dependency-free Node.js module includes the inputs and prints the same CSV. The JSON records SHA-256 hashes and artifact generation time, not an observation date.

node --input-type=module -e 'import { toCsv } from "./dedup-lookup.mjs"; process.stdout.write(toCsv())'

Limits

• Hand-picked integer identities are synthetic, not real fingerprints or sampled backup data.
• This is a reduced candidate-selection illustration, not a replication or implementation of a complete sparse-indexing system.
• No hash collisions, chunking, within-query duplicate IDs, cache, index retention, persistence, compression, placement, timing or failure model.
• Loaded manifests are logical selections, not device-read counts. The full-membership baseline has no modeled I/O cost.
• Missed duplicates consume additional payload storage; the model does not merge different IDs or test corruption.
• Deterministic cases have no sampling uncertainty, confidence interval or observation period; no efficiency estimate for a real workload.

Column definitions

scenario

Synthetic case name; all four cases use the same fixed query and stored manifests.

sampleModulo

Hook predicate: chunk ID modulo this integer equals zero. Blank for the full-membership baseline; not an empirical sampling rate.

maxChampions

Maximum selected manifests. Blank for the full-membership baseline.

queryHooks

Number of qualifying query IDs, including any not found in stored manifests. Blank for the baseline.

loadedManifests

Number of selected manifests examined; not measured I/O. Blank for baseline because its lookup cost is unspecified.

knownDuplicateChunks

Incoming distinct chunks already present in any stored manifest, the denominator of missedDuplicateFraction.

foundDuplicateChunks

Existing query chunks found in examined manifests, or in the complete membership set for baseline.

missedDuplicateChunks

Existing query chunks outside the selected manifests.

newlyStoredChunks

Query chunks not found by lookup, including genuinely new chunks and missed duplicates.

storedBytes

Newly stored payload bytes at 4096 bytes per chunk, excluding metadata, compression and replicas.

missedDuplicateFraction

Missed existing chunks / known existing chunks, dimensionless. Blank when that denominator is zero.

Sources and license

CC0-1.0 for Hesela's original implementation and synthetic rows. Cited papers retain their own rights.

1. Lillibridge et al. Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality. USENIX FAST 2009, pp. 111-123. (accessed 2026-10-19)
2. Zhu, Li and Patterson. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System. USENIX FAST 2008, pp. 269-282. (accessed 2026-10-19)

Related: sparse indexing, deduplication and the separate restore-locality trace.