Curve fitting — where it appears
Named by 7 essays across 7 fields — each of them below, with the objects they name alongside it.
Fitting a class to measurements
A complexity class is normally read off the shape of the loops and written down. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is granted a class only if the fit holds — which turns a statement about code into a statement that can fail.
Two parameters, one bound, no order
With one size parameter the candidate classes are ordered — n beats n log n beats n², always, and comparing two bounds is reading them. With two, E log V and V² have no order at all, and which one is smaller is a property of the graph. Sweeping V at fixed degree and at fixed density are different experiments, and the same algorithm fits different classes in the two.
The cells are not the cost
This field opened by pricing a dynamic program in subproblems — 29,737 calls became 56 cells and the class changed. That is right when a cell is cheap. A table over intervals has 8,385 cells and considers 349,504 transitions to fill them, and the cubic in its bound is inside the cell rather than in the table.
The cheap tail and the expensive merge
A summary whose tolerance tightens towards the tail keeps seven times the tuples of a plain one on a single pass, and after merging sixty-four shards it keeps three and a half times as many. The error function that buys a useful tail promise is also the one that pays most for never having the values in one place.
A floor with two variables in it
Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.
The tuples a merge does not give back
A merge of thirty-two quantile summaries keeps seven times the tuples of one summary over the same values, and sixty-four keeps ten and a half. Fitted across the sweep the count goes as the shard number to the power 0.56, which answers what it converges to — it does not.
The floor a merge does not settle at
Compute a fold's level floors from the shard histograms and the prediction over-shoots by 1.73. A merged summary's floor is not the floor a summary settles at on the same arrivals — it is 0.90 of it at four shards and 0.70 at sixty-four, straight in log₂ m at a 3% residual, because merging preserves the heavy counters and never runs their eviction cascade.
Named alongside it
The objects these essays reach for when they reach for this one.
ShardHonest limitMerge treeMergeable summaryPartitionComplexity classFixed pointGreenwald–KhannaGuaranteeHistogramMeasurementQuantile summary