Approximate Text Deduplication — The MinHash LSH Index

[zhangyue19921010]

1. Requirements & Background

1.1 The problem: exact matching cannot find "near-duplicates"

Datasets are full of records whose content is essentially the same but whose bytes differ. The canonical example:

Page A: "OpenAI released a new model today. The model shows ..."
Page B: "OpenAI released a new model today. The model shows ..."
        + footer / ads / minor text changes

Dedup by exact hash:

SHA256(A) != SHA256(B)     → judged "not duplicate", missed

Dedup by set similarity: cut the text into shingles (sliding windows of n consecutive tokens) and treat it as a set,

Jaccard(A, B) = |A ∩ B| / |A ∪ B| ≈ 0.93   → near-duplicate

The catch: Jaccard is a set-vs-set comparison; the naive approach is pairwise — O(n²), infeasible on corpora with hundreds of millions of rows. Even a single query — "find all documents similar to this one" — requires a full scan computing Jaccard row by row. That is exactly what an index should solve.

1.2 Why this matters for Lance

Lance positions itself as the columnar format for ML workloads, and near-duplicate detection is the first step of AI data engineering. Deduplication has been repeatedly shown to directly affect model quality — near-duplicates in training corpora cause memorization, eval-set contamination, and inflated effective data volume. Mainstream LLM data pipelines (e.g. fuzzy dedup of web corpora) use MinHash as the core dedup technique. These workloads land naturally on Lance:

Scenario	Shape
LLM training-data dedup	Trillion-token web text, fuzzy dedup before training
Web-crawl dedup	Same content from multiple sources, reposts, mirror pages
RAG document dedup	De-dup at ingestion time to avoid redundant retrieval results
Similar code-snippet detection	Code-corpus dedup, license tracing
Plagiarism / copied-content detection	Copy and paraphrase detection on content platforms
Similar tag / category / ID sets	Similarity search over any set-typed field
Set-overlap queries in recsys	"Users whose behavior set is most similar to this user"

Today Lance users must export data to external tools (Spark MinHashLSH, home-grown pipelines) and write results back — the data leaves the lake once and the semantics fracture once. With a built-in MinHash LSH index, dedup / similarity retrieval becomes one native query:

from lance.indices import IndexConfig
from lance.query import MinHashQuery

ds.create_scalar_index("text", IndexConfig(index_type="minhashlsh",
                                           parameters={"num_hashes": 128, "num_bands": 16}))
ds.to_table(nearest=MinHashQuery("OpenAI released a new model ...", "text"), limit=10)

1.3 How this differs from embedding-based dedup

The two answer different questions. MinHash detects literal duplication — "the same content with a few edits" (reposts with footers, mirror pages, copy-paste with tweaks) — with no model, pure CPU, and an interpretable Jaccard score.

Embedding-based dedup detects semantic duplication — "the same thing said differently" (paraphrases, translations) — and requires a model to embed the whole corpus plus a vector index to maintain.

LLM pipelines may run MinHash first to cheaply remove the bulk of literal duplicates, layering semantic dedup on top as needed. In Lance, semantic dedup is already covered by the existing vector indexes; this design supplies the other half — a model-free, literal near-duplicate index built directly on the text column.

---

2. Design

2.1 Core principle 1: MinHash — compress a set into a fixed-length signature

Step 1: turn each row of text into a set (tokenize + n-gram sliding-window shingles). Step 2: prepare k mutually independent hash functions π₁..πₖ; each hash function is applied to every element of the set, and the minimum across elements becomes one position of the signature — k functions give k positions:

  "OpenAI released a new model today ..."
          │  tokenize (reusing the FTS tokenizer stack) + shingle (n-gram sliding window)
          ▼
  S = { s₁="openai released a", s₂="released a new", s₃="a new model", ... }

              s₁      s₂      s₃        min taken per row (ACROSS set elements)
      π₁ │   417      93     805   │ →   93    → compress → signature[0]
      π₂ │   512     650      78   │ →   78    → compress → signature[1]
      π₃ │    31     944     602   │ →   31    → compress → signature[2]
      ⋮  │    ⋮       ⋮       ⋮    │
      πₖ │   208     115     337   │ →  115    → compress → signature[k-1]

  signature = k u16 values (e.g. k=128 → 256 bytes); length independent of set size

