Approximate furthest neighbor search

>>> from mlpack import approx_kfn

This program implements two strategies for furthest neighbor search. These strategies are:

- The 'qdafn' algorithm from "Approximate Furthest Neighbor in High Dimensions" by R. Pagh, F. Silvestri, J. Sivertsen, and M. Skala, in Similarity Search and Applications 2015 (SISAP).

- The 'DrusillaSelect' algorithm from "Fast approximate furthest neighbors with data-dependent candidate selection", by R.R. Curtin and A.B. Gardner, in Similarity Search and Applications 2016 (SISAP).

These two strategies give approximate results for the furthest neighbor search problem and can be used as fast replacements for other furthest neighbor techniques such as those found in the mlpack_kfn program. Note that typically, the 'ds' algorithm requires far fewer tables and projections than the 'qdafn' algorithm.

Specify a reference set (set to search in) with 'reference', specify a query set with 'query', and specify algorithm parameters with 'num_tables' and 'num_projections' (or don't and defaults will be used). The algorithm to be used (either 'ds'---the default---or 'qdafn') may be specified with 'algorithm'. Also specify the number of neighbors to search for with 'k'.

If no query set is specified, the reference set will be used as the query set. The 'output_model' output parameter may be used to store the built model, and an input model may be loaded instead of specifying a reference set with the 'input_model' option.

Results for each query point can be stored with the 'neighbors' and 'distances' output parameters. Each row of these output matrices holds the k distances or neighbor indices for each query point.

For example, to find the 5 approximate furthest neighbors with 'reference_set' as the reference set and 'query_set' as the query set using DrusillaSelect, storing the furthest neighbor indices to 'neighbors' and the furthest neighbor distances to 'distances', one could call

>>> approx_kfn(query=query_set, reference=reference_set, k=5, algorithm='ds')
>>> neighbors = output['neighbors']
>>> distances = output['distances']

and to perform approximate all-furthest-neighbors search with k=1 on the set 'data' storing only the furthest neighbor distances to 'distances', one could call

>>> approx_kfn(reference=reference_set, k=1)
>>> distances = output['distances']

A trained model can be re-used. If a model has been previously saved to 'model', then we may find 3 approximate furthest neighbors on a query set 'new_query_set' using that model and store the furthest neighbor indices into 'neighbors' by calling

>>> approx_kfn(input_model=model, query=new_query_set, k=3)
>>> neighbors = output['neighbors']

input options

output options

The return value from the binding is a dict containing the following elements: