Palantir: Hierarchical Similarity Detection for Post-Deduplication Delta Compression

Backup systems already delete identical blocks with deduplication, but blocks that differ by a few bytes slip through — delta compression could store just the difference against a similar block, yet finding that similar block cheaply forces a single similarity threshold that is either too strict (missing good matches) or too loose (picking bad ones); this work from City University of Hong Kong, Huawei, and Mainz builds Palantir, which groups the same features into several tiers of thresholds and searches most-similar-first, adds a cheap filter that drops matches that would not actually help, and expires stale metadata so the extra bookkeeping stays constant, lifting overall backup compression by 7.3 percent.

Why this problem is worth solving

The technique at the center of this paper is the one that catches what deduplication cannot.

The machinery that makes the matchmaking affordable is also where the difficulty hides.

What people did before, and where it broke

• N-Transform super-features, the standard method. Compute several transforms of a rolling hash over the block, take each transform’s minimum as a feature, bundle the features into a fixed number of super-features, and take the first block that shares one. Where it broke. It uses one fixed threshold, so it is tuned for accuracy and misses a large fraction of still-useful near-matches — a low coverage that leaves compression on the table.
• Finesse, tuned for speed. Replace the global minimum of many hash functions with minimum hashes taken from different regions of the block, which is cheaper to compute. Where it broke. It is faster but detects even fewer similar blocks, so Palantir finds far more base blocks and compresses about 26.5 percent better than it.
• Odess, tuned for lighter computation. Content-defined sampling first reduces the block to a small representative sample, then runs the super-feature algorithm only on that sample, cutting the hashing cost with almost no loss of matching quality. Where it broke. It is still one fixed threshold, so it inherits exactly the same accuracy-versus-coverage dilemma as the original.
• Locality-based systems (MeGA, Dare). Exploit the fact that near-matches cluster in adjacent backup versions, restricting the super-feature search to recent or neighboring blocks to save time and space. Where it broke. This narrows where you look, economically, but does nothing about how good the matching itself is — it is orthogonal to the single-threshold problem, not a fix for it.
• The gap. Every approach commits to one similarity threshold and then chooses a base block first-fit, so none can both widen the net to catch more candidates and still discriminate the good matches from the weak ones. A brute-force search that delta-encodes against everything compresses far better, and the whole field sat well short of it — waiting for a method that could raise coverage without letting bad matches drag the result back down.

How Palantir works

The idea

Build many thresholds out of one set of features, and search them from strict to loose. The whole dilemma of prior systems comes from committing to a single similarity threshold — one bundling of features into super-features — which forces a choice between catching too few near-matches and admitting too many weak ones. Palantir’s first move is to refuse the choice. It takes the very same twelve raw features and bundles them several different ways at once, producing a strict tier, a middle tier, and a loose tier, each with its own threshold, at no cost in extra feature computation. Then it searches them in order, strictest first, so the closest base block is always preferred and the looser tiers only come into play when the strict one finds nothing — coverage climbs steeply while accuracy is protected. Meeting an accuracy-versus-reach trade-off by running several thresholds side by side and adapting which one governs, instead of hard-wiring one, is the same instinct the out-of-core random-walk work covered elsewhere on this site follows when it switches between coarse and fine-grained reads according to how the workload is spread, refusing to fix a single granularity for the whole run.

Replace an impossibly expensive exactness check with a cheap running estimate. Widening the net raises a new danger: some of the extra matches are false positives, base blocks so weakly similar that delta-encoding against them does not shrink the output at all, and can even grow it once metadata is counted. The exact test — recompute the whole dataset’s compression with and without each delta — is hopelessly costly, because lossless compressors work over large buffers holding tens of blocks, and a single change ripples across them. Palantir’s second move is to estimate instead of compute: it compares each delta block’s own compression ratio against a running average of the recent lossless ratios, and drops the match if it falls short. This costs only the compression of the one delta block, yet lands within about one percent of an optimal filter that runs many times slower. Trading a prohibitively expensive global computation for a cheap local proxy that is provably close to it is the same reframing the scalable hardware-invariant-learning work covered elsewhere on this site makes, replacing one giant intractable check with many small ones whose answers compose into nearly the same guarantee.

Keep only the metadata that still earns its space. Three tiers of super-features cost roughly four times the bookkeeping of one, and left unchecked that overhead grows with every backup generation until it swamps the savings. Palantir’s third move rests on two facts about backups: the lower, bulkier tiers contribute the least to compression because their matches are the weakest, and near-matches overwhelmingly cluster in recent versions because each backup is a small edit of the last. So it gives each tier a lifespan — the strict tier lives forever, the middle tier for a few versions, the loose tier for only a couple — and expires the rest, turning a metadata cost that grew without bound into a flat constant. Refusing to pay to store bookkeeping that no longer buys anything is the same economy the SSD-deduplication work covered elsewhere on this site drives at when it stops a dedup layer from redundantly maintaining a mapping table the drive already keeps for itself.

Following the reasoning through Palantir

The strict setting is deliberately picky to avoid weak matches, but that same pickiness makes it blind to a great many genuinely useful ones.

Why it works

