Uber Similarity Search Index

Uber Similarity Search Index, or USSI, is a platform-agnostic, in-memory Java library for nearest neighbor search. It is designed to be embedded inside search systems such as OpenSearch data nodes, while keeping the indexing logic independent from any one serving platform.

The index supports mutable ingestion, k-nearest-neighbor search, minimum-similarity search, and metadata filtering over records represented as TermsAndValues.

Status

This module is an early open-source candidate and currently implements the core memory-only index structure:

• Mutable generic and sparse caches for inserts, updates, deletes, and search.
• Delete-only generic, dense, term, sequence, signature, and hybrid sparse indexes built from graduated cache contents.
• L2, signed Jaccard, and signed weighted-Jaccard (Ruzicka) comparators with configurable normalization into a [0.0, 1.0] similarity score.
• Generalized Levenshtein distance (gld) and its normalized form (ngld) over ordered sequences, each over a configurable Levenshtein, Damerau-Levenshtein, or longest common subsequence distance.
• Exact sparse candidate generation through inverted term lists with length, position, and unordered-prefix filtering.
• Approximate sparse candidate generation using MinHash for Jaccard and I2CWS, ICWS, PCWS, or SCWS for Ruzicka.
• A hybrid sparse index that sends rows with at most 270 terms to the exact term index and longer rows to the signature index.
• A sequence index that generates candidates from element multisets and has the configured edit distance verify each candidate against the ordered sequences.
• Metadata filtering with in-filtering, pre-filtering, post-filtering, and automatic strategy selection.
• Bounded top-k accumulation with BoundedSizeMaxHeap, so each searchable structure and the final merge keep only the configured result limit.
• Optional OpenBLAS acceleration for dense matrix-vector dot products, with a Java fallback when the native scorer is unavailable.

Dense, sparse numeric, and sequence records all use the same public TermsAndValues API. Which of the three a comparator can read is what decides the searchable structures it can be paired with, and a config pairing a comparator with a structure that stores a record type it cannot read is rejected up front.

The library does not provide persistence, sharding, external document-id mapping, TTL enforcement, authorization, or platform-specific plugin/adapter layers for serving systems such as OpenSearch, RediSearch, Milvus, etc. Those concerns are expected to be handled by the hosting platform.

Architecture

The top-level NearestNeighborSearchIndex owns one active cache, zero or more graduating caches that are being converted into indexes, and zero or more indexes. The Internal Design section explains why graduated indexes only need delete support.

insert/update/delete
        |
        v
 active mutable cache
        |
        | reaches maxCacheSize
        v
 graduating cache --background build--> delete-only index
                                      |
                                      | too many searchable structures
                                      v
                              consolidated index

search query
        |
        v
 active cache + graduating caches + indexes
        |
        v
 bounded heap merge

Rows are inserted into the active cache. When the cache reaches maxCacheSize, it is rotated into the graduating-cache list and a fresh cache starts accepting writes. A background task snapshots the graduating cache and builds an index. When the total number of searchable structures reaches maxNumSearchableStructures, older indexes are consolidated in the background.

Deletes are applied to the newest structure that contains the row. Updates are implemented as delete plus insert with the same rowNum, preserving the logical row identity while moving the latest version into the active cache.

The top-level index uses a single read/write lock. Searches run under the read lock, and mutations run under the write lock. Background builds snapshot data under the read lock, build outside the lock, and take the write lock only for the final swap and tombstone replay.

Data Model

Each inserted row has:

• A TermsAndValues record.
• A Map<String, String> metadata object used only for filtering.
• An internal signed 64-bit rowNum returned by insert.

Top-level rowNum values start at 0 and increment on each insert. Updates reuse the existing rowNum.

The hosting platform should maintain any mapping between its document IDs and the returned rowNum values.

TermsAndValues uses parallel arrays:

new TermsAndValues(String[] terms, float[] values)

It can represent three record types:

• Dense vector: empty terms, non-empty values of a fixed dimension.
• Sparse weighted feature: non-empty terms, non-empty values with the same length.
• Sequence: non-empty terms holding the elements in the order they arrived, repeats included, and empty values.

The l2, jaccard, and ruzicka comparators work on both dense and sparse numeric records. Dense values align by array position. Sparse values align by term, and a term missing from either record has value 0.0. The dense index is the exception: it is a matrix implementation that requires dense L2 records with a fixed number of dimensions.

The gld and ngld comparators read sequences only. Sequence terms are left in the order they arrived rather than canonicalized, since that order is what an edit distance measures.

Jaccard compares signed presence: every non-zero magnitude contributes 1.0, and opposite signs do not intersect. Ruzicka uses the same signed matching rule but preserves absolute value magnitudes as weights. L2 uses the original numeric values.

Public string terms are lowercased and encoded into primitive longs on ingestion to reduce memory overhead. Sparse records are canonicalized by sorting the encoded terms, summing values for duplicate terms, and dropping zero sums unless every summed value is zero. Metadata keys and values used for filtering are also lowercased.

Quick Start

import com.uber.ussi.NearestNeighborSearchIndex;
import com.uber.ussi.SearchResults;
import com.uber.ussi.config.NamespaceConfig;
import com.uber.ussi.entity.meta.MetaFilter;
import com.uber.ussi.entity.termsandvalues.TermsAndValues;
import java.util.List;
import java.util.Map;

NamespaceConfig config =
    NamespaceConfig.builder()
        .minTermsAndValuesLength(128)
        .maxTermsAndValuesLength(128)
        .maxCacheSize(10000)
        .cacheType("generic")
        .indexType("dense")
        .comparatorType("l2")
        .comparatorNormalizerType("reciprocal")
        .maxNumSearchableStructures(4)
        .maxNumSimilarities(1000)
        .build();

try (NearestNeighborSearchIndex index = NearestNeighborSearchIndex.create(config)) {
  float[] sfValues = new float[128];
  sfValues[0] = 1.0f;
  float[] laValues = new float[128];
  laValues[1] = 1.0f;
  float[] updatedLaValues = new float[128];
  updatedLaValues[0] = 0.8f;
  updatedLaValues[1] = 0.2f;

  long sf =
      index.insert(
          new TermsAndValues(new String[0], sfValues),
          Map.of("city", "sf", "country", "us"));
  long la =
      index.insert(
          new TermsAndValues(new String[0], laValues),
          Map.of("city", "la", "country", "us"));

  TermsAndValues query = new TermsAndValues(new String[0], sfValues);
  MetaFilter filter = new MetaFilter(Map.of("country", List.of("us")));

  SearchResults neighbors = index.getNearestNeighborRowNums(10, query, filter);
  long nearestRowNum = neighbors.getRowNum(0);
  float nearestSimilarity = neighbors.getSimilarity(0);

  index.update(
      la,
      new TermsAndValues(new String[0], updatedLaValues),
      Map.of("city", "sf"));
  index.delete(sf);
}

getNearestNeighborRowNums and getSimilarRowNums return SearchResults, an ordered result container with parallel rowNums and similarities arrays. Results are ordered by descending similarity, with lower rowNum values breaking ties.

Search API

static NearestNeighborSearchIndex create(NamespaceConfig namespaceConfig)
NamespaceConfig getNamespaceConfig()
long insert(TermsAndValues record, Map<String, String> metadata)
boolean delete(long rowNum)
boolean update(long rowNum, TermsAndValues record, Map<String, String> metadata)
SearchResults getNearestNeighborRowNums(int k, TermsAndValues record, MetaFilter metadataFilter)
SearchResults getSimilarRowNums(float minSimilarity, TermsAndValues record, MetaFilter metadataFilter)
int size()
void close()

Search behavior:

• k must be greater than 0.
• minSimilarity must be in [0.0, 1.0].
• Returned rows are capped by maxNumSimilarities.
• Similarities are normalized comparator outputs.
• Top-k tie-breaking prefers higher similarity, then lower rowNum.
• Empty metadata filters match all non-deleted rows.

