"cosine",
"jaccard" or "hellinger" metrics could give
incorrect results if maximally-dissimilar items were in the nearest
neighbors. Thank you to Maciej
Beręsewicz for the report (https://github.com/jlmelville/rnndescent/issues/14).nnd_knn and rnnd_build:
weight_by_degree. If set to TRUE, then the
candidate list in nearest neighbor descent is weighted in favor of
low-degree items, which should make for a more diverse local join. There
is a minor increase in computation but also a minor increase in
accuracy.rnnd_build generated an error when preparing the search
graph for some metrics (notably cosine and
jaccard).prepare_search_graph:
use_alt_metric. This behaves like the existing
use_alt_metric parameters in other functions and may speed
up the index preparation step in e.g. rnnd_build.rnnd_build and
prepare_search_graph: prune_reverse. If set to
TRUE the reverse graph will be pruned using the
pruning_degree_multiplier parameter before any
diversification. This can help prevent an excessive amount of time being
spent in the diversification step in the case where an item has a large
number of neighbors (in the reverse graph this can be as large as the
number of items in the dataset). Pruning of the merged graph still
occurs, so this is an additional pruning step. This should have little
effect on search results, but for backwards compatibility, the default
is FALSE.CRAN resubmission to fix lingering UBSAN errors.
Initial CRAN submission.
rnnd_build now always prepares the search graph.rnnd_prepare function has been removed. The option
to not prepare the search graph during index building only made sense if
you were only interested in the k-nearest neighbor graph. Now that
rnnd_knn exists for that purpose (see below), the logic of
index building has been substantially simplified.nn_to_sparse function has been removed.merge_knn function has been removed, and
merge_knnl has been renamed to merge_knn. If
you were running e.g. merge_knn(nn1, nn2), you must now use
merge_knn(list(nn1, nn2)). Also the parameter
nn_graphs has been renamed graphs.rnnd_knn. Behaves a lot like
rnnd_build, but only returns the knn graph with no
index built. The index can be very large in size for high dimensional or
large datasets, so this function is useful if you only care about the
knn graph and won’t ever want to query new data.neighbor_overlap. Measures the overlap of
two knn graphs via their shared indices. A similar function was used
extensively in some vignettes so it may have sufficient utility to be
useful to others.rnnd_query and
graph_knn_query: max_search_fraction. This
parameter controls the maximum number of nodes that can be searched
during querying. If the number of nodes searched exceeds this fraction
of the total number of nodes in the graph, the search will be
terminated. This can be used in combination with epsilon to
avoid excessive search times.spearmanr distance has been fixed.n_threads = 0,
progress/interrupt monitoring was not occurring.init
parameter of rnnd_query.rnnd_query: if verbose = TRUE, a summary
of the min, max and average number of distance queries will be logged.
This can help tune epsilon and
max_search_fraction.local_scale_nn has been removed, for similar
reasons to the removal of the standalone distance functions. It remains
in the localscale branch of the github repo.prepare_search_graph is
now transposed. This prevents having to repeatedly transpose inside
every call to graph_knn_query if multiple queries are being
made. You will need to either regenerate any saved search graphs or
transpose them with Matrix::t(search_graph).rnnd_build, rnnd_query and
rnnd_prepare. These functions streamline the process of
building a k-nearest neighbor graph, preparing a search graph and
querying it.The bhamming metric no longer exists as a
specialized metric. Instead, if you pass a logical matrix
to data, reference or query
parameter (depending on the function) and specify
metric = "hamming" you will automatically get the
binary-specific version of the hamming metric.
The hamming and bhamming metrics are
now normalized with respect to the number of features, to be consistent
with the other binary-style metrics (and PyNNDescent). If you need the
old distances, multiply the distance matrix by the number of columns,
e.g. do something like:
res <- brute_force_knn(X, metric = "hamming")
res$dist <- res$dist * ncol(X)The metric l2sqr has been renamed
sqeuclidean to be consistent with PyNNDescent.
metric parameter now accepts a
much larger number of metrics. See the rdoc for the full list of
supported metrics. Currently, most of the metrics from PyNNDescent which
don’t require extra parameters are supported. The number of specialized
binary metrics has also been expanded.rpf_knn and rpf_build:
max_tree_depth this controls the depth of the tree and was
set to 100 internally. This default has been doubled to 200 and can now
be user-controlled. If verbose = TRUE and the largest leaf
in the forest exceeds the leaf_size parameter, a message
warning you about this will be logged and indicates that the maximum
tree depth has been exceeded. Increasing max_tree_depth may
not be the answer: it’s more likely there is something unusual about the
distribution of the distances in your dataset and a random
initialization might be a better use of your time.dgCMatrix to the
data, reference or query
parameters where you would usually use a dense matrix or data frame.
cosine, euclidean, manhattan,
hamming and correlation are all available, but
alternative versions in the dense case,
e.g. cosine-preprocess or the binary-specific
bhamming for dense data is not.init option for graph_knn_query: you
can now pass an RP forest and initialize with that, e.g. from
rpf_build, or by setting ret_forest = TRUE on
nnd_knn or rpf_knn. You may want to cut down
the size of the forest used for initialization with
rpf_filter first, though (a single tree may be enough).
This will also use the metric data in the forest, so setting
metric (or use_alt_metric) in the function
itself will be ignored.prepare_search_graph or to
graph_knn_query contains missing data, this will no longer
cause an error (it still might not be the best idea though).rpf_knn. Calculates the approximate
k-nearest neighbors using a random partition forest.rpf_build. Builds a random partition
forest.rpf_knn_query. Queries a random partition
forest (built with rpf_build to find the approximate
nearest neighbors for the query points.rpf_filter. Retains only the best
“scoring” trees in a forest, where each tree is scored based on how well
it reproduces a given knn.nnd_knn:
init = "tree". Uses the RP Forest initialization
method.nnd_knn: ret_forest.
Returns the search forest used if init = "tree" so it can
be used for future searching or filtering.nnd_knn: init_opts.
Options that can be passed to the RP forest initialization (same as in
rpf_knn).nnd_knn with
n_threads > 0 was reporting double the actual number of
iterations. This made the progress bar way too optimistic.metric: "cosine" and
"correlation" have been renamed
"cosine-preprocess" and
"correlation-preprocess" respectively. This reflects that
they do some preprocessing of the data up front to make subsequent
distance calculations faster. I have endeavored to avoid unnecessary
allocations or copying in this preprocessing, but there is still a
chance of more memory usage.cosine and correlation metrics are
still available as an option, but now use an implementation that doesn’t
do any preprocessing. The preprocessing and non-preprocessing version
should give the same numerical results, give or take some minor
numerical differences, but when the distance should be zero, the
preprocessing versions may give values which are slightly different from
zero (e.g. 1e-7).correlation_distance,
cosine_distance, euclidean_distance,
hamming_distance, l2sqr_distance,
manhattan_distance for calculating the distance between two
vectors, which may be useful for more arbitrary distance calculations
than the nearest neighbor routines here, although they won’t be as
efficient (they do call the same C++ code, though). The cosine and
correlation calculations here use the non-preprocessing
implementations.hamming metric to a standard definition. The
old implementation of hamming metric which worked on binary
data only was renamed into bhamming. (contributed by Vitalie Spinu)obs has been added to most functions: set
obs = "C" and you can pass the input data in
column-oriented format.random_knn function used to always return each item
as its own neighbor, so that only n_nbrs - 1 of the
returned neighbors were actually selected at random. Even I forgot it
did that and it doesn’t make a lot of sense, so now you really do just
get back n_nbrs random selections.init
parameter to nnd_knn or graph_knn_query:
previously, if k was specified and larger than the number
of neighbors included in init, this gave an error. Now,
init will be augmented with random neighbors to reach the
desired k. This could be useful as a way to “restart” a
neighbor search from a better-than-random location if k has
been found to have been too small initially. Note that the random
selection does not take into account the identities of the already
chosen neighbors, so duplicates may be included in the augmented result,
which will reduce the effective size of the initialized number of
neighbors.block_size and grain_size
parameters from functions. These were related to the amount of work done
per thread, but it’s not obvious to an outside user how to set
these.verbose = TRUE) and respond to
user-requested cancellation.nnd_knn_query has been renamed to
graph_knn_query and now more closely follows the current
pynndescent graph search method (including backtracking search).prepare_search_graph for preparing a
search graph from a neighbor graph for use in
graph_knn_query, by using reverse nearest neighbors,
occlusion pruning and truncation.graph_knn_query.There was a major rewrite of the internal organization of the C++ to be less R-specific.
The license for rnndescent has changed from GPLv3 to GPLv3 or later.
"correlation". This is (1 minus) the
Pearson correlation.k_occur which counts the k-occurrences of
each item in the idx matrix, which is the number of times
an item appears in the k-nearest neighbor list in the dataset. The
distribution of the k-occurrences can be used to diagnose the “hubness”
of a dataset. Items with a large k-occurrence (>> k, e.g. 10k),
may indicate low accuracy of the approximate nearest neighbor
result.To avoid undefined behavior issues, rnndescent now uses an internal
implementation of RcppParallel’s parallelFor loop that
works with std::thread and does not load Intel’s TBB
library.
dqrng sample routines from inside a thread, despite it
clearly using the R API extensively. It’s not ok and causes lots of
crashes. There is now a re-implementation of dqrng’s sample
routines using plain std::vectors in
src/rnn_sample.h. That file is licensed under the AGPL
(rnndescent as a whole remains GPL3).merge_knn, to combine two nearest
neighbor graphs. Useful for combining the results of multiple runs of
nnd_knn or random_knn. Also,
merge_knnl, which operates on a list of multiple neighbor
graphs, and can provide a speed up over merge_knn if you
don’t mind storing multiple graphs in memory at once.nnd_knn with
n_threads > 1 and random_knn with
n_threads > 1 and
order_by_distance = TRUE.nnd_knn with
n_threads > 1 due to the use of a mutex pool.Mainly an internal clean-up to reduce duplication.
nnd_knn and nnd_knn_query use
the same progress bar as the brute force and random neighbor functions.
Bring back the old per-iteration logging that also showed the current
distance sum of the knn with the progress = "dist"
option.random_knn and random_knn_query, when
order_by_distance = TRUE and n_threads > 0,
the final sorting of the knn graph will be multi-threaded.n_threads > 0.nnd_knn_query being the most useful, but
brute_force_knn_query and random_knn_query are
also available. This allows for query data to search
reference data, i.e. the returned indices and distances are
relative to the reference data, not any other member of
query. These methods are also available in multi-threaded
mode, and nnd_knn_query has a low and high memory
version.l2 metric has been renamed to l2sqr to
more accurately reflect what it is: the square of the L2 (Euclidean)
metric.use_alt_metric. Set to FALSE if
you don’t want alternative, faster metrics (which keep the distance
ordering of metric) to be used in internal calculations.
Currently only applies to metric = "euclidean", where the
squared Euclidean distance is used internally. Only worth setting this
to FALSE if you think the alternative is causing numerical
issues (which is a bug, so please report it!).block_size for parallel methods, which
determines the amount of work done in parallel before checking for user
interrupt request and updating any progress.random_knn now returns its results in sorted order. You
can turn this off with order_distances = FALSE, if you
don’t need the sorting (e.g. you are using the results as input to
something else).brute_force and
random methods should now be correct.brute_force_knn.random_knn.verbose = TRUE.fast_rand option has been removed, as it only applied
to single-threading, and had a negligible effect.Also, a number of changes inspired by recent work in https://github.com/lmcinnes/pynndescent:
rho sampling parameter has been removed. The size
of the candidates (general neighbors) list is now controlled entirely by
max_candidates.max_candidates has been reduced to 20.use_set logical flag has been replaced by
low_memory, which has the opposite meaning. It now also
works when using multiple threads. While it follows the pynndescent
implementation, it’s still experimental, so
low_memory = TRUE by default for the moment.low_memory = FALSE implementation for
n_threads = 0 (originally equivalent to
use_set = TRUE) is faster.block_size, which balances interleaving
of queuing updates versus applying them to the current graph.