Public Interface

nndescent(GraphT::Type{ApproximateKNNGraph}, data, n_neighbors, metric; kwargs...)

Find the approximate neighbors of each point in data by iteratively refining a KNN graph of type GraphT. Returns the final KNN graph.

Keyword Arguments

• max_iters = 10: Limits the number of iterations to refine candidate

nearest neighbors. Higher values trade off speed for accuracy. Note that graph construction may terminate early if little progress is being made.

• sample_rate = 1: The sample rate for calculating local joins

around each point. Lower values trade off accuracy for speed.

• precision = 1e-3: The threshold for early termination,

where precision is "roughly the fraction of true kNN allowed to be missed due to early termination". Lower values take longer but return more accurate results.

nndescent(::Type{<:ApproximateKNNGraph}, data::AbstractMatrix, n_neighbors::Integer, metric::PreMetric; kwargs...)

nndescent(data, n_neighbors, metric; kwargs...)

Do nndescent using HeapKNNGraph as the KNN Graph type.

search(graph, queries, n_neighbors; max_candidates) -> indices, distances

Search the kNN graph for the nearest neighbors of the points in queries. max_candidates controls how large the candidate queue should be (min n_neighbors); larger values increase accuracy at the cost of speed.

local_join!(graph; kwargs...)

Perform a local join on each vertex v's neighborhood N[v] in graph. Given vertex v and its neighbors N[v], compute the similarity graph.metric(p, q) for each pair p, q ∈ N[v] and update N[q] and N[p].

This mutates graph in-place and returns a nonnegative integer indicating how many neighbor updates took place during the local join.

ApproximateKNNGraph{V, U, D, M} subtypes are weighted, directed graphs where each vertex has exactly k forward edges with weights of type U.

D is the type of the dataset corresponding to this graph, and M is a Distances.PreMetric with result type matching U.

HeapKNNGraph{V, U, D, M}

A weighted, directed graph representing an approximate k-nearest neighbors graph using binary max heaps to store each vertex's forward edges, allowing for efficient updates of the candidate neighbors.

LockHeapKNNGraph - uses locks to synchronize the heaps that store the underlying graph edge data. The heaps themselves are not thread-safe.

knn_diameter(g::ApproximateKNNGraph{V}, v::V)

Compute the diameter of the ball centered on v that covers all of vs approximate k-nearest neighbors.

knn_diameter(graph, v) -> diameter

Return the diameter of the set of KNNs of vertex v.

knn_matrices(graph) -> indices, distances

Return the indices and distances of the approximate KNNs as dense matrices where indices[j, i] and distances[j, i] are the index of and distance to node i's jth nearest neighbor, respectively.

edge_indices(graph) -> CartesianIndices

Return the indices of the KNNs for each node v as tuples (v, i). To be used with node_edge(graph, v, i).

node_edge(graph, v, i) -> edge

Return the ith outgoing edge from node v. No ordering of the edges is guaranteed; in particular, node_edge(graph, v, 1) is not guaranteed to be the edge to v's nearest neighbor.

node_edges(graph::LockHeapKNNGraph, i) -> edges

Return all the outgoing edges from node i in an arbitrary order. Thread-safe.

node_edges(graph, v) -> edges

Return all the outgoing edges from node v in an arbitrary order.

update_flag!(g::LockHeapKNNGraph, i, j, flag)

Update the flag of the edge at the given indices. Since the flags don't influence the edge ordering, this can't invalidate the heap invariant. Uses locks to ensure thread safety.

update_flag!(graph, v, i, new_flag)

Update the flag of node vs ith outgoing edge. Returns the new edge. Note that since the flags don't influence the edge ordering, this can't invalidate the heap invariant.