Configuration

NamespaceConfig is immutable and should be built with NamespaceConfig.builder().

Field	Description
minTermsAndValuesLength	Declared minimum record length. Must be non-negative.
maxTermsAndValuesLength	Declared maximum record length. Must be at least minTermsAndValuesLength.
maxCacheSize	Number of active-cache rows that triggers cache graduation to an index. Must be positive.
cacheType	Supported values: generic, sparse.
cacheParams	Cache-specific options, including sparse-term popularity filtering.
indexType	Supported values: generic, dense, term, sequence, signature, sparse.
indexParams	Index-specific options such as metadata filtering strategy.
comparatorType	Supported values: l2, jaccard, ruzicka, gld, ngld.
comparatorParams	Comparator-specific options, including signature generation and sequence distance.
comparatorNormalizerType	Supported values: identity, lp, reciprocal, complement.
comparatorNormalizerParams	Currently unused; reserved for future normalizer-specific options.
maxNumSearchableStructures	Maximum number of active, graduating, and indexed structures before consolidation. Must be greater than 2.
maxNumSimilarities	Maximum result count kept by structure-level search and final merge. Must be positive.

The current implementation validates these length bounds structurally but does not enforce them against each inserted record.

Supported index combinations:

indexType	Record type	Comparator	Candidate generation
generic	Dense, sparse numeric, or sequence	l2, jaccard, ruzicka, gld, ngld	Exact sequential scan.
dense	Fixed-dimension dense	l2	Exact matrix scan with Java or OpenBLAS dot products.
term	Sparse numeric	l2, jaccard, ruzicka	Exact inverted term lists.
sequence	Sequence	gld, ngld	Element-multiset inverted lists; retained candidates are scored against the ordered sequences.
signature	Sparse numeric	jaccard or ruzicka with a signature generator	Approximate signature inverted lists; retained candidates are scored with the original comparator.
sparse	Sparse numeric	jaccard or ruzicka with a signature generator	Hybrid exact/signature routing at 270 terms.

The generic cache is a sequential scan and works with dense or sparse numeric records. The sparse cache maintains mutable inverted term lists and is intended for sparse numeric records. A sparse cache should normally graduate to a term, signature, or hybrid sparse index. A sequence namespace caches generically, because the sparse cache reads one value per distinct term and a sequence supplies neither.

Index parameters:

Parameter	Values	Default	Description
metadata_filtering_strategy	auto, in_filtering, pre_filtering, post_filtering	auto	Controls how indexes apply metadata filters. Values use underscores.
max_pre_filtering_rows_ratio	double in [0.0, 1.0]	0.1	Maximum matching-row ratio that allows pre-filtering.
max_fraction_ids_per_sparse_key	double in (0.0, 1.0]	1.0	For sparse indexes, discards a term when it occurs in more than this fraction of indexed rows. 1.0 disables this filtering.
popular_term_discard_scope	candidates_and_verification, candidates_only	candidates_and_verification	Which phases of a search a discarded term is absent from. See Discarding Popular Terms.
sparse_candidate_generator	spars, spars_merge	spars	For sparse indexes, selects the candidate generation algorithm. See Sparse Candidate Generation.

The generic cache does not currently accept any cacheParams. The sparse cache accepts the following parameters:

Parameter	Values	Default	Description
max_fraction_ids_per_sparse_key	double in (0.0, 1.0]	1.0	Filters terms whose one-sided popularity confidence bound exceeds this fraction. 1.0 disables this filtering.
popular_term_discard_scope	candidates_and_verification, candidates_only	candidates_and_verification	Which phases of a search a discarded term is absent from. See Discarding Popular Terms.
max_fraction_ids_per_sparse_key_confidence	double in [0.5, 1.0]	0.95	Confidence used for the sparse-cache popularity bound. 0.5 reduces the check to observed popularity.
full_reevaluation_cache_size_decrease_fraction	double in [0.0, 1.0]	0.10	Cache-size decrease from the last exact popularity evaluation that triggers a full reevaluation. 0.0 reevaluates after every deletion; 1.0 waits until the cache is empty.

