Approximate furthest neighbor search

An implementation of two strategies for furthest neighbor search. This can be used to compute the furthest neighbor of query point(s) from a set of points.

:- use_module('path/to/.../src/methods/approx_kfn/approx_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],
initDrusillaModelWithTrain(TrainData, 3, 2, 2),
searchDrusilla(TestData, 3, 2, NeighborsList, _, DistancesList, _).

Available Predicates

links/resources

initDrusillaModelNoTrain/2

Initiates the DrusillaSearch Model but doesn’t train it.

trainDrusilla has to be used before searchDrusilla can be used.

%% predicate definition 
initDrusillaModelNoTrain(L, M) :-
        L > 0,
        M > 0,
        initDrusillaModelNoTrainI(L, M).

%% foreign c++ predicate definition 
foreign(initDrusillaModelNoTrain, c, initDrusillaModelNoTrainI(+integer, +integer)).

Parameters

Name	Type	Description	Default
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

initDrusillaModelWithTrain/4

Initiates the DrusillaSearch Model and trains it with the given reference Set.

Afterwards searchDrusilla can be used.

%% predicate definition 
initDrusillaModelWithTrain(DataList, DataRows, L, M) :-
        L > 0,
        M > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        initDrusillaModelWithTrainI(X, Xsize, Xrownum, L, M).
        
%% foreign c++ predicate definition 
foreign(initDrusillaModelWithTrain, c, initDrusillaModelWithTrainI( +pointer(float_array), +integer, +integer, 
                                                                    +integer, +integer)).

Parameters

Name	Type	Description	Default
referenceSet	+matrix	Matrix containing the reference dataset	-
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

searchDrusilla/7

Run Search on the given Queryset with the Drusilla Search Policy.

%% predicate definition 
searchDrusilla(DataList, DataRows, K, NeighborsList, YCols, DistancesList, ZCols) :-
        K > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        searchDrusillaI(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(searchDrusilla, c, searchDrusillaI( +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	-
k	+integer	Number of furthest neighbors to search for	1
neighbors	-matrix	Matrix to save furthest neighbor distances to	-
distance	-matrix	Matrix to save neighbor indices to	-

trainDrusilla/4

Trains the DrusillaSearch Model with the given reference Set.

%% predicate definition 
trainDrusilla(DataList, DataRows, L, M) :-
        L > 0,
        M > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        trainDrusillaI(X, Xsize, Xrownum, L, M).

%% foreign c++ predicate definition 
foreign(trainDrusilla, c, trainDrusillaI( +pointer(float_array), +integer, +integer, 
                                          +integer, +integer)).

Parameters

Name	Type	Description	Default
referenceSet	+matrix	Matrix containing the reference dataset	-
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

initQDAFNModelNoTrain/2

Initiates the QDAFNSearch Model but doesn’t train it.

trainQDAFN has to be used before searchQDAFN can be used.

%% predicate definition 
initQDAFNModelNoTrain(L, M) :-
        L > 0,
        M > 0,
        initQDAFNModelNoTrainI(L, M).

%% foreign c++ predicate definition 
foreign(initQDAFNModelNoTrain, c, initQDAFNModelNoTrainI(+integer, +integer)).

Parameters

Name	Type	Description	Default
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

initQDAFNModelWithTrain/4

Initiates the QDAFNSearch Model and trains it with the given reference Set.

Afterwards searchQDAFN can be used.

%% predicate definition 
initQDAFNModelWithTrain(DataList, DataRows, L, M) :-
        L > 0,
        M > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        initQDAFNModelWithTrainI(X, Xsize, Xrownum, L, M).

%% foreign c++ predicate definition 
foreign(initQDAFNModelWithTrain, c, initQDAFNModelWithTrainI( +pointer(float_array), +integer, +integer, 
                                                              +integer, +integer)).

Parameters

Name	Type	Description	Default
referenceSet	+matrix	Matrix containing the reference dataset	-
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

searchQDAFN/7

Run Search on the given Queryset with the QDAFN Search Policy.

%% predicate definition 
searchQDAFN(DataList, DataRows, K, NeighborsList, YCols, DistancesList, ZCols) :-
        K > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        searchQDAFNI(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(searchQDAFN, c, searchQDAFNI( +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	-
k	+integer	Number of furthest neighbors to search for	1
neighbors	-matrix	Matrix to save furthest neighbor distances to	-
distance	-matrix	Matrix to save neighbor indices to	-

trainQDAFN/4

Trains the QDAFNSearch Model with the given reference Set.

%% predicate definition 
trainQDAFN(DataList, DataRows, L, M) :-
        L > 0,
        M > 0,
        convert_list_to_float_array(DataList, DataRows, array(Xsize, Xrownum, X)),
        trainQDAFNI(X, Xsize, Xrownum, L, M).

%% foreign c++ predicate definition 
foreign(trainQDAFN, c, trainQDAFNI( +pointer(float_array), +integer, +integer, 
                                    +integer, +integer)).

Parameters

Name	Type	Description	Default
referenceSet	+matrix	Matrix containing the reference dataset	-
l	+integer	Number of projections	5
m	+integer	Number of elements to store for each projection	5

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

Comments

Please register or sign in to add a comment.