Package 'rnndescent'

Matrix of n items to generate neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to return.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n query items, with observations in the rows and features in the columns. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The reference data must be passed in the same orientation as query. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Matrix of m reference items, with observations in the rows and features in the columns. The nearest neighbors to the queries are calculated from this data. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The query data must be passed in the same format and orientation as reference. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format.

Number of nearest neighbors to return.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input query and reference orientation stores each observation as a column (the orientation must be consistent). The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n query items, with observations in the rows and features in the columns. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The reference data must be passed in the same orientation as query. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Matrix of m reference items, with observations in the rows and features in the columns. The nearest neighbors to the queries are calculated from this data. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The query data must be passed in the same format and orientation as reference. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format.

Search graph of the reference data. A neighbor graph, such as that output from nnd_knn() can be used, but preferably a suitably prepared sparse search graph should be used, such as that output by prepare_search_graph().

Number of nearest neighbors to return. Optional if init is specified.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

Initial query neighbor graph to optimize. If not provided, k random neighbors are created. If provided, the input format must be one of:

1. A list containing:

   • idx an n by k matrix containing the nearest neighbor indices.

   • dist (optional) an n by k matrix containing the nearest neighbor distances.

   If k and init are specified as arguments to this function, and the number of neighbors provided in init is not equal to k then:

   • if k is smaller, only the k closest values in init are retained.

   • if k is larger, then random neighbors will be chosen to fill init to the size of k. Note that there is no checking if any of the random neighbors are duplicates of what is already in init so effectively fewer than k neighbors may be chosen for some observations under these circumstances.

   If the input distances are omitted, they will be calculated for you.

2. A random projection forest, such as that returned from rpf_build() or rpf_knn() with ret_forest = TRUE.

Controls trade-off between accuracy and search cost, as described by Iwasaki and Miyazaki (2018), by specifying a distance tolerance on whether to explore the neighbors of candidate points. The larger the value, the more neighbors will be searched. A value of 0.1 allows query-candidate distances to be 10% larger than the current most-distant neighbor of the query point, 0.2 means 20%, and so on. Suggested values are between 0-0.5, although this value is highly dependent on the distribution of distances in the dataset (higher dimensional data should choose a smaller cutoff). Too large a value of epsilon will result in the query search approaching brute force comparison. Use this parameter in conjunction with max_search_fraction and prepare_search_graph() to prevent excessive run time. Default is 0.1. If you set verbose = TRUE, statistics of the number of distance calculations will be logged which can help you tune epsilon.

Maximum fraction of the reference data to search. This is a value between 0 (search none of the reference data) and 1 (search all of the data if necessary). This works in conjunction with epsilon and will terminate the search early if the specified fraction of the reference data has been searched. Default is 1.

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path. If a search forest is used for initialization via the init parameter, then the metric is fetched from there and this setting is ignored.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input query and reference orientation stores each observation as a column (the orientation must be consistent). The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

integer matrix containing the nearest neighbor indices, integers labeled starting at 1. Note that the integer labels do not have to refer to the rows of idx, for example if the nearest neighbor result is from querying one set of objects with respect to another (for instance from running graph_knn_query()). You may also pass a nearest neighbor graph object (e.g. the output of running nnd_knn()), and the indices will be extracted from it, or a sparse matrix in the same format as that returned by prepare_search_graph().

The number of closest neighbors to use. Must be between 1 and the number of columns in idx. By default, all columns of idx are used. Ignored if idx is sparse.

logical indicating whether the label i in idx is considered to be a valid neighbor when found in row i. By default this is TRUE. This can be set to FALSE when the the labels in idx refer to the row indices of idx, as in the case of results from nnd_knn(). In this case you may not want to consider the trivial case of an object being a neighbor of itself. In all other cases leave this set to TRUE.

A list of nearest neighbor graphs to merge. Each item in the list should consist of a sub-list containing:

• idx an n by k matrix containing the k nearest neighbor indices.

• dist an n by k matrix containing k nearest neighbor distances. The number of neighbors can differ between graphs, but the merged result will have the same number of neighbors as the first graph in the list.