Why it works (one-line intuition): a hash function amounts to a random ordering over "all possible shingles"; signature[i] records "the front-runner of the set under that ordering (its hash value)". For two sets A and B, signature[i] is equal ⟺ the global front-runner of A∪B under that ordering falls inside A∩B — and that probability is exactly |A∩B| / |A∪B|, i.e. Jaccard itself. k independent functions are k independent votes, hence:

estimated Jaccard(A, B) = fraction of equal positions between the two signatures

k independent permutations are k independent samples, with error ~ O(1/√k). Text of arbitrary length is compressed into a fixed-length signature that is comparable position-by-position, mergeable, and indexable.

How the values are computed (the persisted contract):

1. Tokenize with the FTS tokenizer (lower-cased, stemming and stop-word removal off by default), form shingle_size-token shingles (a text shorter than one shingle is a single shingle; a text with no tokens has no signature and is not indexed), hash each shingle once with xxh64 (seed 42) into a 64-bit base hash x.

2. The k "functions" are k cheap 64-bit linear transforms πᵢ(x) = aᵢ·x + bᵢ mod 2⁶⁴ (aᵢ odd), with (aᵢ, bᵢ) derived deterministically from SplitMix64 seeded by 42. The 64-bit minimum mᵢ is taken over all shingles.

3. Each minimum is stored as 16 bits: signature[i] = (cᵢ · mᵢ mod 2⁶⁴) >> 48 with a per-position odd multiplier cᵢ from the same generator. This is b-bit MinHash: comparing 16 bits per position instead of 64 keeps the estimator unbiased up to a collision term ≤ 2⁻¹⁵ per position, far below the 1/k resolution of the estimate, and shrinks the signature table fourfold.

   Why the multiply-shift and not just the high bits of mᵢ: a minimum over n shingles is an order statistic, not a uniform value — its high 16 bits are all zero with probability 1 − e^(−n/65536), so long texts would look identical to each other. Multiply-shift with a random odd multiplier is 2-universal: for any two distinct minima the stored values collide with probability ≤ 2⁻¹⁵ regardless of how small the minima are.

4. Every constant above (seed, the derivation of aᵢ, bᵢ, cᵢ, the shingle separator, the hash function) is pinned by signature_version; changing any of them bumps the version so that segments built by different versions can never be compared.

2.2 Core principle 2: LSH banding — make similar rows collide on purpose

With signatures we still need to avoid pairwise comparison. The trick: split the signature into b bands of r elements each (k = b × r) and hash each band as a whole into one key; two rows become a candidate pair as soon as any one band key matches. The hit probability P = 1 − (1 − sʳ)ᵇ is an S-shaped curve of the similarity s:

signature (k=128)
┌────────┬────────┬────────┬─  ──┬────────┐
│ band 0 │ band 1 │ band 2 │ ... │ band 15│      r=8 elements per band
└───┬────┴───┬────┴───┬────┴─  ──┴───┬────┘
    │hash    │hash    │hash          │hash
    ▼        ▼        ▼              ▼
  key₀     key₁     key₂    ...    key₁₅

  band key = band_id << 56 | low 56 bits of xxh64(the r u16 values, little-endian; same seed)

  P(candidate) = 1 − (1 − sʳ)ᵇ       with b=16, r=8 the threshold ≈ (1/b)^(1/r) ≈ 0.71:
  s        =  0.5   0.6   0.7   0.8   0.9
  P(cand)  ≈  6%    24%   61%   95%   99.99%

