nucleation

CLAIM-311: A search cut off before an exhaustive pass can establish absence when the arrangement certifies that the unsearched remainder cannot hold the item: a sorted table answers non-membership in a logarithmic number of probes, and the Threshold Algorithm stops early with its answer proved, so absence needs a certificate about the remainder, not exhaustion; similarity search in high dimension is where no such certificate exists

3 min read

Properties8
StatusActive
Rolecounter
Warrantdemonstrated
Tagslogic, databases, information-retrieval
Linedistributed-agency
GroundsTHEORY-340 — For answering membership in a static set of n keys with the fewest worst-case cell reads, sorted order with binary search is optimal only when the key universe exceeds a Ramsey-number threshold and table cells may hold nothing but stored keys or pointer symbols; it is beaten for small universes, and by two probes once one cell may hold an encoded value, THEORY-363 — For finding the top k objects under a monotone combining function from m lists each sorted by one attribute, with sorted and random accesses the only costs, the threshold algorithm is correct and on every database costs at most a constant times what any correct algorithm that makes no wild guesses costs; the constant is m + m(m−1)c_R/c_S, no deterministic algorithm does better when the function is strict, and once wild guesses are allowed no algorithm has such a guarantee on databases with ties, THEORY-366 — With a fixed number of data points and a query drawn independently of them, if the variance of the p-th power of the query-to-point distance divided by its mean tends to zero, the farthest point comes within any factor 1 + ε of the nearest with probability tending to one; independent coordinates meet this condition, while data on a low-dimensional subspace, or queries that fall inside well-separated clusters, escape it, THEORY-369 — Under uniformly distributed, independent data and queries in the unit cube with Euclidean distance and a fixed number of points, an optimal nearest-neighbour search over any index that partitions points into blocks or convex clusters of at least two points must read a fraction of blocks that grows toward all of them as dimension rises; with a five-fold sequential advantage for scanning, estimates put the crossover at about 15–26 dimensions for rectangular and spherical bounding regions, and two tree indexes measured on 50,000 points lost to a scan beyond about 10
SupportsCLAIM-312 — "If I can't find it, it isn't there" asserts operational unavailability, that the item will not be put to use before the deadline, not absence: a search that fails by the deadline establishes unavailability outright, and licenses absence only with a certificate that the unsearched remainder cannot hold the item, from exhaustion, from an invariant of the arrangement, or from a closed-world default
Objects toCLAIM-306 — Under a deadline, search can establish presence by finding one item but absence only by exhausting the collection, so "If I can't find it, it isn't there" acts on an unfinished search as negation as failure acts on a finished one: a default stronger than either the closed-world assumption or negation as failure, safe only when the arrangement makes the full search finish within the deadline

Graph View

The objection

CLAIM-306 holds that “absent” is shown “only by a pass that rules out every place it could be”, and is defeated by “a search procedure, under a deadline shorter than an exhaustive pass, whose failure to find an item licenses its absence with no assumption that the unsearched part would also have failed”.

Two of the record’s readings supply such procedures.

  • A sorted table. Membership in a static sorted set is decided by binary search, and a failed search is a proof of non-membership: the order guarantees that every unexamined key lies on the wrong side of the probes already made. Yao’s question was only when this is the cheapest scheme (THEORY-340); that it is correct for absence was never in doubt.
  • The Threshold Algorithm. Over lists each sorted by one attribute, it stops as soon as the k-th best grade seen reaches the threshold formed from the last grades read under sorted access. Nothing unread can beat that threshold, so the answer is proved without reading the rest, and on every database it costs at most a constant times any correct algorithm that makes no wild guesses (THEORY-363).

In both, the unsearched part is not assumed to fail. It is shown unable to hold the item, by an invariant of the arrangement. So the asymmetry is not between one find and an exhaustive pass. It is between one find and a certificate about the remainder. Exhaustion is one certificate. Sorted order, an index and a labelled compartment are others, and they can be far cheaper.

Where CLAIM-306’s asymmetry stands

When the arrangement gives no bound on the remainder, a failed search certifies nothing short of exhaustion. That is the unsorted pile of CASE-094, and it is also, more surprisingly, similarity search in high dimension. Where the nearest and farthest neighbours become nearly equidistant (THEORY-366), the bounds a partitioning index uses to skip blocks prune almost nothing, and a correct search reads nearly every block (THEORY-369, under uniform data). “There is nothing like it here” then has no certificate cheaper than a scan, however the collection is organized.

What it does not say

  • That the medic’s search had a certificate. A cabinet of compartments searched by eye under stress has none of these invariants.
  • That every arrangement certifies absence. A sort certifies absence only for the attribute it is sorted on; a query on another attribute is back to a scan.
  • That the conceded claim was wrong about the medic. Its reading of CASE-085 as a decision to stop, not an inference, is kept by the restatement.

Backlinks