Embedding Nearest Neighbours

What it replaces, and where it stops. This is the surface that lets an RDF project drop the pgvector it kept beside its triple store for nearest-neighbour search: ?neighbour <space> ( ?seed k ?distance ) answered in-process, exact top-k under the metric the artifact declares, and byte-identical natively and on wasm32. It is an exact scan — every candidate scored, no pruning, no approximate index — bounded by a caller-supplied KnnGuard, under three metrics (cosine, negative dot, squared Euclidean), over a PURREMB embedding space. PurRDF computes no embeddings and runs no ANN payload: the vectors come from a PURREMB artifact the caller fills, and PurRDF writes that carrier itself (EmbeddingBuilder in memory, EmbeddingStreamWriter streaming — Rust only) and opens it fail-closed; the model that produced the vectors is the caller’s.

The PURREMB layer in purrdf-core (see Deterministic embedding companions and docs/PURREMB.md) stores RDF-1.2-addressable vectors, a declared distance metric, and tamper-evident guards binding third-party index payloads to the exact matrix they were built over. It deliberately does not rank anything — ranking is a query operation and PURREMB is an artifact format. The knn module of purrdf-sparql-eval is that query operation, exposed through the property-function seam.

The call shape

PREFIX knn: <https://example.org/space/>
PREFIX d:   <https://example.org/d/>

SELECT ?neighbour ?distance WHERE {
  ?neighbour knn:points ( d:a 3 ?distance )
}

Four flattened positions — one on the subject side, three on the object side:

The ranked-search mode is fbbf: the seed and k are inputs the relation cannot enumerate, while ?neighbour and ?distance may each be bound or free. k accepts any integer-derived datatype (xsd:integer, xsd:int, xsd:long, xsd:nonNegativeInteger, …); k = 0 is a valid request for zero neighbours. A seed with no vector in the space is an empty answer, not an abort — otherwise every query ranging a seed over partly-embedded terms would die. A second mode, bbff, binds the neighbour and seed while leaving k free: it asks whether the space holds that neighbour, without ranking it. Binding k always selects ranked search, even when the neighbour is bound.

PurRDF mints no IRI for this

The predicate is the caller’s, and it is how a query names a space: a host builds one EmbeddingSpace per (artifact, target set, vector space) triple it wants queryable and registers an EmbeddingKnnRelation over it under whatever IRI its own vocabulary uses. There is no default IRI and no fallback space. Registering one relation per space — rather than one relation taking a space IRI as an argument — is what lets the planner read an honest row bound off the space that will actually be searched.

use std::sync::Arc;
use purrdf::sparql::{EmbeddingKnnRelation, EmbeddingSpace, KnnGuard, PropertyFunctionRegistry};

// The guard is caller-supplied configuration with no default: the largest
// space one invocation may scan, and the largest `k` it may request.
let guard = KnnGuard::new(/* max_candidates */ 100_000, /* max_neighbours */ 64)?;

// `bindings` names the RDF term each PURREMB row stands for. A row with no
// term is a construction-time refusal, not a skipped row — a top-k over a
// silently smaller candidate set would be the top-k of a subset.
let space = EmbeddingSpace::from_artifact(
    &purremb_bytes, target_set_id, vector_space_id, bindings, guard,
)?;

let mut registry = PropertyFunctionRegistry::new();
registry.register(
    "https://example.org/space/points".to_owned(),
    Arc::new(EmbeddingKnnRelation::new(Arc::new(space))),
);

The registry then reaches the engine through an ExtensionEnv (ExtensionEnv::over_relations, handed to the query with QueryOptions::with_env) exactly as on the full-text page. This is a Rust-host seam.

Exact search, ordered under the declared metric

The search is exact: every candidate row is scored under the metric the space’s family contract declares (FamilyView::metric() — cosine or squared Euclidean disagree on real data, and a surface using one kernel for both fails the tests that pin them apart), and the k returned are the true k nearest. There is no candidate pruning anywhere. That is what lets the engine’s row-ceiling pushdown be sound here — emission order is rank order, so the first n rows are the n nearest for every n ≤ k — and what makes “ordered correctly” a property the module is tested for rather than a property of a tuning parameter.

Rank order is (distance ASC, row ASC). Row numbers are distinct, so the order is strict and total, and the tie-break is meaningful: a PURREMB target set is sorted and deduplicated by TargetId, a digest of canonical identity, so ascending row number is ascending canonical content order. Two artifacts built from the same content in opposite insertion orders answer byte for byte, serialized JSON included.

Binary64, in a pinned order

The workspace’s full-text ranked-retrieval surface uses no floating-point arithmetic, because BM25 needs a logarithm and IEEE-754 does not require ln to be correctly rounded. That reason does not transfer. A kNN kernel needs no transcendental — subtraction, multiplication, addition, division and square root are all correctly rounded — so binary64 gives the same cross-target guarantee here. docs/PURREMB.md fixes the artifact’s own folds normatively (“binary64, round-to-nearest ties-to-even, in the written order, without a fused multiply-add”), and the L2 norm is one of them, so the kNN surface uses purrdf_core’s normative norm fold rather than a copy of it. Fixed point would have introduced a quantization step the format does not have.

The two residual hazards are closed structurally. Every dot product and squared Euclidean sum follows one pinned law, purrdf_core::distance::Exact (binary64-lane16-tree-v1): sixteen binary64 lanes over the whole sixteen-element chunks, a fixed pairwise tree, then the remaining terms in ascending index, never split across workers. It is the same order on every target and dispatch path, and its independent lanes are what lets it vectorize without licensing any reordering (a test folds a vector whose lane-tree sum is 1 and whose sequential sums are 0, and pins which). Every product is bound to a named local before it is added, so no fused multiply-add can form, and a thread whose float environment flushes subnormals is refused by name. Distances are emitted as xsd:double, whose canonical lexical round-trips the exact bits — a rounded decimal would print two adjacent doubles alike and hide exactly the divergence this is about.

One limit, stated rather than hidden: cosine self-distance need not be exactly zero (dot(v, v) and |v|·|v| are two roundings of one real number). Do not assume zero self-distance; ranking follows the computed distance and the canonical row tie-break.

What a search costs

The governor’s earlier charge points priced a host relation by invocations driven and rows accepted. For a generator, neither is where the cost is: a scan over a million vectors returning five rows would have been priced like a six-row table scan. The relation therefore reports its internal work through PfCursor::take_work after every pull, and the engine spends one unit of fuel per reported unit — so the search charge follows the space size, not the rows returned, and a KnnGuard is what keeps both the charge and the planner’s row bound honest.

The design record — the four decisions that were not obvious and what fixed each — is docs/design/purrdf-embedding-knn.md.