Low-similarity rows almost never collide (small candidate set → fast); high-similarity rows almost always collide (high recall). Tuning (b, r) shifts the threshold: with k=64 / b=8 (r=8) it is ≈ 0.77, with k=96 / b=16 (r=6) ≈ 0.63. Lowering r raises recall for mid-similarity pairs but also lets the mass of low-similarity rows (which share common words and boilerplate) into the candidate set — at a billion rows r=4 admits ~10⁻⁴ of them, i.e. 10⁵ candidates per query — so r=6..8 is the practical range.

2.3 Why retrieval needs a refine step

Banding only answers "who collided" — it produces no score: all candidates look alike, cannot be ranked, and the middle of the S-curve produces false positives. Retrieval is therefore always two-phase:

1. Candidate generation (bands file): b key lookups produce the collision candidate set;
2. Refine (signatures file): fetch the candidates' full signatures, compute the estimated Jaccard exactly, sort, take top-k.

This dictates that the index must store two kinds of data — which is where the file design below comes from.

2.4 Index file design

Each index segment consists of two files (both standard Lance files):

_indices/{uuid}/
├── bands.lance          ── candidate generation: every (band key, doc) pair, globally sorted
│     band_key: u64   (high 8 bits band_id, low 56 bits band hash; ascending across the file)
│     doc_id:   u32   (segment-local row number of signatures.lance; ascending within a key)
│     ┌──────────────┬────────┐
│     │ 0x00a3…      │ 17     │ ← a bucket is the run of rows sharing a key ...
│     │ 0x00a3…      │ 4210   │
│     │ 0x00b7…      │ 96     │ ← ... most buckets are a single row
│     │    …         │  …     │
│     │ 0x0fc1…      │ 5      │ ← a hot bucket (a duplicate cluster) is a long run
│     │ 0x0fc1…      │ 8      │    that may span page boundaries
│     └──────────────┴────────┘
│     12 bytes per row, "none" encoding, rows × num_bands rows in total
│     + page table (global buffer): max(band_key) of every 4096-row page — 8 B per page,
│       ~0.01% of the file (1.6 MB per 100M rows at b=8), RAM-resident
│
└── signatures.lance     ── refine: signature table (row number = segment-local doc_id)
      _rowid:    u64
      signature: FixedSizeList<u16, k>  (non-null, fixed width: 8 + 2k bytes per row)

Two key trade-offs:

• bands is a sorted fixed-width pair table with a page table, not an in-memory hash table and not variable-width posting rows: the number of band keys ≈ rows × b (100M rows × 16 bands = 1.6B keys) — impossible to keep resident, so the file stays key-ordered and is located via a resident page table (this is also why the build cannot avoid the sort). One row per pair costs a constant 12 bytes: a Lance variable-width column carries ~8.6 B of overhead per row, so posting arrays would not be smaller for the singleton buckets that make up the vast majority, and fixed-width rows give the reader exact byte offsets. A bucket is simply a run of equal keys; its extent is known from the page table without probing (it starts in the first page whose maximum key reaches the key and ends in the first page whose maximum key exceeds it, and the pages in between hold nothing else), so a duplicate cluster of any size is read in bounded windows — no truncation, no recall loss, and no memory proportional to the cluster. Segment merge is a rebuild from signatures (§3.3), not a posting merge.
• signatures uses fixed-width rows with row number = doc_id: the row width is constant (8 + 2k bytes; 264 B at k=128), and with Lance's full-zip encoding row i lives at byte offset i × row_width — fetching a signature by doc_id is one exact ranged read, with no lookup structure at all. Consecutive 128 MiB chunks (≈ 987K rows at k=64, ≈ 500K at k=128) are the unit of cache residency.

2.5 End-to-end flow