• Several thresholds from one feature set catch what a single threshold cannot. A fixed super-feature setting either rejects good near-matches or admits bad ones → but grouping the very same twelve features three different ways yields three thresholds side by side → so a block missed by the strict tier is still caught by a looser one, without computing a single extra feature.
• Searching strict-tier-first keeps accuracy while the loose tiers add reach. Simply lowering the threshold would find more blocks but often pick a weak one → but querying the highest-similarity tier before the lower ones takes the closest available base block first → so coverage climbs from about a third to over ninety percent of 65-percent-similar blocks with the best match still preferred.
• A cheap false-positive filter converts the extra coverage into real savings. Looser tiers inevitably surface matches whose delta does not actually shrink the output → but comparing each delta block against a running average of recent compression ratios flags the useless ones for pennies → so the weak matches are dropped and only the genuinely helpful ones survive, landing within about one percent of an optimal filter that runs far slower.
• Judging against the dataset’s own recent ratio adapts the filter automatically. Whether a weak match helps depends on how compressible the data already is → but using the trailing lossless-compression average as the bar lets the threshold self-tune per dataset → so the same filter is aggressive on highly compressible backups and lenient on poorly compressible ones, with no manual tuning.
• Expiring the bulky low tiers bounds the metadata blow-up to a constant. Three tiers of super-features would otherwise pile up and over-double the bookkeeping as versions accumulate → but keeping the strict tier forever, the middle tier for five versions, and the loose tier for two exploits that near-matches cluster in recent versions → so the extra metadata settles from 133 percent down to a steady 32 percent within about ten backups.

What it costs (trade-offs and scope)

• The gains are real but modest and dataset-dependent. The end-to-end compression improvement is 7.3 percent on average over the best baseline, but only 1.1 percent on the highly compressible Linux repository, and even at its best Palantir remains about 17.8 percent short of what a brute-force search achieves. It moves the needle, but it does not close the gap to optimal.
• Throughput drops, and some stages get much heavier. Palantir is about 7.7 percent slower than Odess overall, with the hashing and writing stages each taking about 3.5 times as long; the pipeline hides most of this, but the deduplication stage slows under the added compute and memory pressure. The authors call the cost acceptable for backup and note that a latency-sensitive system might prefer the traditional pipeline.
• The two ideas do not both fire on every dataset. On highly compressible data the tiered super-features contribute almost nothing and all the benefit comes from the false-positive filter; on other datasets the reverse. The headline number blends cases where only one of the two mechanisms is doing the work.
• Even optimized, the metadata is not free. The lifecycle manager cuts the extra bookkeeping to a constant, but that constant is still about 32 percent more than a single-tier system stores; without the manager it is 133 percent and climbing.
• The false-positive filter is a heuristic. An optimal greedy filter compresses about one percent better end-to-end, but runs some 84 percent slower, so Palantir trades a sliver of ratio for speed. On a dataset whose compressibility swings sharply, the running-average estimate could misjudge individual matches.
• Per-match delta quality actually falls. Because Palantir deliberately accepts lower-similarity base blocks, its average delta efficiency per matched block is lower than the baselines; the win comes from wider coverage times careful filtering, not from sharper individual deltas.
• Duplicate handling adds bookkeeping subtlety. Expiring super-features means a later duplicate of an already-expired block must re-add its super-features to the newest version and delete the stale copy, so the system needs careful lifecycle logic to avoid losing the ability to delta-encode against such blocks.

The evaluation

Check yourself

Sources

The paper is “Palantir: Hierarchical Similarity Detection for Post-Deduplication Delta Compression” by Hongming Huang, Peng Wang, Qiang Su, Hong Xu, Chun Jason Xue, and Andre Brinkmann, published at ASPLOS 2024, pages 830 to 843, DOI 10.1145/3620665.3640353. The authors are at City University of Hong Kong, Huawei Technologies, The Chinese University of Hong Kong, the Mohamed bin Zayed University of Artificial Intelligence, and Johannes Gutenberg University Mainz.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the introduction and background on the three-layer backup reduction pipeline (deduplication, delta compression, lossless compression) and on super-features derived from Broder’s theorem, including the N-Transform, Finesse, and Odess baselines and the accuracy-versus-coverage dilemma of a single fixed grouping; the motivation showing the gap to a brute-force optimal on DB_Stock and the matching-probability curves for different feature groupings; the design section presenting hierarchical super-features with default tiers of three-by-four, four-by-three, and six-by-two searched strictest-first, the adaptive false-positive filter that compares a delta block against a running average of recent lossless ratios, and the version-based metadata lifecycle manager that keeps the strict tier for all versions, the middle tier for five, and the loose tier for two; the four-stage pipeline implementation (FastCDC chunking, SHA1 fingerprints with 64-bit sampled super-features, deduplication and delta and ZSTD compression, and metadata writing); and the evaluation on six datasets reporting the 7.3 percent and 26.5 percent end-to-end improvements, 27.4 percent more base blocks, the 9.3 percent delta-stage gain, the 7.7 percent throughput cost with the 3.5-times heavier hashing and writing stages, the false-positive filter within one percent of an optimal greedy filter that runs 84 percent slower, and the metadata overhead falling from 133 percent to a constant 32 percent within about ten backup versions.