If TRUE then the graphs are treated as the result of a knn query, not a knn building process. Or: is the graph bipartite? This should be set to TRUE if nn_graphs are the results of using e.g. graph_knn_query() or random_knn_query(), and set to FALSE if these are the results of nnd_knn() or random_knn(). The difference is that if is_query = FALSE, if an index p is found in nn_graph1[i, ], i.e. p is a neighbor of i with distance d, then it is assumed that i is a neighbor of p with the same distance. If is_query = TRUE, then i and p are indexes into two different datasets and the symmetry does not hold. If you aren't sure what case applies to you, it's safe (but potentially inefficient) to set is_query = TRUE.

Number of threads to use.

If TRUE, log information to the console.

Indices of a nearest neighbor graph, i.e. a matrix of nearest neighbor indices. Can also be a list containing an idx element.

Indices of a nearest neighbor graph, i.e. a matrix of nearest neighbor indices. Can also be a list containing an idx element. This is considered to be the ground truth.

Number of neighbors to consider. If NULL, then the minimum of the number of neighbors in idx1 and idx2 is used.

If TRUE, also return a vector containing the per-item overlap.

Matrix of n items to generate neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to return. Optional if init is specified.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

Name of the initialization strategy or initial data neighbor graph to optimize. One of:

• "rand" random initialization (the default).

• "tree" use the random projection tree method of Dasgupta and Freund (2008).

• a pre-calculated neighbor graph. A list containing:

  • idx an n by k matrix containing the nearest neighbor indices.

  • dist (optional) an n by k matrix containing the nearest neighbor distances. If the input distances are omitted, they will be calculated for you.'

If k and init are specified as arguments to this function, and the number of neighbors provided in init is not equal to k then:

• if k is smaller, only the k closest values in init are retained.

• if k is larger, then random neighbors will be chosen to fill init to the size of k. Note that there is no checking if any of the random neighbors are duplicates of what is already in init so effectively fewer than k neighbors may be chosen for some observations under these circumstances.

a list containing arguments to pass to the random partition forest initialization. See rpf_knn() for possible arguments. To avoid inconsistences with the tree calculation and subsequent nearest neighbor descent optimization, if you attempt to provide a metric or use_alt_metric option in this list it will be ignored.

Number of iterations of nearest neighbor descent to carry out. By default, this will be chosen based on the number of observations in data.

Maximum number of candidate neighbors to try for each item in each iteration. Use relative to k to emulate the "rho" sampling parameter in the nearest neighbor descent paper. By default, this is set to k or 60, whichever is smaller.

The minimum relative change in the neighbor graph allowed before early stopping. Should be a value between 0 and 1. The smaller the value, the smaller the amount of progress between iterations is allowed. Default value of 0.001 means that at least 0.1% of the neighbor graph must be updated at each iteration.

If TRUE, use a lower memory, but more computationally expensive approach to index construction. If set to FALSE, you should see a noticeable speed improvement, especially when using a smaller number of threads, so this is worth trying if you have the memory to spare.

If TRUE, then candidates for the local join are weighted according to their in-degree, so that if there are more than max_candidates in a candidate list, candidates with a smaller degree are favored for retention. This prevents items with large numbers of edges crowding out other items and for high-dimensional data is likely to provide a small improvement in accuracy. Because this incurs a small extra cost of counting the degree of each node, and because it tends to delay early convergence, by default this is FALSE.

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

Number of threads to use.

If TRUE, log information to the console.

Determines the type of progress information logged if verbose = TRUE. Options are:

• "bar": a simple text progress bar.

• "dist": the sum of the distances in the approximate knn graph at the end of each iteration.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

If TRUE and init = "tree" then the RP forest used to initialize the nearest neighbors will be returned with the nearest neighbor data. See the Value section for details. The returned forest can be used as part of initializing the search for new data: see rpf_knn_query() and rpf_filter() for more details.

Matrix of n items, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

neighbor graph for data, a list containing:

• idx an n by k matrix containing the nearest neighbor indices of the data in data.

• dist an n by k matrix containing the nearest neighbor distances.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