Write (index build / delta):

  data stream (text + _rowid)
      │  per row: tokenize → shingle → signature   (CPU pool; the scan is the only serial stage)
      ├───────────────→ signatures.lance (appended in doc_id order)
      │  per row: split signature into bands → b (band_key, doc_id) pairs
      └── external sort ─→ bands.lance (written globally sorted by band_key) + page table
          (runs are sorted in memory and spilled as raw 12-byte records to a local
           temporary directory, partitioned by key so the merge works in bounded groups
           in parallel; the run and group sizes derive from one memory budget — 2 GiB
           by default, `LANCE_MEM_POOL_SIZE` overrides it — and the temporary space is
           checked against `LANCE_MAX_TEMP_DIRECTORY_SIZE` (100 GiB by default) and the
           free space of `TMPDIR` before every spill, so a build that cannot fit fails
           before writing rather than halfway through; 1B rows at b=8 spill 89 GiB,
           removed with the build)

Query (top-k):

        query text
            │ ① build the signature with the params recorded in the index (pure CPU)
            ▼
        [signature] ── ② split into b bands → b band_keys
            │
            ▼ ③ page-table binary search locates every bucket's first and last page;
            │    all boundary pages are fetched in ONE scattered read (cached);
            │    the interior pages of a bucket that spans pages are read as doc_id-only
            │    8 MiB windows and dropped once merged (not cached)
      bands.lance ──→ candidate doc_id set (bitmap)
            │
            ▼ ④ candidates in resident signature chunks are scored from memory;
            │    the rest are read in scattered 8 MiB batches (≈ 61K rows at k=64), or by a
            │    sequential scan of the file when candidates exceed 10% of the segment
   signatures.lance ──→ score each candidate: estimated Jaccard (equal-position fraction)
            │
            ▼ ⑤ bounded top-k heap ordered by (distance, row id); multi-segment results merged directly
      result: _rowid + _distance (= 1 − estimated Jaccard)

The IO upper bound of a typical query is crisp: one scattered read of ≤ 2b band pages (cold) + one batched candidate-signature read; everything else stays in memory, and a prewarmed segment answers from memory alone. Step ⑤ deserves emphasis: the estimated Jaccard depends only on the two signatures themselves and on no global statistics, so top-k merging across segments is exact by nature — cleaner multi-segment semantics than corpus-statistics-based scoring (e.g. BM25).

Cache residency: a query caches the band pages it reads, so pages warm up on demand; signatures are only brought in by prewarm, chunk by chunk (as many as the index cache holds — the cache reports its capacity), then band pages if room remains. Residency is therefore proportional to the cache, never all-or-nothing: with a 32 GiB cache a 100M-row segment answers in ~11 µs at the index layer; with 8 GiB (60% of the chunks) the median stays there while the tail pays one scattered read. On an object store the resident numbers are the same and every non-resident access costs one round trip (§4).

2.6 Parameters

Parameter	Default	Meaning
num_hashes (k)	128	Signature length; precision ~1/√k, storage 8 + 2k B/row in signatures.lance
num_bands (b)	16	Number of bands; must divide k evenly — otherwise a hard error (no silent truncation); bands.lance costs 12·b B/row
shingle_size	3	Sliding-window length in tokens
tokenizer	FTS default with stemming and stop-word removal off	The FTS tokenizer configuration, persisted as lance.table.InvertedIndexDetails; custom_stop_words and lance_tokenizer are rejected because the details message cannot record them, and a query must rebuild the tokenizer from the index alone

There is no seed parameter: the hash seed (42) and every derived constant are part of signature_version, so an index is fully described by the four parameters above plus that version.

2.7 Format contract

The durable contract — what a reader needs to answer queries against files written by any conforming writer — is small and lives in protos/index.proto and docs/src/format/index/scalar/minhash_lsh.md (submitted as a dedicated format PR ahead of the implementation, per the format-change process):