The mutable sparse cache updates popularity decisions incrementally. Deletions recheck terms from the deleted row and the currently filtered set. When the cache has shrunk by at least the configured fraction from the last exact evaluation, it reevaluates all terms to account for the smaller denominator.

To apply the same popularity threshold before and after cache graduation, set max_fraction_ids_per_sparse_key to the same value in both cacheParams and indexParams. The same goes for popular_term_discard_scope: it is read from each structure's own params, so setting it on only one of the two leaves a namespace reporting one kind of similarity before graduation and the other kind after. The confidence parameter applies only to the mutable cache.

Comparator parameters:

Parameter	Comparator	Values	Default
signature_generator_type	jaccard	minhash	None
signature_generator_type	ruzicka	i2cws, icws, pcws, scws	None
sequence_distance_type	gld, ngld	levenshtein, damerau_levenshtein, lcs	levenshtein

Without signature_generator_type, Jaccard and Ruzicka still work in generic, sparse-cache, and exact term paths. The signature and hybrid sparse indexes require it. L2 does not support signature generation.

Both sequence comparators are named for the distance they report. gld is the generalized Levenshtein distance, the number of single-element edits that turn one sequence into the other. It is generalized in that which edits count is itself configurable, through sequence_distance_type. ngld is the normalized generalized Levenshtein distance, that same edit count divided by the two sequences' lengths as 2 * d / (length1 + length2 + d), which is what makes it comparable across sequences of different lengths.

The distances differ only in the edits they permit:

• levenshtein: insertion, deletion, and substitution of one element.
• damerau_levenshtein: the Levenshtein edits plus transposition of two adjacent elements, so a pair of elements in the wrong order costs one edit rather than two.
• lcs: insertion and deletion only, the distance complementing the longest common subsequence. Every element outside that subsequence has to be deleted from one sequence or inserted into the other, so the distance is length1 + length2 - 2 * lcsLength. Rewriting an element costs a deletion and an insertion, so an lcs distance is never below the levenshtein distance over the same pair.

When metadata_filtering_strategy is auto, GenericIndex resolves metadata filtering to in-filtering. DenseMatrixIndex tries pre-filtering when the metadata filter is selective enough according to max_pre_filtering_rows_ratio; otherwise it falls back to post-filtering. Term and signature indexes also try selective pre-filtering, then fall back to in-filtering.

Normalizer behavior:

• identity: the comparator value must already be a similarity in [0.0, 1.0].
• reciprocal: converts distance d to 1 / (1 + d).
• lp: converts distance d to 1 - d / 2, intended for bounded Lp-style distances.
• complement: converts distance d to 1 - d, and requires d to already be in [0.0, 1.0].

Jaccard and Ruzicka naturally produce similarities and normally use identity. L2 produces a distance and normally uses reciprocal, or lp when the input domain guarantees distances in [0.0, 2.0]. gld produces an unbounded edit count and normally uses reciprocal; ngld produces one already normalized into [0.0, 1.0] and normally uses complement.

None of the currently supported comparator normalizers accept parameters. comparatorNormalizerParams is reserved for future use.

Metadata Filtering

Metadata is provided at insertion time as Map<String, String>. All non-null metadata keys and values are indexed for filtering. Null metadata keys and values are skipped.

Queries use MetaFilter, which accepts a Map<String, List<String>>.

new MetaFilter(
    Map.of(
        "country", List.of("us"),
        "city", List.of("sf", "la")))

Filtering semantics:

• Values within the same metadata key are ORed.
• Different metadata keys are ANDed.
• Keys and values are matched exactly after lowercasing.
• An empty MetaFilter matches every non-deleted row.

For example, country in [us] AND city in [sf, la] matches rows in either SF or LA where the country is US.

Internal Design

The following sections describe internal maintenance structures. Embedding platforms should use the public NearestNeighborSearchIndex API rather than managing these structures directly.

