Sketched Search: the Whole Pipeline as an Index

Searching with sketches always follows the same four steps. Encode the dataset. Index the codes. Retrieve more candidates than requested, under the cheap sketch distance. Re-score those candidates with the real distance. Written by hand it is a handful of lines – Projections.SketchedSearch exists because every one of those lines is a place to be silently wrong:

• encoding the query with a freshly fitted model instead of the dataset's, which produces codes that are not comparable with the stored ones;
• indexing the sketches under the original distance instead of distance(qs);
• forgetting the re-scoring pass and returning sketch distances as if they were real ones.

None of those raise an error. They return worse results, which is the hardest kind of bug to notice in an approximate search.

Using it

SketchedSearch is an ordinary AbstractSearchIndex: search and searchbatch work on it unchanged, and the identifiers it returns are indices into the original database, with true distances. Replacing one index by the other is therefore the whole experiment.

# SimilaritySearch v1.6
using SimilaritySearch
const P = SimilaritySearch.Projections

X = randn(Float32, 128, 5_000)
db = MatrixDatabase(X)
dist = Dist.SqL2()

model = P.gaussian(128, 256)                       # 256 hyperplanes
S = P.SketchedSearch(model, 4, dist, db; factor=8) # 4 bits each, 8x candidates before re-scoring

ctx = GenericContext()
q = randn(Float32, 128)
res = search(S, ctx, q, knnqueue(KnnSorted, 10))

for p in IdDistView(res)
    println("id=", p.id, "  distance=", p.dist)    # ids into `db`, distances under `dist`
end

Compare against the exact answer to see what the sketch stage costs:

# SimilaritySearch v1.6
using SimilaritySearch
const P = SimilaritySearch.Projections

X = randn(Float32, 128, 5_000)
db = MatrixDatabase(X)
dist = Dist.SqL2()
Q = MatrixDatabase(randn(Float32, 128, 30))
ctx = GenericContext()

gold, _ = searchbatch(ExhaustiveSearch(dist, db), ctx, Q, 10)

for factor in (1, 4, 16)
    S = P.SketchedSearch(P.gaussian(128, 256), 4, dist, db; factor)
    ids, _ = searchbatch(S, ctx, Q, 10)
    println("factor=", factor, "  recall=", macrorecall(gold, ids))
end

The knobs, and what each one trades

factor controls the recall. The sketch stage is fast but loses information, so it is asked for more candidates than needed. The exact distance then settles the final order among them. factor=1 disables the widening but still re-scores, so the distances stay exact even then.

What it is not

SketchedSearch is built once over a fixed database and is not incremental. The quantization range of its encoder is fitted on exactly the data given to the constructor. For the hyperplane models, the anchors are fitted the same way. Growing the collection therefore requires rebuilding the index, and not pushing into it. For a growing collection, bootstrap a SearchGraph from sketches instead (see Multi-Bit Sketches) and keep inserting into the graph.

The re-scoring pass is also what separates it from the asymmetric graph of the previous section. In that graph the correction happens inside the distance while the graph navigates, when the estimator has a correction at all. No pass over the raw data follows the search.

This closes the tutorial series. Sketches are the last of the compression strategies; for queries bounded by a distance rather than by a count, see Radius Queries, and for the full API, the reference.