[VOTE] MinHash LSH scalar index format specification

[zhangyue19921010]

Formal vote on PR #9076.

This proposal adds the MinHash LSH scalar index to the Lance format: an approximate near-duplicate index over text columns that ranks rows by the estimated Jaccard similarity of their token shingles. The PR adds the MinHashLshIndexDetails message
and the specification of the two files a segment stores (signatures.lance and bands.lance): the version-0 signature procedure with known-answer vectors, the PyArrow schemas and schema metadata, the page table, and reader navigation. Version 0 admits only tokenizers whose data ships with Lance, so a query is tokenized from the index details alone and segments built anywhere stay comparable. It is a new, optional index type; no existing file or index format changes, and datasets without the index are unaffected.

• Design discussion: #8820
• Format specification (the proposal under vote): #9076
• Reference implementation, reviewed separately once the format is accepted: #9114

Per the voting process, format specification
changes are voted on the PR itself:

• +1: approve feat(format): add the MinHash LSH scalar index specification (experimental) #9076
• 0: abstain / no strong opinion
• -1: request changes on feat(format): add the MinHash LSH scalar index specification (experimental) #9076, including the blocking concern

Only approvals on the latest commit count. The vote needs three binding +1 votes from PMC members, excluding the proposer, and stays open for at least 72 hours, weekends excluded; the vote gate comments on the PR with the exact closing time.

Please keep detailed design discussion in the PR.

[yanghua]

+1 binding

[zhangyue19921010]

Hi @BubbleCal @Xuanwo @wjones127 and @jackye1995. Really appreciate if get your attention. would u mind to take a look if possible? Thanks in advance.

[Xuanwo]

My questions are:

• How general will this index be? Will it solve a wide enough range of use cases that it is better to build it in rather than provide it as an index plugin?
• How complex will this index be? How about do a PoC first to evaluate how good this index is before we start voting.
• There is also an experimental feature route: we can add this feature as an experiment without a formal vote, as long as adding or removing it would not affect users who did not use this feature. Maybe this is better for our case?

[zhangyue19921010]

Thanks for the questions — they are connected, so I'll answer them together.

1. How general is this index? Built-in vs plugin?

Near-duplicate detection over text is a routine step of ML data curation rather than a niche need: deduplicating pretraining and fine-tuning corpora, web crawls and RAG ingestion, train/eval contamination checks, and fuzzy joins on text columns, among others.

2. Complexity, and a PoC before voting

The implementation, along with accuracy and performance testing, is complete: #9114

Data. A synthetic corpus modeled on natural text, so the index sees realistic buckets and dits: Zipf word frequencies over a 50K vocabulary; text lengths of 6–240 words (30% snippets, 60% paragraphs, 10% articles, mean 40); a third of the texts carry one of 200 shared boilerplate phrases; 20% of the texts are near duplicates of an earlier text, with heavy-tailed cluster sizes (up to ~300K copies at 1B) and edits ranging from exact copies to 30% replaced words plus truncations. Every document is a pure function of its id, so the source of any near duplicate and its exact Jaccard are known without reading the dataset. 1M, 100M and 1B rows (210 GB of text at 1B), k=64 / b=8 / 3-token shingles, 200 queries per measurement, k=10.

	1M local	100M local	1B local	1B cloud (S3)
index size	228 MB	22.9 GB	229 GB	229 GB
build	1.2 s	68 s	2201 s	939 s
merge of all segments	0.65 s	135 s	2467 s	1106 s
query, cold (nothing cached), p50	6 ms	32 ms	242 ms	2.7 s
query, index cache filled on demand, p50 / p95	2.0 / 3.1 ms	3.1 / 5.9 ms	6.8 / 20.8 ms	65 / 217 ms
query after prewarm (64 GiB at 1B), p50 / p95	0.30 / 0.61 ms	0.36 / 1.6 ms	0.68 / 12 ms	0.67 / 57 ms
index layer, fully resident, p50 / p95	—	11 / 21 µs	14 / 26 µs	19 / 30 µs
peak RSS: build / merge	0.9 / 0.6 GB	6.2 / 1.7 GB	9.0 / 3.7 GB	16.1 / 4.3 GB
recall of the source text at true Jaccard ≥ 0.9 / 0.7–0.9	100% / 65%	100% / 52%	100% / 61%	100% / 61%
returned hits with true Jaccard ≥ 0.5	98.5%	99.5%	99.6%	99.6%
estimated vs exact Jaccard, mean error	0.009	0.010	0.008	0.008