the degree of diversification of the search graph by removing unnecessary edges through occlusion pruning. This should take a value between 0 (no diversification) and 1 (remove as many edges as possible) and is treated as the probability of a neighbor being removed if it is found to be an "occlusion". If item p and q, two members of the neighbor list of item i, are closer to each other than they are to i, then the nearer neighbor p is said to "occlude" q. It is likely that q will be in the neighbor list of p so there is no need to retain it in the neighbor list of i. You may also set this to NULL to skip any occlusion pruning. Note that occlusion pruning is carried out twice, once to the forward neighbors, and once to the reverse neighbors. Reducing this value will result in a more dense graph. This is similar to increasing the "alpha" parameter used by in the DiskAnn pruning method of Subramanya and co-workers (2014).

How strongly to truncate the final neighbor list for each item. The neighbor list of each item will be truncated to retain only the closest d neighbors, where d = k * pruning_degree_multiplier, and k is the original number of neighbors per item in graph. Roughly, values larger than 1 will keep all the nearest neighbors of an item, plus the given fraction of reverse neighbors (if they exist). For example, setting this to 1.5 will keep all the forward neighbors and then half as many of the reverse neighbors, although exactly which neighbors are retained is also dependent on any occlusion pruning that occurs. Set this to NULL to skip this step.

If TRUE, prune the reverse neighbors of each item before the reverse graph diversification step using pruning_degree_multiplier. Because the number of reverse neighbors can be much larger than the number of forward neighbors, this can help to avoid excessive computation during the diversification step, with little overall effect on the final search graph. Default is FALSE.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n items to generate random neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to return.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

If TRUE (the default), then results for each item are returned by increasing distance. If you don't need the results sorted, e.g. you are going to pass the results as initialization to another routine like nnd_knn(), set this to FALSE to save a small amount of computational time.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n query items, with observations in the rows and features in the columns. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The reference data must be passed in the same orientation as query. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Matrix of m reference items, with observations in the rows and features in the columns. The nearest neighbors to the queries are randomly selected from this data. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The query data must be passed in the same orientation and format as reference. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format.

Number of nearest neighbors to return.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

If TRUE (the default), then results for each item are returned by increasing distance. If you don't need the results sorted, e.g. you are going to pass the results as initialization to another routine like graph_knn_query(), set this to FALSE to save a small amount of computational time.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input query and reference orientation stores each observation as a column (the orientation must be consistent). The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n items to generate neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to build the index for. You can specify a different number when running rnnd_query, but the index is calibrated using this value so it's recommended to set k according to the likely number of neighbors you will want to retrieve. Optional if init is specified, in which case k can be inferred from the init data. If you do both, then the specified version of k will take precedence.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

Name of the initialization strategy or initial data neighbor graph to optimize. One of:

• "rand" random initialization (the default).

• "tree" use the random projection tree method of Dasgupta and Freund (2008).

• a pre-calculated neighbor graph. A list containing:

  • idx an n by k matrix containing the nearest neighbor indices.

  • dist (optional) an n by k matrix containing the nearest neighbor distances. If the input distances are omitted, they will be calculated for you.'

If k and init are specified as arguments to this function, and the number of neighbors provided in init is not equal to k then:

• if k is smaller, only the k closest values in init are retained.

• if k is larger, then random neighbors will be chosen to fill init to the size of k. Note that there is no checking if any of the random neighbors are duplicates of what is already in init so effectively fewer than k neighbors may be chosen for some observations under these circumstances.

The number of trees to use in the RP forest. A larger number will give more accurate results at the cost of a longer computation time. The default of NULL means that the number is chosen based on the number of observations in data. Only used if init = "tree".

The maximum number of items that can appear in a leaf. This value should be chosen to match the expected number of neighbors you will want to retrieve when running queries (e.g. if you want find 50 nearest neighbors set leaf_size = 50) and should not be set to a value smaller than 10. Only used if init = "tree".

The maximum depth of the tree to build (default = 200). If the maximum tree depth is exceeded then the leaf size of a tree may exceed leaf_size which can result in a large number of neighbor distances being calculated. If verbose = TRUE a message will be logged to indicate that the leaf size is large. However, increasing the max_tree_depth may not help: it may be that there is something unusual about the distribution of your data set under your chose metric that makes a tree-based initialization inappropriate. Only used if init = "tree".

A character string specifying the method used to assign points to one side of the hyperplane or the other. Possible values are:

• "explicit" categorizes all distance metrics as either Euclidean or Angular (Euclidean after normalization), explicitly calculates a hyperplane and offset, and then calculates the margin based on the dot product with the hyperplane.

• "implicit" calculates the distance from a point to each of the points defining the normal vector. The margin is calculated by comparing the two distances: the point is assigned to the side of the hyperplane that the normal vector point with the closest distance belongs to.

• "auto" (the default) picks the margin method depending on whether a binary-specific metric such as "bhammming" is chosen, in which case "implicit" is used, and "explicit" otherwise: binary-specific metrics involve storing the data in a way that isn't very efficient for the "explicit" method and the binary-specific metric is usually a lot faster than the generic equivalent such that the cost of two distance calculations for the margin method is still faster.

Only used if init = "tree".

Number of iterations of nearest neighbor descent to carry out. By default, this will be chosen based on the number of observations in data.

The minimum relative change in the neighbor graph allowed before early stopping. Should be a value between 0 and 1. The smaller the value, the smaller the amount of progress between iterations is allowed. Default value of 0.001 means that at least 0.1% of the neighbor graph must be updated at each iteration.

Maximum number of candidate neighbors to try for each item in each iteration. Use relative to k to emulate the "rho" sampling parameter in the nearest neighbor descent paper. By default, this is set to k or 60, whichever is smaller.

If TRUE, use a lower memory, but more computationally expensive approach to index construction. If set to FALSE, you should see a noticeable speed improvement, especially when using a smaller number of threads, so this is worth trying if you have the memory to spare.

If TRUE, then candidates for the local join are weighted according to their in-degree, so that if there are more than max_candidates in a candidate list, candidates with a smaller degree are favored for retention. This prevents items with large numbers of edges crowding out other items and for high-dimensional data is likely to provide a small improvement in accuracy. Because this incurs a small extra cost of counting the degree of each node, and because it tends to delay early convergence, by default this is FALSE.

the number of trees to keep in the search forest as part of index preparation. The default is 1.

How strongly to truncate the final neighbor list for each item. The neighbor list of each item will be truncated to retain only the closest d neighbors, where d = k * pruning_degree_multiplier, and k is the original number of neighbors per item in graph. Roughly, values larger than 1 will keep all the nearest neighbors of an item, plus the given fraction of reverse neighbors (if they exist). For example, setting this to 1.5 will keep all the forward neighbors and then half as many of the reverse neighbors, although exactly which neighbors are retained is also dependent on any occlusion pruning that occurs. Set this to NULL to skip this step.

the degree of diversification of the search graph by removing unnecessary edges through occlusion pruning. This should take a value between 0 (no diversification) and 1 (remove as many edges as possible) and is treated as the probability of a neighbor being removed if it is found to be an "occlusion". If item p and q, two members of the neighbor list of item i, are closer to each other than they are to i, then the nearer neighbor p is said to "occlude" q. It is likely that q will be in the neighbor list of p so there is no need to retain it in the neighbor list of i. You may also set this to NULL to skip any occlusion pruning. Note that occlusion pruning is carried out twice, once to the forward neighbors, and once to the reverse neighbors.

If TRUE, prune the reverse neighbors of each item before the reverse graph diversification step using pruning_degree_multiplier. Because the number of reverse neighbors can be much larger than the number of forward neighbors, this can help to avoid excessive computation during the diversification step, with little overall effect on the final search graph. Default is FALSE.

Number of threads to use.

If TRUE, log information to the console.

Determines the type of progress information logged during the nearest neighbor descent stage when verbose = TRUE. Options are:

• "bar": a simple text progress bar.

• "dist": the sum of the distances in the approximate knn graph at the end of each iteration.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n items to generate neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to return. Optional if init is specified.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

Name of the initialization strategy or initial data neighbor graph to optimize. One of:

• "rand" random initialization (the default).

• "tree" use the random projection tree method of Dasgupta and Freund (2008).

• a pre-calculated neighbor graph. A list containing:

  • idx an n by k matrix containing the nearest neighbor indices.

  • dist (optional) an n by k matrix containing the nearest neighbor distances. If the input distances are omitted, they will be calculated for you.'

If k and init are specified as arguments to this function, and the number of neighbors provided in init is not equal to k then:

• if k is smaller, only the k closest values in init are retained.

• if k is larger, then random neighbors will be chosen to fill init to the size of k. Note that there is no checking if any of the random neighbors are duplicates of what is already in init so effectively fewer than k neighbors may be chosen for some observations under these circumstances.

The number of trees to use in the RP forest. A larger number will give more accurate results at the cost of a longer computation time. The default of NULL means that the number is chosen based on the number of observations in data. Only used if init = "tree".

The maximum number of items that can appear in a leaf. This value should be chosen to match the expected number of neighbors you will want to retrieve when running queries (e.g. if you want find 50 nearest neighbors set leaf_size = 50) and should not be set to a value smaller than 10. Only used if init = "tree".

The maximum depth of the tree to build (default = 200). If the maximum tree depth is exceeded then the leaf size of a tree may exceed leaf_size which can result in a large number of neighbor distances being calculated. If verbose = TRUE a message will be logged to indicate that the leaf size is large. However, increasing the max_tree_depth may not help: it may be that there is something unusual about the distribution of your data set under your chose metric that makes a tree-based initialization inappropriate. Only used if init = "tree".

A character string specifying the method used to assign points to one side of the hyperplane or the other. Possible values are:

• "explicit" categorizes all distance metrics as either Euclidean or Angular (Euclidean after normalization), explicitly calculates a hyperplane and offset, and then calculates the margin based on the dot product with the hyperplane.

• "implicit" calculates the distance from a point to each of the points defining the normal vector. The margin is calculated by comparing the two distances: the point is assigned to the side of the hyperplane that the normal vector point with the closest distance belongs to.

• "auto" (the default) picks the margin method depending on whether a binary-specific metric such as "bhammming" is chosen, in which case "implicit" is used, and "explicit" otherwise: binary-specific metrics involve storing the data in a way that isn't very efficient for the "explicit" method and the binary-specific metric is usually a lot faster than the generic equivalent such that the cost of two distance calculations for the margin method is still faster.

Only used if init = "tree".

Number of iterations of nearest neighbor descent to carry out. By default, this will be chosen based on the number of observations in data.

The minimum relative change in the neighbor graph allowed before early stopping. Should be a value between 0 and 1. The smaller the value, the smaller the amount of progress between iterations is allowed. Default value of 0.001 means that at least 0.1% of the neighbor graph must be updated at each iteration.

Maximum number of candidate neighbors to try for each item in each iteration. Use relative to k to emulate the "rho" sampling parameter in the nearest neighbor descent paper. By default, this is set to k or 60, whichever is smaller.

If TRUE, then candidates for the local join are weighted according to their in-degree, so that if there are more than max_candidates in a candidate list, candidates with a smaller degree are favored for retention. This prevents items with large numbers of edges crowding out other items and for high-dimensional data is likely to provide a small improvement in accuracy. Because this incurs a small extra cost of counting the degree of each node, and because it tends to delay early convergence, by default this is FALSE.

If TRUE, use a lower memory, but more computationally expensive approach to index construction. If set to FALSE, you should see a noticeable speed improvement, especially when using a smaller number of threads, so this is worth trying if you have the memory to spare.

Number of threads to use.

If TRUE, log information to the console.

Determines the type of progress information logged during the nearest neighbor descent stage when verbose = TRUE. Options are:

• "bar": a simple text progress bar.

• "dist": the sum of the distances in the approximate knn graph at the end of each iteration.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

A nearest neighbor index produced by rnnd_build().

Matrix of n query items, with observations in the rows and features in the columns. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version). Sparse and non-sparse data cannot be mixed, so if the data used to build index was sparse, the query data must also be sparse. and vice versa.

Number of nearest neighbors to return.

Controls trade-off between accuracy and search cost, as described by Iwasaki and Miyazaki (2018). Setting epsilon to a positive value specifies a distance tolerance on whether to explore the neighbors of candidate points. The larger the value, the more neighbors will be searched. A value of 0.1 allows query-candidate distances to be 10% larger than the current most-distant neighbor of the query point, 0.2 means 20%, and so on. Suggested values are between 0-0.5, although this value is highly dependent on the distribution of distances in the dataset (higher dimensional data should choose a smaller cutoff). Too large a value of epsilon will result in the query search approaching brute force comparison. Use this parameter in conjunction with max_search_fraction to prevent excessive run time. Default is 0.1. If you set verbose = TRUE, statistics of the number of distance calculations will be logged which can help you tune epsilon.

