How to fit program footprint curves

A footprint is the volume of data accessed in a time window. A complete characterization requires summarizing all footprints in all execution windows. A concise summary is the footprint curve, which gives the average footprint in windows of different lengths. The footprint curve contains information from all footprints. It can be measured in time O(n) for a trace of length n, which is fast enough for most benchmarks.