Deep Nested LSH Explorer

Classical LSH bands signature rows with AND inside each band and OR across bands to sharpen the line between pairs judged similar and pairs judged dissimilar. Deep Nested LSH adds further alternating AND and OR levels and misclassifies fewer pairs than shallow banding at the same row budget.

Cascade explorer

Build a tree. Watch a pair of documents flow up it.

Preset

Target Jaccard t

Solve d1 for t

Cascade P(s) One level Ideal step at t FP area FN area Width W

Sharpest depth 2 in the same rows Flat reading

Pair similarity s

Depth k

Each faint curve is one level. AND levels set the FP tail. OR levels set the FN tail.

Trial seed

Terms used on this page

LSH: Locality sensitive hashing. It hashes documents so similar pairs likely collide and become candidates without comparing every pair.
The study: A search over trees by depth and row budget, scored on one generated corpus of 1000 documents. Most of its documents form clusters of near duplicates. The presets and their trees come from this search.
Jaccard similarity s: Shared shingles of two documents over all their shingles. A shingle here is a run of three consecutive words after lowercasing.
MinHash row: One hash value per document. Two documents agree on a row with probability s.
Signature length n: The number of MinHash rows a tree reads. It is the product of the arities.
Row budget: The largest n a tree may use. The presets compare trees within 1000 or 10000 rows.
Tuple d and depth k: d = (d0, d1, …) lists one arity per level. Depth k is the number of levels. n is the product of the arities.
Band: d0 rows joined by AND. It fires when the two documents agree on every one of its rows.
Arity dj: How many nodes of level j − 1 each node at level j combines. Level 0 combines rows.
AND level and OR level: An AND level fires only when every child fires. An OR level fires when any child fires.
Cascade reading: Odd levels OR their children and even levels AND them. Depth 2 is standard (r, b) banding.
(r, b) banding: Standard LSH with b bands of r rows each. As a tuple it is (r, b) with r = d0 and b = d1.
Flat reading: Every level above the bands ORs. It collapses to two-level banding (d0, n / d0).
Root and rung: The ladder holds one rung per level with the signature rows at the bottom and the root on top. Each rung sets its level's arity and shows the children of one node. The root is the single top node.
Rung labels Lj: L0 is the level of bands, L1 the level above it and so on up to the root. The AND or OR tag beside each label names that level's operation.
Hidden tile +k · j on: A rung draws only its first children. The last tile counts the k children not drawn and, after a run, the j of them that fired.
Candidate: A pair whose root fires. Only candidates go on to an exact check.
S curve P(s): The candidate probability curve. P(s) is the chance that a pair of similarity s becomes a candidate.
Per-level curves: Each faint curve traces one level over s. It is the curve the subtree up to that level follows. Hover or focus a rung to pick out its curve.
p gauges: The p value and bar on each rung give the chance that a node at that level fires at the current s. The rows rung shows s itself.
Target t: The Jaccard value meant to split pairs. Pairs at or above t should become candidates.
Ideal step: The perfect filter at t. It is 0 below t and 1 at or above t.
Threshold t̂: The s where the candidate probability P(s) crosses one half. The study solves d1 so t̂ lies within 0.01 of t.
Solve d1 for t: Solves one arity for the target t. At depth 1 it sets d0 to the value with the closest t̂. At depth 2 or more it solves d1 for t and tries the whole numbers on either side of that solution. It sets d1 to the sharpest of them whose t̂ lies within 0.01 of t, or to the one with the closer t̂ when neither does. When the solution falls below 1.5 or does not exist it leaves d1 unchanged. A tree whose t̂ lands more than 0.01 from t is flagged as unmatched.
Width W: The span of s over which P(s) climbs from 0.05 to 0.95. Smaller is sharper.
Sharpest: The smallest width W among the trees whose t̂ lies within 0.01 of t.
Error area E: The area between P(s) and the ideal step at t. The FP area lies left of t and the FN area right of it.
Depth 2 search skipped above 10 million rows: The error area card compares the tree with the sharpest depth 2 banding in the same rows. The page skips that search for trees above 10 million rows.
TP and TN: A true positive is a pair at or above t that becomes a candidate. A true negative is a pair below t that stays out.
FP and FN: A false positive is a pair below t that becomes a candidate. A false negative is a pair at or above t that does not.
f+ and f−: Tail exponents. f+ is the product of the AND arities with d0. f− is the product of the OR arities. f+ f− = n.
Measured slope: The local slope of a log-log tail at its far end, at s 10⁻⁶ for the FP tail and at 1 − s 10⁻⁶ for the FN tail. It approaches f+ and f−. The tail cards and the Measured caption show it.
Trial dots and Wilson interval: Run sends one random pair at s up the tree. 1000 at s and Sweep send 1000 random pairs at each s and plot a dot for the share that became candidates. Its bar is the 95% Wilson score interval for that share. The dots should sit on the curve.
Trial seed: Seeds the random pairs. Clear or a new seed drops the trial dots and restarts the pairs from the shown seed, so the same seed replays the same trials. It affects only the random trials.
At its own threshold: The preset sets t to the tree's own t̂.
Standard banding at 10000 rows: The study's best depth 2 (r, b) banding within 10000 rows at each target.
Sharpest tree per depth at 10000 rows: The sharpest tree at each depth from 2 to 5 within 10000 rows at each target.
Least error area beyond depth 5: Trees past depth 5 from the error area search at 1000 and 10000 rows. Each label names the search kind and the depth, such as two-tier 9D.
max-depth: The least error area tree at the deepest depth at which a tree matched to t fits the budget with every arity at least 2.
two-tier: The depth and the arities chosen together for the least error area.
all-2s: Every arity 2 with one 3 where it fits. A naive baseline with no threshold match.
Arity families at t 0.5: Trees at depths 3 to 5 near 10000 rows matched to t 0.5. The families differ in where the large arities sit.
head-heavy, even-weights and tail-heavy: Head-heavy puts the large arities at the low levels near the rows. Tail-heavy puts them at the high levels near the root. Even-weights keeps the arities as close to equal as the threshold allows.
Flat reading collapse (7, 23, 3) and (7, 69): Under the flat reading (7, 23, 3) collapses to the banding (7, 69). Switch on Flat reading to compare the two trees.