Handling Inserts, Deletes, and Updates

The top-level index is mutable even though graduated indexes are delete-only. New rows are always inserted into the active mutable cache. When that cache reaches maxCacheSize, it is snapshotted and built into an index; newer writes continue in a fresh active cache.

Delete-only indexes are enough for graduated data because they only need to serve searches over the snapshot they were built from and hide rows that are no longer current. A delete removes the row from the active cache if present. Otherwise, the system scans searchable structures from newest to oldest and tombstones the record in the first structure that contains it. Only the first match needs a tombstone because each rowNum lives in exactly one structure at a time. Candidate scoring skips tombstoned records at query time without waiting for physical removal from inverted lists. An update is handled as a delete of the old row version followed by inserting the new version into the active cache with the same logical rowNum, so the active cache always holds the latest version.

If a record is deleted while a cache graduation or index consolidation is building in the background, that delete is recorded in a per-build tombstone set and replayed onto the newly built index when the build completes. This ensures that rows deleted during the build do not reappear in search results after the swap.

This keeps immutable index implementations simple: they do not need to support in-place inserts or updates, only search and tombstone-style deletes. Background consolidation later rebuilds older indexed rows into a newer index and drops deleted rows from that rebuilt snapshot.

Searchable Structures

Index implementations live under com.uber.ussi.searchablestructure.index, split into sub-packages by index type:

• index.generic: GenericIndex, the generic sequential-scan index.
• index.dense: DenseMatrixIndex and its matrix-vector dot-product scorers (DenseMatrixDotProductScorers and the Java and OpenBLAS scorers).
• index.sparse: TermIndex, SequenceIndex, SignatureIndex, and the hybrid SparseIndex. All four share BaseSparseIndex, which owns the uni-sorted inverted lists and drives the candidate generators. TermIndex and SequenceIndex further share BaseTermKeyedIndex, which covers the indexes whose list keys are the terms of the record being indexed rather than a signature derived from it.
• index.sparse.generator: the two generators every sparse index draws its candidates from, SparseFilteredSearch (sparse-key-major) and SparseMergeSearch (row-major), along with the inverted list they walk and the search context, row filter, and results heap they walk it with. A generator only ever reads sparse keys and uni values, so sequences reuse both unchanged: a sequence is indexed by the multiset of its elements, and only the comparator that scores a candidate cares about their order. Every type here is public purely to be reachable from the indexes in the parent package, and says so in its javadoc.

The shared Index base class, IndexFactory, and MetadataFilteredSearchExecutor stay in the index package itself. Mutable GenericCache and SparseCache implementations live under searchablestructure.cache.

Comparators

Comparator implementations live under com.uber.ussi.comparator, with the two pieces that only a comparator composes in sub-packages of their own:

• comparator.sequencedistance: the edit distances the gld and ngld comparators measure with, sharing the banded dynamic program in SequenceDistance.
• comparator.signaturegenerator: the MinHash and consistent weighted sampling generators the jaccard and ruzicka comparators draw signatures from.

Normalizers are separate, under com.uber.ussi.comparatornormalizer, because a namespace configures one independently of its comparator.

Generic Cache

GenericCache is mutable and supports insert, update, delete, kNN search, and minimum-similarity search. It scans all cached rows and applies metadata filters before scoring rows.

Sparse Cache

SparseCache is mutable and keeps inverted term lists in insertion order. It generates deduplicated candidates from query terms using unordered-prefix filtering, then scores candidates with the configured comparator. A metadata filter matching at most 1% of the cache uses a direct scan of those matching rows instead.

Sparse-cache searches only return rows sharing at least one non-discarded term with the query. High-popularity terms are discarded dynamically according to the configured one-sided confidence bound, and popular_term_discard_scope decides what that discard means; see Discarding Popular Terms. The complete stored records and inverted lists retain those terms, allowing the decisions to be reversed as the cache changes.

Generic Index

GenericIndex (in index.generic) is delete-only and uses sequential scan search over a snapshot of graduated rows. It supports metadata in-filtering and can participate in pre-filtering or post-filtering depending on configuration.