3. The experimental route

From the code's point of view:

1. The implementation is decoupled: the index is a self-contained module that does not touch the other index implementations; the proto change is a single new message with no changes to existing fields; the index files live only under the index's own _indices/{uuid}/, and the manifest, data files and other indices are untouched. Existing indices and data are not affected in any way.
2. It has its own versioning: versions are checked when the index is opened, and an index written by a newer version fails with a clear error instead of being misread. Evolving the format is a version bump; the worst case is rebuilding the index, which is derived data, so the underlying data is never affected.

So I agree: let's follow the rules in #8304. The prerequisites are met

• the proto and the docs can be marked experimental;
• the index is a self-contained module whose files live only under its own _indices/{uuid}/, so readers and writers that don't use it are unaffected either way, and dropping it requires no data rewrite;
• the design discussion already exists (Approximate Text Deduplication — The MinHash LSH Index #8820).

[BubbleCal]

+1
that would be amazing if we can compare this with vector search in the case of text deduplication (cost/speed/accuracy...)

[zhangyue19921010]

@BubbleCal Thanks for your attention. And look forward to your help in reviewing the Format specification (the proposal under vote): #9076 and the Reference implementation, which will be reviewed separately once the format is accepted: #9114. The specific test cases and conclusions are as follows

Part 1 — Test setup

Item	Details
Dataset	100M rows of synthetic text, 40 words on average. 20% of the rows are duplicates of an earlier document, each produced by a single edit of the original: 25% are verbatim copies, the rest have 2–30% of their words replaced, and some are also truncated or extended. The table has three columns (id, text, vector) and lives on object storage
Embedding	768 dimensions, all-mpnet-base-v2, FP32
Vector index	IVF_RQ with 5-bit quantization, built on a single machine with the default parameters of main; 4,096 partitions
MinHash LSH index	128 hashes, 16 bands, 3-word shingles; built on a single machine
Machine	Index builds and queries all run on the same machine: 64 cores, 247 GB of memory

Part 2 — Cost

Cost item	Vector search	MinHash LSH
Data compute: generating the embedding column	6,044 core-hours (4,080 cores for 89 minutes)	none
Data storage: the embedding column	307 GB	none
Index build	7.25 core-hours of CPU time, 630 s wall-clock	0.32 core-hourck
Index storage	50.5 GB	45.4 GB

Part 3 — Query latency

Latency after prewarming the index, returning row IDs only. For each result count, the queries are original documents for which both engines can return a full result list.

For reference only. Results may vary with different datasets and parameters.

Results returned (k)	MinHash LSH, p50 / p99	Vector, nprobes=1024, p50 / p99
10	2.9 / 3.5 ms	286 / 302 ms
1,000	4.7 / 42.2 ms	286 / 299 ms
10,000	18.0 / 44.3 ms	292 / 303 ms
50,000	50.4 / 53.6 ms	320 / 326 ms

Part 4 — Accuracy

How accuracy is computed

• The data distribution is known in advance: for every original document, its ilarity to it are known exactly.
• We query with the original document and take the top K results, where K is the number of true duplicates of that document. Score = number of true duplicates among the top K results ÷
  K.
• The score is computed for 200 randomly sampled originals and averaged; both engines use the same 200 originals.
• The threshold for "how similar counts as a duplicate" is the true Jaccard sievels.

Duplicate threshold (true Jaccard similarity)	MinHash LSH	Vector, nprobes=1024
Jaccard ≥ 0.9	0.995	0.975
Jaccard ≥ 0.8	0.975	0.892
Jaccard ≥ 0.7	0.951	0.862
Jaccard ≥ 0.6	0.862	0.855
Jaccard ≥ 0.5	0.741	0.859

[Xuanwo]

Hi @zhangyue19921010, I suggest we take the experimental route: we can add and merge PRs first while keeping this vote open. Once we have validated this index on real user workloads, we can come back to decide whether to keep or remove it entirely.

[zhangyue19921010]

Sure. Thanks a lot for your suggestion.