Skip to content

LearnIndex & store

k-nearest neighbors

kNN · k-NN

The k stored vectors closest to a query under a chosen distance; in retrieval, the top-k passages a vector search returns.

In DocSlurpGlossary entry

On this page

The k-nearest neighbors (kNN) of a query are the k stored items closest to it under a chosen distance. In retrieval, a vector search for the top 10 chunks is a 10-nearest-neighbor query: embed the question, then find the 10 chunk vectors at the smallest distance.

The exact algorithm is short. Measure the distance from the query to every stored vector, sort, keep the first k. With three stored vectors at distances 0.31, 0.12 and 0.48 from the query, the 2-nearest neighbors are the ones at 0.12 and 0.31. The answer depends on the distance: Euclidean distance and cosine similarity can rank the same vectors differently unless the vectors are normalized.

(In machine learning, kNN also names a classifier that labels a point by majority vote of its neighbors. Retrieval uses only the neighbor-finding part.)

The gotcha

Exact kNN costs one distance computation per stored vector per query, so its cost grows linearly with the collection. That is why large systems use approximate nearest neighbor search, which returns nearly the k nearest. Exact kNN remains the reference: measure an index’s recall by comparing its results with exact kNN on sample queries.

Filters change the answer too. “The 10 nearest chunks from travel-desk-guide.pdf” is not the same as “the 10 nearest chunks, then keep those from travel-desk-guide.pdf”, which may leave none. DocSlurp applies the document-scope filter before choosing neighbors, and scores each hit as 1 / (1 + distance) from its L2 distance.

In DocSlurp

In DocSlurp

Each vector search asks LanceDB for the limit nearest chunks by L2 distance, filtered to the documents in scope before neighbors are chosen, and converts distance to a score as 1 / (1 + distance) (core/server/src/search/lancedb.ts).

Sources

Jump to