Maximum fraction of the reference data to search. This is a value between 0 (search none of the reference data) and 1 (search all of the data if necessary). This works in conjunction with epsilon and will terminate the search early if the specified fraction of the reference data has been searched. Default is 1.

An optional matrix of k initial nearest neighbors for each query point.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n items to generate the index for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

Note that if margin = "explicit", the metric is only used to determine whether an "angular" or "Euclidean" distance is used to measure the distance between split points in the tree.

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"). Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path. Only applies if the implicit margin method is used.

The number of trees to use in the RP forest. A larger number will give more accurate results at the cost of a longer computation time. The default of NULL means that the number is chosen based on the number of observations in data.

The maximum number of items that can appear in a leaf. This value should be chosen to match the expected number of neighbors you will want to retrieve when running queries (e.g. if you want find 50 nearest neighbors set leaf_size = 50) and should not be set to a value smaller than 10.

The maximum depth of the tree to build (default = 200). If the maximum tree depth is exceeded then the leaf size of a tree may exceed leaf_size which can result in a large number of neighbor distances being calculated. If verbose = TRUE a message will be logged to indicate that the leaf size is large. However, increasing the max_tree_depth may not help: it may be that there is something unusual about the distribution of your data set under your chose metric that makes a tree-based initialization inappropriate.

A character string specifying the method used to assign points to one side of the hyperplane or the other. Possible values are:

• "explicit" categorizes all distance metrics as either Euclidean or Angular (Euclidean after normalization), explicitly calculates a hyperplane and offset, and then calculates the margin based on the dot product with the hyperplane.

• "implicit" calculates the distance from a point to each of the points defining the normal vector. The margin is calculated by comparing the two distances: the point is assigned to the side of the hyperplane that the normal vector point with the closest distance belongs to.

• "auto" (the default) picks the margin method depending on whether a binary-specific metric such as "bhammming" is chosen, in which case "implicit" is used, and "explicit" otherwise: binary-specific metrics involve storing the data in a way that isn't very efficient for the "explicit" method and the binary-specific metric is usually a lot faster than the generic equivalent such that the cost of two distance calculations for the margin method is still faster.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Nearest neighbor data in the dense list format. This should be derived from the same data that was used to build the forest.

A random partition forest, e.g. created by rpf_build(), representing partitions of the same underlying data reflected in nn. As a convenient, this parameter is ignored if the nn list contains a forest entry, e.g. from running rpf_knn() or nnd_knn() with ret_forest = TRUE, and the forest value will be extracted from nn.

The number of trees to retain. By default only the best-scoring tree is retained.

Number of threads to use.

If TRUE, log information to the console.

Matrix of n items to generate neighbors for, with observations in the rows and features in the columns. Optionally, input can be passed with observations in the columns, by setting obs = "C", which should be more efficient. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Number of nearest neighbors to return. Optional if init is specified.

Type of distance calculation to use. One of:

• "braycurtis"

• "canberra"

• "chebyshev"

• "correlation" (1 minus the Pearson correlation)

• "cosine"

• "dice"

• "euclidean"

• "hamming"

• "hellinger"

• "jaccard"

• "jensenshannon"

• "kulsinski"

• "sqeuclidean" (squared Euclidean)

• "manhattan"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "spearmanr" (1 minus the Spearman rank correlation)

• "symmetrickl" (symmetric Kullback-Leibler divergence)

• "tsss" (Triangle Area Similarity-Sector Area Similarity or TS-SS metric)

• "yule"

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

• "cosine-preprocess": cosine with preprocessing.

• "correlation-preprocess": correlation with preprocessing.

For non-sparse binary data passed as a logical matrix, the following metrics have specialized variants which should be substantially faster than the non-binary variants (in other cases the logical data will be treated as a dense numeric vector of 0s and 1s):

• "dice"

• "hamming"

• "jaccard"

• "kulsinski"

• "matching"

• "rogerstanimoto"

• "russellrao"

