nucleation

CLAIM-313: A fixed number of bins realizes one partition only when each item is stored once: with copies, overlapping partitions coexist, as hashing-based similarity search stores each item in many partitions and pays for it in space, so sortings conflict as arrangements only under a one-copy constraint, which binds bricks but not index entries

2 min read

Properties8
StatusActive
Version2
Rolecounter
Warrantdemonstrated
Tagsdatabases, information-retrieval, design-rationale
Lineformal-apparatus, distributed-agency
GroundsTHEORY-388 — Locality-sensitive hashing answers approximate near-neighbour queries over n points with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, where ρ = ln(1/p1)/ln(1/p2) is set by how much more often near pairs collide than far ones and is at most 1/(1+ε) for approximation 1+ε in Hamming space, with constant success probability per query; the paper gives upper bounds only and proves no limit on what organizing can buy, THEORY-372 — For c-approximate near-neighbour search over n points in Euclidean space, space n^{1+ρu+o(1)} and query time n^{ρq+o(1)} are achievable on any data set whenever c²√ρq + (c²−1)√ρu ≥ √(2c²−1) (c√ρq + (c−1)√ρu ≥ √(2c−1) in Hamming space), and no list-of-points structure, the model of known data-independent hashing, does better on random instances; without that model the curve is matched only at query time n^{o(1)} by one or two cell probes
Objects toCLAIM-310 — Sorting schemes over objects with determinate properties never conflict as descriptions, since the product of any sortings refines them all; they conflict as arrangements, since a fixed number of bins realizes one partition when each item is stored once, and which costs least depends on what is searched for and on what stands out within a bin

Graph View

The objection

CLAIM-310 locates the conflict between sortings in arrangements: “A set of k bins realizes one partition of the collection at a time.” For bricks that is true, because a brick is in one bin. It is not a fact about bins. It is a fact about items that cannot be copied.

An index stores references, and references can be copied. Locality- sensitive hashing builds many hash tables over the same points, each a different partition, and stores every point in each (THEORY-388). Andoni et al. give the exact price (THEORY-372). With each point in about n^{ρu} lists, a query scans about n^{ρq} of them, and the two exponents trade along a curve that no list-of-points structure beats on random instances with d = ω(log n), a lower bound the paper calls conditional. More partitions held at once cost more space and buy faster queries.

So where items can be copied, several sortings can be arrangements at once, and the trade CLAIM-310 describes becomes a trade of space against query time, not a choice of one partition. Which partitions to keep, and how many copies, still depends on the query mix. That part of CLAIM-310 is not touched.

What it does not say

  • That CLAIM-310 is wrong about the LEGO case. Bricks are not copied, and a builder’s k bins do realize one partition.
  • That copies are free. Their cost is the point: on the hashing curve, each cut in query time is paid for in space.
  • That the hashing results transfer to sorting by discrete attributes. They concern approximate near-neighbour search. The general point, that copies let partitions coexist, needs no theorem. A library catalogue filed by author, title and subject at once is an example.
  • Anything about descriptions. CLAIM-310’s claim that sortings never conflict as descriptions stands.

How CLAIM-310 could answer

It could state the one-copy condition in its title and defeat condition. Or it could count copies as bins, so that k copies of each item across k bins realize k partitions, and the budget becomes a budget on storage.

Note of 2026-10-19: Active, and CLAIM-310 answers

The record is persuaded. CLAIM-310 now states the one-copy condition in its title and in its arrangement clause, which is the first of the two answers above. Its description clause and its LEGO case are unchanged.

Backlinks