The pass that runs the other way

The pass that was never a parameter made the number of passes a dial, on the grounds that a prohibition cannot be swept and a parameter can. It left a second thing fixed and unnamed: every one of those passes runs forwards.

So does every pass in the streaming literature’s lower bounds. The phrase that appears in them is p-pass, not p-forward-pass, which reads as though the direction were not a choice.

The question the direction trivialises #

The sliding-window model asks for an answer about the last $W$ arrivals, and the summary that has to forget established why that is hard: a counter has no record of which of its increments are old, so an exact answer needs the arrivals themselves.

Forwards, the difficulty is precisely stated. When an item arrives, the algorithm does not know whether it will still be in the window when the question is asked, so it must keep it — or accept the error a bounded structure gives. The ring buffer is the whole structure, and the stamps are what make expiry decidable.

Backwards, the last $W$ arrivals are the first $W$ items read. An algorithm reading from the end takes $W$ items, counts them, and stops. No expiry, no stamps, no approximation, and no bound to prove.

The stamps are the clearest part of it. Knowing when something arrived is only necessary for an algorithm that met it before it knew whether it mattered. Read from the end and every item met is in the window by construction, so there is nothing to date.

The saving is exactly n over W #

The read ratio is not an empirical finding and the figure asserts it rather than fitting it: a backward pass reads exactly $W$ and a forward pass reads exactly $n$, so the ratio is $n/W$ and nothing else.

That shape is worth reading, because it says where the trick is worth having. The saving is large when the window is a small fraction of the stream — a five-minute window over a day’s log — and vanishes when the window approaches the whole stream. A question about most of the data is a question a backward pass cannot answer more cheaply, because it has to read most of the data.

What it costs: one seek, and the strict model #

Two costs, and the second is the honest limit of the whole idea.

A seek. Starting at the end rather than the beginning is a jump, and the machinery here counts it. One seek is cheap on anything with an index — a file, a log segment, a column chunk — and charging for it is what stops read it backwards from becoming read it in any order at all, which is a model in which nothing is hard and nothing is interesting.

And a stream, in the strict sense, does not permit one. This is the real boundary. If the data is arriving now, over a socket, and cannot be stored, then there is no end to start from and the backward algorithm does not exist. Every bound in the sliding-window model is correct and unavoidable in that setting.

The setting where it is avoidable is the one where most of these structures are actually run: over data at rest. A log file, a partition on disk, a day of records in a column store — all of them permit a backward read, and the sliding-window structures get deployed against all of them, with their bounds quoted, because the bounds came with the structure.

The structure is right and its precondition has been left behind.

Why the state differs too, and not only the reads #

The read count is the striking number and the state is the more interesting one, because it says what the stamps were for.

A forward algorithm holding the window exactly holds $W$ keys and $W$ stamps — 4,096 of each at thirteen bits per stamp, 184,320 bits in total. The stamps are not decoration: the structure has to decide, on each arrival, which stored item has now left, and the only way to know is to have written down when each arrived.

The backward algorithm holds a counter per distinct key among the $W$ it read — 792 of them on this stream — and no stamps at all. Every item it has seen is in the window, so there is no expiry decision and nothing to date.

Two savings are tangled there and they are worth separating. The stamps go because expiry goes, which is a direct consequence of the direction. The 4,096 keys become 792 counters because counting is a summary and a ring buffer is not — a forward algorithm could also hold counts rather than the ring if it were willing to give up exactness, and the summary that has to forget is the essay about what that costs.

So the direction buys the first saving outright and merely enables the second. That distinction matters because the first is unavailable to any forward algorithm at any price, and the second is a trade a forward algorithm can also make.

The mirror, which is drawn as often #

A family that only showed the win would be arguing rather than measuring, so here is the same question about the other end of the stream.

Reading from the end answers the suffix question in 4,096 reads and the prefix question in 40,000. Reading from the start does exactly the reverse.

There is no direction that is better. There is a direction that suits a question, and the sliding-window model’s difficulty is that the question it asks and the direction a stream permits are the mismatched pair. That is a sharper statement than backward passes are powerful, and it is the one the measurement supports.