Dense Matrix Index

DenseMatrixIndex (in index.dense) is delete-only and stores dense vectors in a row-major float matrix. It supports only the l2 comparator. Rows must have empty terms and the same non-zero dimension.

For unfiltered all-row scoring, it computes matrix-vector dot products and then derives L2 distance from:

||query - row||^2 = ||query||^2 + ||row||^2 - 2 * dot(query, row)

The dense scorer tries to use OpenBLAS on supported Linux and macOS platforms. If OpenBLAS cannot be loaded, it falls back to the Java scorer. NearestNeighborSearchIndex.close() releases any native dense-matrix memory.

Term Index

TermIndex is a delete-only sparse index whose keys are the terms themselves, canonicalized. Every sparse index keeps inverted lists, so what sets this one apart is the source of its keys: a row's own terms, with nothing derived from them, which is why the terms a query and a candidate share determine their similarity exactly rather than bounding it.

Inverted lists are sorted by each row's comparator-specific unilateral value, enabling length filtering. Candidate traversal combines length, position, and unordered-prefix filtering while tightening the similarity threshold as the top-k heap fills. Either candidate generator can traverse these lists; see Sparse Candidate Generation.

Each row and each query must have non-empty terms and values arrays of equal length after canonicalization; a query and a row do not need to have the same number of terms as each other. Search only considers rows sharing at least one non-discarded term with the query. This is important for sparse L2: two disjoint sparse vectors can have a non-zero normalized L2 similarity, but term deliberately does not return such rows. Use generic when exhaustive scoring across disjoint sparse L2 records is required.

At build time, terms occurring in more than floor(numRows * max_fraction_ids_per_sparse_key) rows are discarded. The default fraction of 1.0 disables this behavior. See Discarding Popular Terms for what a discard means.

Sequence Index

SequenceIndex is a delete-only index over ordered sequences. An edit distance depends on the order the elements appear in, so it cannot be read off the elements a query and a row share. What those shared elements do give is a bound: two sequences within edit distance d have element multisets within L1 distance l1BoundFactor * d of each other, where the factor is 2.0 for levenshtein and damerau_levenshtein and 1.0 for lcs. A substitution takes one element out of a multiset and puts another in, moving two, while an insertion or a deletion moves one, which is why forbidding substitution halves the factor and makes lcs the more selective choice for candidate generation. A row sharing too few elements with the query, disregarding their order, therefore cannot be close enough in order either.

Each row travels through a search in two forms. The inverted lists are keyed by the distinct elements of the row's multiset and carry how many times each occurs, which is what length and prefix filtering prune on. The comparator then verifies each surviving candidate against the ordered sequences, running the banded dynamic program under the budget the active similarity threshold allows.

Each row and each query must have non-empty terms and an empty values array. A query and a row do not need to be the same length as each other. Search only considers rows sharing at least one non-discarded element with the query.

Signature Index

SignatureIndex replaces original terms as inverted-list keys with 270 deterministic, similarity-preserving signatures per row. Jaccard uses MinHash; Ruzicka uses the configured CWS variant. Signature collisions generate candidates approximately, but candidates are scored using canonical terms and values, in whichever form the configured discard scope leaves them, not by comparing the signatures themselves.

Signature prefix filtering applies a generator-specific approximation safety margin: 0.1 for MinHash, I2CWS, ICWS, and SCWS, and 0.15 for PCWS. These margins broaden candidate generation but do not make the signature index exact.

Hybrid Sparse Index

SparseIndex combines a TermIndex and a SignatureIndex. During each index build, rows with at most 270 terms go to the term child and rows with more than 270 terms go to the signature child. The configured length range may be entirely below, entirely above, or span this internal boundary.

Queries search the child matching the query length first. Jaccard's cardinality bounds can skip the other child when no row on that side can reach the active similarity threshold. Ruzicka and popularity-filtered searches conservatively search both children because term count alone cannot prove that one side is irrelevant. Results from the searched children are merged and limited by maxNumSimilarities.

