Nearest neighbour searches in manifoldsR
kNN graphs are the core of different manifold learning methods. This vignette gives you an intro in the provided methods, plus the advantages and disadvantages of the different methods. The wrappers can be also used to avoid recomputing the kNN graph if you wish to test different parameters.
# number neighbours
k <- 10L
# number samples
n_samples <- 1000LSynthetic data
We will generate some synthetic data and test the different methods out.
cluster_data <- manifold_synthetic_data(
type = "cluster",
n_samples = n_samples
)Exhaustive search
This is simplest search type… It uses an exhaustive search index under the hood with SIMD acceleration over a flat structure for cache locality. On small data sets, this one might in times be even faster than the approximate searches we will discuss subsequently.
exhaustive <- generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "exhaustive"
)
exhaustive
#> NearestNeighbours
#> n_samples: 1000
#> k_neighbours: 10There is a set of getters for these classes, see below. An important note is that the indices are 0-based (from Rust), so if you wish to use them in R, you need to be aware of this!
# flat representation of the indices
indices_flat <- get_idx_flat(exhaustive)
# as N x idx nearest neighbours matrix
indices_mat <- get_idx_mat(exhaustive)The distances can also be extracted easily:
# flat representation of the distances
dist_flat <- get_dist_flat(exhaustive)
# as N x idx nearest neighbours matrix
dist_mat <- get_dist_mat(exhaustive)An alternative, exact version is the KmKnn (k-means for k-nearest neighbour). It leverages k-means and triangle inequality to reduce the number of searches - a (very) fast, exact index that works well on low-dimensional data that has strong structure.
kmknn <- generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "kmknn"
)
kmknn
#> NearestNeighbours
#> n_samples: 1000
#> k_neighbours: 10
all(get_idx_flat(kmknn) == get_idx_flat(exhaustive))
#> [1] TRUEApproximate searches
This package is designed to deal with large datasets and leverages under the hood the ann-search-rs crate which provides various approximate nearest neighbour searches. The 4 methods exposed in this package are (+ the exhaustive version above):
| Method | Features | Class | Use case |
|---|---|---|---|
| BallTree | Simple method, good for small data sets (≤ 100,000) | Tree-based | Small data sets, small dimensionality |
| Annoy | Classic in single cell, scales well to data sets of up to 500,000 | Tree-based | Large data sets, small dimensionality |
| HNSW | Powerful on large datasets (≥ 500,000), slightly slower index build type, fast queries. The implementation here uses a benign race condition during index building. | Graph-based | Large data sets, small to large dimensionality |
| NNDescent | Another graph-based version, good all-rounder when certain sizes are reached (≥ 100,000) | Graph-based | Medium data sets, small to large dimensionality |
| IVF | A fast cluster-based index powering libraries like FAISS. | Cluster-based | Large data sets, any dimensionality. You can squeeze out aggressively speed with the n_probe parameter if need be. Be careful to set n_list pending your data structure. If you have few well defined data clusters, it is better to set it lower for this method. |
manifoldsR defaults to kMkNN, but you can play around with the parameters & methods. The package was written with massive scale in mind, but if you are looking at smaller data sets with clear structure and low dimensionality (like in this vignettes), kMkNN does the job (fast). If you have high dimensional data and/or massive amounts of samples, some of the other methods will shine.
Speed
Let’s just have a look on how the different kNN methods perform on different sizes.
cluster_data <- manifold_synthetic_data(
type = "cluster",
n_samples = 1000L
)
microbenchmark::microbenchmark(
exhaustive = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "exhaustive",
.verbose = FALSE
)
},
kmknn = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "kmknn",
.verbose = FALSE
)
},
annoy = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "annoy",
.verbose = FALSE
)
},
hnsw = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "hnsw",
.verbose = FALSE
)
},
balltree = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "balltree",
.verbose = FALSE
)
},
nndescent = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "nndescent",
.verbose = FALSE
)
},
ivf = {
generate_knn_graph(
data = cluster_data$data,
k = k,
knn_method = "ivf",
nn_params = params_nn(),
.verbose = FALSE
)
},
times = 1L # single comparison for speed
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> exhaustive 2.953389 2.953389 2.953389 2.953389 2.953389 2.953389 1
#> kmknn 4.003242 4.003242 4.003242 4.003242 4.003242 4.003242 1
#> annoy 19.609178 19.609178 19.609178 19.609178 19.609178 19.609178 1
#> hnsw 21.197227 21.197227 21.197227 21.197227 21.197227 21.197227 1
#> balltree 2.566587 2.566587 2.566587 2.566587 2.566587 2.566587 1
#> nndescent 5.792088 5.792088 5.792088 5.792088 5.792088 5.792088 1
#> ivf 4.048349 4.048349 4.048349 4.048349 4.048349 4.048349 1On small datasets, the exhaustive search beats everything. We need to build the indices in the other methods, a cost that only makes sense when we have sufficient samples to do this. Otherwise, modern CPUs with SIMD can do the necessary O(N^2) in no time on smaller datasets. What about 50k cells?
benchmark_data <- manifold_synthetic_data(
type = "cluster",
n_samples = 50000L
)
microbenchmark::microbenchmark(
exhaustive = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "exhaustive",
.verbose = FALSE
)
},
kmknn = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "kmknn",
.verbose = FALSE
)
},
annoy = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "annoy",
.verbose = FALSE
)
},
hnsw = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "hnsw",
.verbose = FALSE
)
},
balltree = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "balltree",
.verbose = FALSE
)
},
nndescent = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "nndescent",
.verbose = FALSE
)
},
ivf = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "ivf",
nn_params = params_nn(n_probes = 25L),
.verbose = FALSE
)
},
times = 1L # single comparison for speed
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> exhaustive 3080.5213 3080.5213 3080.5213 3080.5213 3080.5213 3080.5213 1
#> kmknn 940.1250 940.1250 940.1250 940.1250 940.1250 940.1250 1
#> annoy 2329.5098 2329.5098 2329.5098 2329.5098 2329.5098 2329.5098 1
#> hnsw 2458.5019 2458.5019 2458.5019 2458.5019 2458.5019 2458.5019 1
#> balltree 705.1398 705.1398 705.1398 705.1398 705.1398 705.1398 1
#> nndescent 299.2266 299.2266 299.2266 299.2266 299.2266 299.2266 1
#> ivf 828.0629 828.0629 828.0629 828.0629 828.0629 828.0629 1We start observing the first pattern, that the approximate nearest neighbour searches are faster than the exhaustive search. The delta becomes more pronounced with more samples:
benchmark_data <- manifold_synthetic_data(
type = "cluster",
n_samples = 100000L
)
# this will take some time...
microbenchmark::microbenchmark(
exhaustive = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "exhaustive",
.verbose = FALSE
)
},
kmknn = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "kmknn",
.verbose = FALSE
)
},
annoy = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "annoy",
.verbose = FALSE
)
},
hnsw = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "hnsw",
.verbose = FALSE
)
},
balltree = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "balltree",
.verbose = FALSE
)
},
nndescent = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "nndescent",
.verbose = FALSE
)
},
ivf = {
generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "ivf",
nn_params = params_nn(n_probes = 25L),
.verbose = FALSE
)
},
times = 1L # single comparison for speed
)
#> Unit: milliseconds
#> expr min lq mean median uq max
#> exhaustive 11857.1801 11857.1801 11857.1801 11857.1801 11857.1801 11857.1801
#> kmknn 3036.9877 3036.9877 3036.9877 3036.9877 3036.9877 3036.9877
#> annoy 5785.3470 5785.3470 5785.3470 5785.3470 5785.3470 5785.3470
#> hnsw 6220.8212 6220.8212 6220.8212 6220.8212 6220.8212 6220.8212
#> balltree 2660.1198 2660.1198 2660.1198 2660.1198 2660.1198 2660.1198
#> nndescent 728.1448 728.1448 728.1448 728.1448 728.1448 728.1448
#> ivf 2197.8121 2197.8121 2197.8121 2197.8121 2197.8121 2197.8121
#> neval
#> 1
#> 1
#> 1
#> 1
#> 1
#> 1
#> 1Precision
In the end, these are approximate methods. So, we need to understand how good they are at recovering the true neighbours. Two metrics:
-
Recall@k: the fraction of the truekneighbours that the method found, regardless of order. - Mean distance ratio: distance to the approximate neighbour divided by the distance to the true neighbour at the same rank, averaged over everything. 1.0 means perfect. It tells you how wrong the misses are.
Let’s have a look at 25k samples:
samples <- 25000L
benchmark_data <- manifold_synthetic_data(
type = "cluster",
n_samples = samples
)
exhaustive <- generate_knn_graph(
data = benchmark_data$data,
k = k,
knn_method = "exhaustive",
.verbose = FALSE
)
true_idx <- get_idx_mat(exhaustive)
true_dist <- get_dist_mat(exhaustive)
indices <- c("hnsw", "annoy", "nndescent", "balltree", "ivf", "kmknn")
precision <- purrr::map(indices, \(idx) {
knn_i <- generate_knn_graph(
data = benchmark_data$data,
k = k,
nn_params = params_nn(n_probes = 25L),
knn_method = idx,
.verbose = FALSE
)
idx_i <- get_idx_mat(knn_i)
hits <- purrr::map_int(seq_len(samples), \(i) {
length(intersect(true_idx[i, ], idx_i[i, ]))
})
data.frame(
method = idx,
recall = sum(hits) / (k * samples),
dist_ratio = mean(get_dist_mat(knn_i) / true_dist)
)
})
knitr::kable(
do.call(rbind, precision),
digits = 4,
col.names = c("Method", "Recall@k", "Mean distance ratio")
)| Method | Recall@k | Mean distance ratio |
|---|---|---|
| hnsw | 0.9998 | 1.0000 |
| annoy | 1.0000 | 1.0000 |
| nndescent | 0.9651 | 1.0011 |
| balltree | 0.9942 | 1.0002 |
| ivf | 0.9920 | 1.0003 |
| kmknn | 1.0000 | 1.0000 |
NNDescent has the lowest recall here, but the distance ratio tells the real story: the neighbours it misses are basically as close as the true ones. The synthetic data has very tight clusters, so plenty of points sit at near identical distances and swapping one for another costs nothing. For manifold learning that is exactly the kind of miss you don’t care about. If you wish to understand more how these methods work, how they compare, etc., please check this out.