It also says what to look for. A problem whose bound is proved by an adversary who controls the order of arrivals is a problem whose bound may be an artefact of the order; a problem whose bound is about the contents is not. The window problem is entirely about order — the same multiset in a different order has a different answer — which is why it is the one direction rescues.

The machinery, and why it refuses things #

Making direction a dial meant making the stream object take one, and the object refuses two things on purpose.

It refuses a third pass where two were allowed, in either direction, which is the enforcement the pass that was never a parameter introduced and which stops an algorithm quietly taking a read it was not given.

And it refuses a direction that is not a direction — an algorithm asking to read sideways gets an error rather than a default. That sounds like a joke assertion and it is not: the alternative to two directions is a general permutation, and a model that permits arbitrary access order is a model in which the sliding-window problem is trivial and so is everything else. Two directions is a deliberate restriction, and the refusal is what keeps it one.

The comparison harness refuses a third thing. It runs both directions and requires the answers to be identical, key for key and count for count, throwing if they are not. They are answers to the same question; a difference between them is a bug in one of the implementations, not a finding about direction, and drawing it as a finding is the failure this collection is most careful about.

Passes traded against direction #

There is a second separation, and it is cleaner because it is stated in the currency this collection already charges.

Ask for the longest suffix of a stream of costs whose total is within a budget. Backwards it is one pass in constant state: accumulate from the end, stop when the total passes the budget. Forwards, the answer’s starting point is not known until the stream’s total is, so it takes two passes — one for the total, one to find the earliest cut — carrying a single number between them.

One backward pass, or two forward passes and a carry. That is the sharpest form of the claim, because a bound saying two passes are needed is a bound about forwards and does not say so.

The reads differ too, and in a way the passes do not capture: the forward route reads $2n$ at every budget, because the first pass must reach the end before the total is known. The backward route reads only as far as the budget takes it — 40 items at a budget of 2,000 and 2,042 at a budget of 100,000.

What this does to the bounds already on this site #

Three of this collection’s own results acquire a precondition, and it is worth stating rather than leaving for a reader to notice.

A floor one pass cannot get under proves a space lower bound for a one-pass algorithm. The proof is a counting argument over the states a machine can be in after reading a prefix, and the word prefix is where the direction lives. Read backwards, the same argument applies to suffixes, and the problems it bounds are different problems.

The floor under a window bounds the space of any structure answering a windowed query. Same shape: the adversary’s power comes from choosing what arrives next, and an algorithm reading from the end has already seen what arrives next.

What a second pass buys shows a second pass turning a superset into an exact answer at the cost of the carry. That result is direction-blind — the second pass verifies candidates and it does not matter which end it starts from — and it is the useful control: not everything about passes is about direction, and the two resources are genuinely separate.

None of the three is wrong. Each is a statement about a model whose access pattern is fixed by a word that does not appear in it, and the useful move is to write the word down.

Where a backward read is actually available #

It is worth being concrete about which systems have the option, because the answer is more than expected and the reason is that the streaming model gets adopted by analogy.

A log file has it. Reading the tail of a file backwards is what every log viewer does, and the last five minutes of a log is a suffix.

A partitioned object store has it. Objects are written in time order and named accordingly, so the last hour is the last few objects and they can be fetched in any order.

A column store has it. Values are stored in row order within a chunk and chunks are ordered; scanning the last chunk first costs one metadata lookup.

A Kafka-style log has it, on replay. Live consumption is a strict stream; replay from a retained offset is not, and the offsets are exactly a seek.

A socket does not. Nor does a sensor, a network tap, or anything arriving now and not stored.

The pattern is that the strict model applies at the point of ingest and almost nowhere downstream, and the structures written for the strict model are used at every stage because they came with a reputation. A windowed structure at the ingest is correct engineering; the same structure over yesterday’s partition is a structure solving a problem that partition does not pose.

The identity also says where the option stops being decisive, which is worth knowing before it is reached for. A window that is a large fraction of the stream leaves a backward pass reading most of the stream anyway, and the whole of the advantage was that it did not have to. At the last point of that sweep the backward route reads 16,384 items against the forward route’s 40,000 — two and a half times fewer rather than a hundred and fifty-six times fewer — and a factor of two and a half is the sort of number an implementation detail can eat.

The rule worth keeping #

A lower bound in the streaming model is a bound about an access pattern, and the pattern is a precondition rather than a law. Check whether the data permits another one before quoting the bound.

