Public Interface
Documentation for NearestNeighborDescent.jl
's public interface.
Contents
Index
NearestNeighborDescent.KNNGraphs.ApproximateKNNGraph
NearestNeighborDescent.KNNGraphs.HeapKNNGraph
NearestNeighborDescent.KNNGraphs.LockHeapKNNGraph
NearestNeighborDescent.KNNGraphs.edge_indices
NearestNeighborDescent.KNNGraphs.knn_diameter
NearestNeighborDescent.KNNGraphs.knn_matrices
NearestNeighborDescent.KNNGraphs.node_edge
NearestNeighborDescent.KNNGraphs.node_edges
NearestNeighborDescent.KNNGraphs.update_flag!
NearestNeighborDescent.local_join!
NearestNeighborDescent.nndescent
NearestNeighborDescent.search
Public Interface
NearestNeighborDescent.nndescent
— Functionnndescent(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.
NearestNeighborDescent.search
— Functionsearch(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.
NearestNeighborDescent.local_join!
— Functionlocal_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.
KNN Graphs Public Interface
NearestNeighborDescent.KNNGraphs.ApproximateKNNGraph
— TypeApproximateKNNGraph{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
.
NearestNeighborDescent.KNNGraphs.HeapKNNGraph
— TypeHeapKNNGraph{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.
NearestNeighborDescent.KNNGraphs.LockHeapKNNGraph
— TypeLockHeapKNNGraph - uses locks to synchronize the heaps that store the underlying graph edge data. The heaps themselves are not thread-safe.
NearestNeighborDescent.KNNGraphs.knn_diameter
— Functionknn_diameter(g::ApproximateKNNGraph{V}, v::V)
Compute the diameter of the ball centered on v
that covers all of v
s approximate k-nearest neighbors.
knn_diameter(graph, v) -> diameter
Return the diameter of the set of KNNs of vertex v
.
NearestNeighborDescent.KNNGraphs.knn_matrices
— Functionknn_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.
Missing docstring for flag
. Check Documenter's build log for details.
Missing docstring for weight
. Check Documenter's build log for details.
NearestNeighborDescent.KNNGraphs.edge_indices
— Functionedge_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)
.
NearestNeighborDescent.KNNGraphs.node_edge
— Functionnode_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.
NearestNeighborDescent.KNNGraphs.node_edges
— Functionnode_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.
NearestNeighborDescent.KNNGraphs.update_flag!
— Functionupdate_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 v
s 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.