The hybrid requires a signature-capable Jaccard or Ruzicka comparator.

Discarding Popular Terms

A term that occurs in most rows generates most of the index as candidates without narrowing anything down, so both the sparse cache and the sparse indexes can discard the terms above a configured popularity. What a discard means is popular_term_discard_scope, and the two settings differ in which half of the answer stays exact rather than in how aggressive they are.

Under the default candidates_and_verification, a discarded term is absent from the inverted lists and from the records the comparator scores. A search reports the similarity between the records that remain once the popular terms are removed from both, and every row within the threshold of the query, measured that same way, is found. This redefines what the reported similarities mean, which is the right trade when the popular terms carry no signal worth reporting.

Under candidates_only, a discarded term is absent from the inverted lists only. A search reports the similarity between the records as supplied, including their discarded terms, which is the right trade when an application has to report an exact similarity on the original records but cannot pay to generate candidates from their popular terms. The cost is recall: candidate generation still prunes on the similarity measured without the discarded terms, and removing a shared term can only lower that measure, so a row within the threshold of the query can be pruned before verification ever scores it. How much is lost depends on how much of the similarity the discarded terms carried. This also rules out scoring a row from the conjunction accumulated over the inverted lists, since that conjunction can only report the similarity that excludes the discarded terms, so spars_merge verifies each candidate through the comparator under this scope.

Sparse Candidate Generation

The three sparse index types (term, signature, and hybrid sparse) build the same uni-sorted inverted lists but can traverse them with either of two candidate generators, selected per namespace with the sparse_candidate_generator index parameter. Both return identical results and honor every metadata filtering strategy; they differ only in how much work they do to get there.

spars is the default and is sparse-key-major. It visits the query's sparse keys cheapest first, narrows each key's inverted list to the rows that length filtering admits, and scores every surviving candidate with the comparator. Because it always scores through the comparator, it supports every sparse index type and every supported comparator.

spars_merge is row-major. One frontier spans all of the query's sparse keys and advances them in step, so every inverted-list entry belonging to a candidate row arrives together. That lets the generator accumulate the row's conjunction, which is the part of the similarity that the query and the row derive from the sparse keys they share, as it goes, and abandon the row as soon as no completion of it can reach the active similarity threshold. It trades a priority queue over the query's keys for the ability to prune a row mid-scan, which pays off when a query has many sparse keys and the threshold rejects most rows early.

When the sparse keys are exact terms, the inverted lists also carry each row's value at that key, so the accumulated conjunction is the row's exact similarity and no further comparison is needed. Signature keys carry no usable value, so over a signature index the merge generator scores each retained candidate with the comparator, exactly as the filtered scan does. The hybrid sparse index applies the generator independently to each child, so its term child scores from the conjunction while its signature child verifies.

A comparator opts into the merge generator by implementing its conjunction hooks. Jaccard, Ruzicka, and L2 all do, so spars_merge is available for every supported sparse comparator; the inverted-list values it needs are only materialized for the index types that read them.

Build and Test

bazel build //:src_main
bazel test //:test_main

Operational Notes

• The index is memory-only. The hosting platform remains the source of truth.

• TTL should be enforced by the hosting platform by calling delete(rowNum) when a row expires.

• Background cache graduation and index consolidation are internal maintenance tasks. Search results include active, graduating, and indexed rows while those tasks are in flight. Deletes that occur during a background build are recorded and replayed onto the new index at swap time, so deleted rows never reappear.

• Signature indexes use approximate candidate generation. Final scores are exact for the candidates that are found, but qualifying rows can be missed.

• High-popularity sparse-term filtering changes both candidate generation and comparison by removing the filtered terms from each query and row.

• The implementation favors correctness and simple integration for the current MVP. More specialized sparse or approximate indexes can be added behind the same cache/index factory interfaces.

Code of Conduct

This project follows the Uber Code of Conduct.

License

Apache License 2.0. See LICENSE.md.