Lodestar.Text 0.6.0. This page is frozen at that release. Read the current documentation for what main says now. A link to a decision or a migration page follows main, and leaves the archive.

A banded index over MinHash signatures: candidates without comparing every pair.

public sealed class LshIndex

Example — one band agreeing is enough to be a candidate.

using Lodestar.Text.Similarity;

var index = new LshIndex(new LshBanding(2, 2));
index.Add("stored", [1u, 2u, 3u, 4u]);

IReadOnlyList<string> found = index.Query([1u, 2u, 99u, 99u]);

int howMany = found.Count;  // => 1
int held = index.Count;  // => 1

Members — one page each.

Remarks — reference behaviour is datasketch 1.6.5's MinHashLSH. Two signatures are candidates when they agree on every slot of at least one band, which is what turns a quadratic scan into a lookup.

Query returns candidates, not matches. Scoring them with MinHash.Jaccard is the caller's next step, and LshBanding decides how often that step is wasted. An index that returned matches would have to hold every signature and compare them, which is the cost this exists to avoid.

A signature longer than the banding needs is accepted and its tail ignored, because Solve usually returns a banding consuming fewer slots than the length it was given.

Adding is not thread-safe; concurrent Query calls are.

Applies to — net10.0, netstandard2.0.

See also — LshBanding, MinHash, the set-similarity index.