message MinHashLshIndexDetails {
  uint32 num_hashes        = 1;
  uint32 num_bands         = 2;
  uint32 shingle_size      = 3;
  lance.table.InvertedIndexDetails tokenizer = 4;   // reuses the FTS tokenizer contract
  uint32 signature_version = 5;                     // pins seed, hashing and compression
}

Item	Contract
signatures.lance	Columns _rowid: u64, signature: FixedSizeList<u16, num_hashes> (full-zip structural encoding, no compression, so row i = doc_id i sits at a fixed offset); schema metadata minhash_lsh_params (JSON of the four parameters) and minhash_lsh_index_version
bands.lance	Columns band_key: u64, doc_id: u32 (no compression), sorted by (band_key, doc_id); schema metadata minhash_lsh_params, minhash_lsh_index_version, minhash_lsh_num_docs, minhash_lsh_page_rows (4096) and minhash_lsh_page_table_buffer (index of the global buffer holding one little-endian u64 max key per page). A reader takes all of its metadata from this file
Signature	§2.1 steps 1–4; band key = §2.2
Reader navigation	§2.5 steps ①–④
Scoring	_distance = 1 − (equal positions / num_hashes), ties broken by row id
Coverage	A segment's fragment_bitmap names the fragments it indexes; rows outside every segment are not in the index (§3.2 says what the query does about them); a segment opened after a deferred compaction remaps its stored row ids through the fragment-reuse index before any mask, filter or rebuild sees them
Versioning	index_version (file layout) and signature_version (signature semantics) are independent; both are 0 while the format is unstable; a reader rejects a segment whose index_version is newer than it knows or whose signature_version differs from its own

This supersedes the layout sketched in the first draft of the discussion (posting rows per bucket, u32 signatures).

---

3. Integration with Lance's Index Framework

3.1 Index build/load: existing paths, minimal new machinery

Step	How
Definition	MinHashLshIndexDetails in protos/index.proto (§2.7)
Registration	One add_plugin line in IndexPluginRegistry; plugin name MinHashLsh
Training	The plugin exposes the framework's BasicTrainer: the usual value + _rowid stream in, the two index files out
Storage	Files written via the existing IndexStore into _indices/{uuid}/, isomorphic to every scalar index
Loading	The details type URL in the manifest dispatches back to this plugin automatically
Creation API	Python create_scalar_index(column, IndexConfig(index_type="minhashlsh", parameters={...})) through the existing generic entry — no binding changes

Two trait methods were added with default implementations, so no existing plugin or cache changes: ScalarIndexPlugin::validate_new_segments_against_existing (the segment-consistency gate of §3.4) and CacheBackend::capacity_bytes (lets prewarm size residency to the cache).

3.2 Top-k query: under the nearest similarity-search, zero new APIs

MinHash retrieval is, at its core, similarity top-k — isomorphic to vector search (ranked by similarity, k is the only semantic parameter, scores independent of corpus statistics) — not text-relevance search (BM25). It therefore hangs under the nearest umbrella, with no new entry point, only one new query object:

from lance.query import MinHashQuery

# today: vector search
ds.to_table(nearest={"column": "vec", "q": [...], "k": 10})

# new: near-duplicate search — the same nearest knob, _distance = 1 − estimated Jaccard
ds.to_table(nearest=MinHashQuery("OpenAI released a new model ...", "text"), limit=10)

The result column follows _distance (= 1 − estimated Jaccard; Jaccard distance is a true metric, lower-is-better matches vector-search convention, and distance_range can later provide "similarity ≥ threshold" range queries for free).