• "sokalmichener"

• "sokalsneath"

• "yule"

Note that if margin = "explicit", the metric is only used to determine whether an "angular" or "Euclidean" distance is used to measure the distance between split points in the tree.

If TRUE, use faster metrics that maintain the ordering of distances internally (e.g. squared Euclidean distances if using metric = "euclidean"), then apply a correction at the end. Probably the only reason to set this to FALSE is if you suspect that some sort of numeric issue is occurring with your data in the alternative code path.

The number of trees to use in the RP forest. A larger number will give more accurate results at the cost of a longer computation time. The default of NULL means that the number is chosen based on the number of observations in data.

The maximum number of items that can appear in a leaf. The default of NULL means that the number of leaves is chosen based on the number of requested neighbors k.

The maximum depth of the tree to build (default = 200). If the maximum tree depth is exceeded then the leaf size of a tree may exceed leaf_size which can result in a large number of neighbor distances being calculated. If verbose = TRUE a message will be logged to indicate that the leaf size is large. However, increasing the max_tree_depth may not help: it may be that there is something unusual about the distribution of your data set under your chose metric that makes a tree-based initialization inappropriate.

If TRUE (the default) then an item is considered to be a neighbor of itself. Hence the first nearest neighbor in the results will be the item itself. This is a convention that many nearest neighbor methods and software adopt, so if you want to use the resulting knn graph from this function in downstream applications or compare with other methods, you should probably keep this set to TRUE. However, if you are planning on using the result of this as initialization to another nearest neighbor method (e.g. nnd_knn()), then set this to FALSE.

If TRUE also return a search forest which can be used for future querying (via rpf_knn_query()) and filtering (via rpf_filter()). By default this is FALSE. Setting this to TRUE will change the output list to be nested (see the Value section below).

A character string specifying the method used to assign points to one side of the hyperplane or the other. Possible values are:

• "explicit" categorizes all distance metrics as either Euclidean or Angular (Euclidean after normalization), explicitly calculates a hyperplane and offset, and then calculates the margin based on the dot product with the hyperplane.

• "implicit" calculates the distance from a point to each of the points defining the normal vector. The margin is calculated by comparing the two distances: the point is assigned to the side of the hyperplane that the normal vector point with the closest distance belongs to.

• "auto" (the default) picks the margin method depending on whether a binary-specific metric such as "bhammming" is chosen, in which case "implicit" is used, and "explicit" otherwise: binary-specific metrics involve storing the data in a way that isn't very efficient for the "explicit" method and the binary-specific metric is usually a lot faster than the generic equivalent such that the cost of two distance calculations for the margin method is still faster.

Number of threads to use.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.

Matrix of n query items, with observations in the rows and features in the columns. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The reference data must be passed in the same orientation as query. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format. Dataframes will be converted to numerical matrix format internally, so if your data columns are logical and intended to be used with the specialized binary metrics, you should convert it to a logical matrix first (otherwise you will get the slower dense numerical version).

Matrix of m reference items, with observations in the rows and features in the columns. The nearest neighbors to the queries are calculated from this data and should be the same data used to build the forest. Optionally, the data may be passed with the observations in the columns, by setting obs = "C", which should be more efficient. The query data must be passed in the same format and orientation as reference. Possible formats are base::data.frame(), base::matrix() or Matrix::sparseMatrix(). Sparse matrices should be in dgCMatrix format.

A random partition forest, created by rpf_build(), representing partitions of the data in reference.

Number of nearest neighbors to return. You are unlikely to get good results if you choose a value substantially larger than the value of leaf_size used to build the forest.

if TRUE (the default) then candidate indices found in the leaves of the forest are cached to avoid recalculating the same distance repeatedly. This incurs an extra memory cost which scales with n_threads. Set this to FALSE to disable distance caching.

Number of threads to use. Note that the parallelism in the search is done over the observations in query not the trees in the forest. Thus a single observation will not see any speed-up from increasing n_threads.

If TRUE, log information to the console.

set to "C" to indicate that the input data orientation stores each observation as a column. The default "R" means that observations are stored in each row. Storing the data by row is usually more convenient, but internally your data will be converted to column storage. Passing it already column-oriented will save some memory and (a small amount of) CPU usage.