k-Furthest-Neighbors Search
An implementation of k-furthest-neighbor search using single-tree and dual-tree algorithms. Given a set of reference points and query points, this can find the k furthest neighbors in the reference set of each query point using trees.
:- use_module('path/to/.../src/methods/kfn/kfn.pl').
%% usage example
TrainData = [5.1,3.5,1.4, 4.9,3.0,1.4, 4.7,3.2,1.3, 4.6,3.1,1.5],
TestData = [3,2,0, 5,1,4, 0,0,4, 3,3,5, 0,5,5, 2,5,5],
kfn_initAndBuildModel(kd, dual_tree, 0, 20, 0.0, TrainData, 3),
kfn_searchWithQuery(TestData, 3, 2, NeighborsList, _, DistancesList, _).Available Predicates
kfn_initAndBuildModel/7
Initialize the Model and build it.
%% predicate definition
kfn_initAndBuildModel(TreeType, SearchMode, RandomBasis, LeafSize, Epsilon, ReferenceList, ReferenceRows) :-
LeafSize >= 1,
Epsilon >= 0,
convert_list_to_float_array(ReferenceList, ReferenceRows, array(Xsize, Xrownum, X)),
initAndBuildModelI(TreeType, SearchMode, RandomBasis, LeafSize, Epsilon, X, Xsize, Xrownum).
%% foreign c++ predicate definition
foreign(initAndBuildModel, c, initAndBuildModelI( +string, +string,
+integer, +integer, +float32,
+pointer(float_array), +integer, +integer)).Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| treeType | +string | Type of tree to use: "kd", "vp", "rp", "max_rp", "ub", "cover", "r", "r_star", "x", "ball", "hilbert_r", "r_plus", "r_plus_plus", "oct". | kd |
| searchMode | +string | Type of neighbor search: "naive", "single_tree", "dual_tree", "greedy". | dual_tree |
| randomBasis | +integer(bool) | Before tree-building, project the data onto a random orthogonal basis. | (0)false |
| leafSize | +integer | Leaf size for tree building. Not used by cover trees | 20 |
| epsilon | +float | If specified, will do approximate furthest neighbor search with given relative error. Must be in the range [0,1). | 0.0 |
| referenceSet | +matrix | Matrix containing the reference dataset. | - |
kfn_searchWithQuery/7
Perform neighbor search on the queryset.
%% predicate definition
kfn_searchWithQuery(QueryList, QueryRows, K, NeighborsList, YCols, DistancesList, ZCols) :-
K > 0,
convert_list_to_float_array(QueryList, QueryRows, array(Xsize, Xrownum, X)),
searchWithQueryI(X, Xsize, Xrownum, K, Y, YCols, YRows, Z, ZCols, ZRows),
convert_float_array_to_2d_list(Y, YCols, YRows, NeighborsList),
convert_float_array_to_2d_list(Z, ZCols, ZRows, DistancesList).
%% foreign c++ predicate definition
foreign(searchWithQuery, c, searchWithQueryI( +pointer(float_array), +integer, +integer,
+integer,
-pointer(float_array), -integer, -integer,
-pointer(float_array), -integer, -integer)).Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| querySet | +matrix | Matrix containing query points (optional). | - |
| k | +integer | Number of furthest neighbors to find. | 0 |
| neighbors | -matrix | Matrix to output distances into. | - |
| distances | -matrix | Matrix to output neighbors into. | - |
kfn_searchNoQuery/5
Perform monochromatic neighbor search.
%% predicate definition
kfn_searchNoQuery(K, NeighborsList, YCols, DistancesList, ZCols) :-
K > 0,
searchNoQueryI(K, Y, YCols, YRows, Z, ZCols, ZRows),
convert_float_array_to_2d_list(Y, YCols, YRows, NeighborsList),
convert_float_array_to_2d_list(Z, ZCols, ZRows, DistancesList).
%% foreign c++ predicate definition
foreign(searchNoQuery, c, searchNoQueryI( +integer,
-pointer(float_array), -integer, -integer,
-pointer(float_array), -integer, -integer)).Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| k | +integer | Number of furthest neighbors to find. | 0 |
| neighbors | -matrix | Matrix to output distances into. | - |
| distances | -matrix | Matrix to output neighbors into. | - |
Connected Links/Resources
If you want a more detailed explanation, then go to the python documentation. There is most of the time a good explanation on how the methods work and what the parameters do.
added some of the links from the python documentation