The only thing a user has to learn is one class name. The implementation side is purely additive as well — one new peer exec node on the query side, the existing plugin machinery on the index side:

  nearest = MinHashQuery(text, column)
        │  (zero new Python params)
        ▼
  plan dispatch: query object type = MinHash → find the minhash index on the column
        ├─ MinHashSearchExec (peer of the existing KNN/FTS nodes)
        │      per index segment: steps ①–⑤ of §2.5 → per-segment top-k
        └─ FlatMinHashExec, only for rows no segment covers (fragments added since the
               last optimize, rows rewritten by a data overlay): computes their signatures
               on the fly with the same code and scores them exactly like the index does
        ▼
  union → top-k by _distance → _rowid + _distance
        (composes with prefilter / deleted rows / downstream take & filter as usual;
         an external row mask is applied before either node's top-k)

Three semantic guarantees, each with a clear anchor point in the source:

1. Illegal combinations are unrepresentable by construction: the MinHash query does not join the FtsQuery enum, so it can never end up inside BooleanQuery / BoostQuery being summed or max-ed with BM25 scores (different scales) — no validation code needed; setting it together with a vector or FTS query is an explicit plan-time error.
2. Results do not depend on optimize timing: rows the index does not cover yet are scored by the flat node with the same signature code, so a query returns the same top-k whether or not optimize_indices has run; fast_search=True opts into index-only results (the weak-consistency mode vector search already offers). A column with no MinHash index at all is an explicit error naming the required index type — never a silent full scan.
3. Every score is comparable: the query signature is built from the parameters recorded in the index, never user-supplied, and all segments of an index are held to identical parameters (§3.4).

Existing FTS and vector query objects, exec nodes, and behavior are untouched.

3.3 Lifecycle: the standard segment mechanism

The segmented lifecycle of existing scalar indexes applies directly, with nothing special-cased:

• Delta: new fragments get covered by a new segment built by optimize; queries fan out over all segments (merging is exact, per §2.5);
• Merge / update / remap — one path, a rebuild driven by the stored signatures: the old segments' signatures.lance is streamed (rows of retired fragments dropped through the framework's old-data filter, row ids rewritten through a compaction mapping when remapping), band keys are recomputed from the stored signatures, and the external sort writes the new segment. The text is never tokenized again, so merging costs the same as writing the index once, and one pipeline serves optimize_indices, explicit segment merges and post-compaction remaps alike;
• Row ids and deletes: the signature table records _rowid (row address or stable row id). Deleted rows are masked at query time; after a deferred compaction the segment is opened with the fragment-reuse index, and the stored row ids are remapped through it both when answering queries and before any rebuild applies its filter — so a merge after a deferred compaction keeps every live row;
• Coverage: a segment's fragment_bitmap declares the fragments it indexes; rows outside every segment's coverage are served by the flat node (§3.2) until the next optimize.

3.4 Distributed indexing & parameter consistency

Parameter consistency (the precondition for comparability):

• Every segment records the full parameter set (k, b, shingle size, the tokenizer configuration) plus signature_version in its MinHashLshIndexDetails, and the index is only comparable if all segments agree; that agreement is enforced rather than assumed:
• Incremental builds derive the parameters from the existing segments, never from the user again.
• Write-path gates: committing or merging segments compares their parsed parameters and rejects any mismatch (validate_new_segments_against_existing, with a byte-equality fast path) — parameter drift is stopped at write time instead of surfacing as silently wrong query results. Comparing parsed parameters rather than bytes keeps a segment written by a newer Lance that serializes an extra default field from being mistaken for drift.
• Query side: the query signature's parameters are read only from the index (never user-supplied at query time), and opening multiple segments performs a defensive equality check across them (cached with the index handle, zero marginal cost) — even an index corrupted by an external writer fails loudly instead of returning silently mis-ranked results.

Distributed build: the initial full build assigns fragments to workers, each producing an uncommitted segment; a final commit validates and atomically registers them:

driver: fix params ──┬─→ worker 1: build_uncommitted(params, fragments 0-99)   → segment A
                     ├─→ worker 2: build_uncommitted(params, fragments 100-199) → segment B
                     └─→ worker N: …                                            → segment N
                                   ↓
        driver: commit([A, B, …, N])
                ├─ validate: identical parameters across all segments (incl. signature_version), reject otherwise
                └─ atomically register as N segments of one logical index

