13 Compression debt
On this page · Permalink · Source line 1514
Compression may postpone work rather than eliminate it. A later task may require reconstruction of material that was omitted from the current representation.
Definition 13.1: Future task model
Let \({\mathcal T}\) be a finite task set with probabilities \(p_t\ge0\) satisfying \(\sum_t p_t=1\). Let \(R_t\subseteq V\) be the node set required by task \(t\), and let \(c(v)\ge0\) be the recovery cost of node \(v\) when it is absent.
Definition 13.2: Expected compression debt
The expected compression debt of retained set \(K\) is
Proposition 13.3: Debt is monotone under retention
If \(K_1\subseteq K_2\), then
Proof
For every task \(t\), the missing set \(R_t\setminus K_2\) is contained in \(R_t\setminus K_1\). Recovery costs are nonnegative. The taskwise cost cannot increase, and neither can its probability-weighted sum.
Corollary 13.4: Irreversible compression accumulates debt
For a descending sequence of retained sets
the expected debt is nondecreasing.
A recovery archive can change the cost function. If an omitted node has a stable provenance pointer and a reproducible generator, its recovery cost may be small. If it survives only in memory, its recovery cost may be effectively infinite.