Three questions decide it, and all three are answerable before any code is written:

• Is the data at rest? If yes, the strict streaming model is a choice rather than a constraint.
• Is the question about a suffix? If yes, a backward read makes it trivial and no structure is needed at all.
• Is the bound proved by an adversary who controls the order? If yes, it is a candidate for being an artefact of the direction.

A system answering yes to all three is running a sliding-window structure to solve a problem it does not have.

A note on what was actually built #

The dial is small and it is worth saying what it consists of, because the point of building it was that the alternative was an argument.

A stream object that allows $p$ passes now takes a direction per pass and returns a generator rather than an array iterator, so an algorithm that stops early is charged for what it took rather than for what it could have taken. Reads are counted, seeks are counted, and both are reported beside the passes.

That is the whole change: about forty lines, one of which is the check that a direction is one of the two. What it buys is that forwards stopped being an assumption and became a value in a call, which is the same move the pass that was never a parameter made for the pass count and the model, made a parameter made for the cost model.

The pattern is worth naming because it keeps working: when a result seems to depend on something the statement does not mention, make the thing a parameter and sweep it. The sweep either shows the result was robust — which is worth knowing — or shows the missing precondition, which is worth more.

The saving is about recency, not about windows #

The identity is stated as $n/W$ and read as the saving is large when the window is a small fraction of the stream. That is right for the two windows measured and it is not the general statement, because both of them are at an end.

Take a window of $W$ arrivals starting at position $a$. A forward pass must reach $a + W$ before it can stop; a backward pass must reach back to $a$, which is $n - a$ items. So the better of the two reads

$$\min(a + W,\; n - a),$$

and the choice is simply read from the nearer end.

Evaluate the extremes. At $a = n - W$ the window is the suffix and the backward pass reads $W$: the $n/W$ this page measures. At $a = 0$ it is the prefix and the forward pass reads $W$: the mirror plate. And at $a = (n-W)/2$ — the window in the middle — both routes read about $n/2$, so the better direction saves a factor of two and no more, at any window length.

That is a materially narrower claim than the one the sweep supports on its own. The enormous saving is not a property of windows being small; it is a property of the window being adjacent to an end, and the length only decides how large the saving is once adjacency is granted.

Which relocates what the trick is for. The last five minutes is a suffix and gets $n/W$ — a hundred and fifty-six times at the finest window drawn here. The five minutes around three o’clock yesterday is the same window length in the same stream and gets a factor of two, because half the data lies on each side of it whichever way the read runs.

So the useful summary is that direction buys recency, and recency is exactly what the sliding-window model asks about. The model’s question is the last $W$, never the $W$ around some instant, and that is the coincidence the whole result rests on: the one question the strict streaming model insists on is the one question a backward read makes trivial.

It also adds a fourth entry to the criterion this page offers. A bound is a candidate for being a direction artefact when the question depends on arrival order and the part of the stream it depends on abuts an end. The first condition alone is not enough: a mid-stream window is thoroughly order-dependent — permute the arrivals and the answer changes — and a backward read is worth a factor of two on it, which is a constant and not a model difference.

That sharpens the three questions above by one. Is the data at rest, is the bound about order, and now is the region of interest at an end — and the third is the one that separates a structure that can be deleted from a structure that can be run half as long. The summary that has to forget is about the first case and has no counterpart for the second, which is the honest gap: nothing here measures a mid-stream window, and the factor of two above is arithmetic rather than a plate.

What is not established #

One problem, measured both ways. Exact heavy hitters over a suffix, and the suffix-budget problem. Two problems are not a theory of which questions direction helps with, and the criterion offered above — that the bound is about order rather than contents — is a conjecture supported by two cases and a control.

Seeks are counted and not priced. One seek is charged and its cost in any real storage system is not modelled. On a medium where a seek costs more than reading the stream, everything above inverts, and this collection’s own one access, eight kilobytes is the field in which that arithmetic gets done.

And no lower bound is proved here. That reading backwards is easier for these problems is demonstrated by exhibiting an algorithm. That reading forwards is necessarily harder is the existing literature’s claim and is not re-derived — what is shown is that the claim’s model has a parameter in it that its statement does not mention.