Workers need zero coordination and zero communication — doc_ids are segment-local and the hash functions derive deterministically from the shared parameters, so there is no global structure to exchange; scores depend on no corpus statistics, so cross-segment top-k merging is exact by nature. Incremental builds commit new delta segments for newly added fragments only; existing segments are retained automatically.

Scale limit: doc_ids are segment-local u32 (a cap of 4.29B rows per segment — a 1.1 TB signature table at k=128, far beyond any sane single-segment size). The build validates the row count and fails with clear guidance to build fragment-scoped uncommitted segments and commit them together — the same mechanism as the distributed flow above, equally usable on a single machine. Refine never materializes a whole segment: resident chunks are scored in memory, the rest in bounded scattered batches or one streaming pass (§2.5 ④), so query memory does not grow with the segment or with the size of a duplicate cluster.

---

4. Measured (reference implementation)

Data. Synthetic corpus modeled on natural text so the index meets realistic buckets and edits: 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 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.

Machine. 64-core Xeon 8457C, 247 GB RAM, one ~190 MB/s virtual disk (local), and Volcengine ToS S3 in the same region (cloud; index and data on the bucket, spill on the local disk). The OS page cache is dropped before every phase.

	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

[zhangyue19921010]

Really appreciate if you have any thoughts on this @yanghua @Xuanwo @jackye1995 @BubbleCal @wjones127 @westonpace :)

[BubbleCal]

Some questions and comments:

1. How to handle the texts seems important, I think we can just reuse the existing FTS's tokenizer API and functionalities (e.g. lower-case, stemming, ...), and adding the shingle function to the tokenizer API, the tokenizer params should be part of the index params.
2. in bands.lance, can we store it as bucket_key | list of doc ids to avoid sorting? what's the tradeoff here?
3. this design would limit the max num rows the index can work to u32::max, we need a solution in case of more documents here
4. Make the query as one of full text query seems strange, this is more like vector search, can we go with dataset.to_table(nearest="this is the query text", ...) or dataset.to_table(nearest=MinHashQuery("this is the query text"), ...)?

[zhangyue19921010]

Hi @BubbleCal, thanks a lot for the review — it materially improved the design. Where we landed (proposal text updated accordingly):

1. Tokenizer — agreed. We'll reuse the FTS tokenizer API/stack, and put the full tokenizer config into the index params (persisted in index details, replayed verbatim at query time).

2. bucket_key | list of doc_ids — agreed, with one note. The file becomes one row per distinct bucket_key, with the posting stored as a sorted u64 array. The note: the sort itself is unavoidable — at #keys ≈ rows × b an in-RAM key map is impossible, so lookup requires a key-ordered file + a resident page table.

3. u32 limit — agreed, fixed. doc_id is now u64: no row-count limit anywhere in the format, one code path, consistent with Lance's u64 row-reference convention.

4. nearest=MinHashQuery(...) — agreed, and it's the better design. MinHash search is similarity top-k, not text relevance.

Thanks again — happy to hear if these resolutions look good to you, and feel free to ping me anytime if there's anything else worth discussing.

[BubbleCal]

@zhangyue19921010 u32 doc_id may be good, we can split the index into multiple segments if it's too large
for distributed indexing, we may need to make sure that all segments would share the same hash functions, so that they are comparable with each other.
It would be nice if we can make it clear about the distributed case.

This design looks good and this feature is needed, feel free to file a PR!

[zhangyue19921010]

Thanks @BubbleCal!

Distributed case — now spelled out in the proposal (new section 3.4): all signature parameters plus a signature_version live only in the index-level metadata as the single source of truth, so every segment derives the same hash functions; commits/merges reject segments with mismatched metadata, and the query side reads parameters from the same metadata — comparability is enforced on both write and read paths.

Thanks again for the review — I'll file a PR soon. Any questions or suggestions are always welcome!