[VOTE] Add FM-Index to Lance index format

[beinan]

This is the voting thread for adding the FM-Index scalar index type to the Lance format specification. See PR #7026 for the implementation.

What is FM-Index?

FM-Index is a compressed full-text index based on the Burrows-Wheeler Transform, following the Infini-gram Mini paper. It supports exact substring matching with index size ~0.44-0.95x of the text corpus.

Key features:

• Exact results (no false positives, unlike N-Gram)
• 17x faster than N-Gram on medium-length queries
• Works with any query length (N-Gram fails on queries shorter than 3 chars)
• Index size comparable to text size (vs 6x for suffix array)

Format Changes

• Add FMIndexIndexDetails message to protos/index.proto (empty message; all metadata stored in Lance file headers)
• Add FMIndex = 11 variant to IndexType enum
• Index data stored as Lance files using the existing blocked storage format (Huffman wavelet bitvectors + sampled suffix array)

Benchmark (100K gitlake source code files, 1.59 GB text)

Metric	FM-Index	N-Gram
Index size	1,513 MB (0.95x)	84 MB (0.05x)
Medium queries	29ms/q	480ms/q
Long queries	34ms/q	206ms/q

Voting Instructions

Please vote by commenting:

• +1 Add FM-Index to the format specification
• 0
• -1 Do not add FM-Index to the format specification because...

[westonpace]

+1

[prrao87]

+1 (binding)

[jackye1995]

+1 binding