Arbitrary-query sketch correction #
Correct the rank of an arbitrary query using the actual significant-bit sketch and the two stored keys neighboring its inclusive sketch rank. Exact hits return that rank directly; other queries use a second sketch rank at a prefix boundary. No word-RAM running-time bound is asserted.
Main definitions #
upperRank,lowerRank: inclusive and strict ranks in a finite sequence.bestSketchNeighbor: select between indicest-1andtat inclusive sketch rankt.correctedRank: the resulting arbitrary-query correction.
Main results #
highestDiff_mem_relevantBits_of_lt: every stored pair's highest differing bit is selected.exists_sketchNeighbor_prefix: every nonempty query-prefix block contains a sketch neighbor.exists_sketchNeighbor_min_highestDiff: a sketch neighbor attains a globally longest prefix.correctedRank_eq_upperRank: correction gives the true inclusive rank for every bounded query.
References #
See [FW93] and [MIT 6.851, Spring 2021, Lecture 12, handwritten page 4] (https://courses.csail.mit.edu/6.851/spring21/lectures/L12.pdf).
Every pair of distinct stored keys has its highest differing bit among the adjacent-pair bits, even when the keys are not adjacent.
A query sharing the larger stored key's prefix lies strictly above every sketch of a smaller stored key outside that prefix block.
A query sharing the smaller stored key's prefix lies strictly below every sketch of a larger stored key outside that prefix block.
Every nonempty full-prefix block contains an immediate sketch neighbor of the query. The query is arbitrary: it need not be a stored key or have a faithful sketch rank.
For a query unequal to every stored key, an immediate sketch neighbor attains the longest full common prefix, expressed as the minimum highest differing position.
Minimizing over the at most two sketch neighbors therefore minimizes over every key.
Every key sharing the query's prefix above the globally minimum differing bit differs from the query at that bit. Thus none follows the query's branch there.
If the query takes the one branch at its first divergence from a longest-prefix key, the true inclusive comparison equals the inclusive sketch comparison at the lower boundary.
If the query takes the zero branch at its first divergence from a longest-prefix key, the true inclusive comparison equals the strict sketch comparison at the upper boundary.
The corrected sketch rank equals the true inclusive rank when j minimizes divergence
among the immediate sketch neighbors. This hypothesis is a comparison of at most two keys.
The inclusive rank of a stored key is its index plus one.
An exact hit has its true inclusive rank already, before correction.
The predecessor is precisely index t-1, using the inclusive convention.
The successor is precisely index t, using the inclusive convention.
The two optional candidates are exactly the immediate sketch neighbors.
A chosen candidate belongs to the input pair and has minimum score among that pair.
Exact hits score zero; other keys are scored by their highest differing bit plus one.
Instances For
The selected neighbor minimizes the divergence score among the two candidates.
A nonempty node always has at least one of the two sketch neighbors.
An exact stored hit is the predecessor of the inclusive sketch cut.
If the selected candidate is not an exact hit, then no stored key is an exact hit. Only the two neighboring candidates are inspected by the selection function.
Away from exact hits, the two-candidate selector minimizes the highest differing bit.
Arbitrary-query correction using two sketch neighbors. Exact hits return the initial inclusive sketch rank directly. Otherwise a second sketch rank uses the appropriate boundary. After taking sketch ranks, candidate selection and correction use at most two full-key values. The sketches and rank primitives here are mathematical specifications, without a RAM-time bound.
Instances For
For every bounded query, correction of the actual significant-bit sketch gives the true inclusive rank among the stored keys. This includes empty nodes, boundary cuts, and exact hits.