An implementation of fast exact max-kernel search. More...
Public Member Functions | |
FastMKS (const arma::mat &referenceSet, TreeType *referenceTree, const arma::mat &querySet, TreeType *queryTree, const bool single=false, const bool naive=false) | |
Create the FastMKS object with already-initialized trees built on the reference and query points. | |
FastMKS (const arma::mat &referenceSet, TreeType *referenceTree, const bool single=false, const bool naive=false) | |
Create the FastMKS object with an already-initialized tree built on the reference points. | |
FastMKS (const arma::mat &referenceSet, const arma::mat &querySet, KernelType &kernel, const bool single=false, const bool naive=false) | |
Create the FastMKS object using separate reference and query sets, and with an initialized kernel. | |
FastMKS (const arma::mat &referenceSet, KernelType &kernel, const bool single=false, const bool naive=false) | |
Create the FastMKS object using the reference set as the query set, and with an initialized kernel. | |
FastMKS (const arma::mat &referenceSet, const arma::mat &querySet, const bool single=false, const bool naive=false) | |
Create the FastMKS object using separate reference and query sets. | |
FastMKS (const arma::mat &referenceSet, const bool single=false, const bool naive=false) | |
Create the FastMKS object using the reference set as the query set. | |
~FastMKS () | |
Destructor for the FastMKS object. | |
metric::IPMetric< KernelType > & | Metric () |
Modify the inner-product metric induced by the given kernel. | |
const metric::IPMetric < KernelType > & | Metric () const |
Get the inner-product metric induced by the given kernel. | |
void | Search (const size_t k, arma::Mat< size_t > &indices, arma::mat &products) |
Search for the maximum inner products of the query set (or if no query set was passed, the reference set is used). | |
Private Member Functions | |
void | InsertNeighbor (arma::Mat< size_t > &indices, arma::mat &products, const size_t queryIndex, const size_t pos, const size_t neighbor, const double distance) |
Utility function. Copied too many times from too many places. | |
Private Attributes | |
metric::IPMetric< KernelType > | metric |
The instantiated inner-product metric induced by the given kernel. | |
bool | naive |
If true, naive (brute-force) search is used. | |
const arma::mat & | querySet |
The query dataset. | |
TreeType * | queryTree |
The tree built on the query dataset. | |
const arma::mat & | referenceSet |
The reference dataset. | |
TreeType * | referenceTree |
The tree built on the reference dataset. | |
bool | single |
If true, single-tree search is used. | |
bool | treeOwner |
If true, this object created the trees and is responsible for them. |
An implementation of fast exact max-kernel search.
Given a query dataset and a reference dataset (or optionally just a reference dataset which is also used as the query dataset), fast exact max-kernel search finds, for each point in the query dataset, the k points in the reference set with maximum kernel value K(p_q, p_r), where k is a specified parameter and K() is a Mercer kernel.
For more information, see the following paper.
@inproceedings{curtin2013fast, title={Fast Exact Max-Kernel Search}, author={Curtin, Ryan R. and Ram, Parikshit and Gray, Alexander G.}, booktitle={Proceedings of the 2013 SIAM International Conference on Data Mining (SDM 13)}, year={2013} }
This class allows specification of the type of kernel and also of the type of tree. FastMKS can be run on kernels that work on arbitrary objects -- however, this only works with cover trees and other trees that are built only on points in the dataset (and not centroids of regions or anything like that).
KernelType | Type of kernel to run FastMKS with. | |
TreeType | Type of tree to run FastMKS with; it must have metric IPMetric<KernelType>. |
Definition at line 69 of file fastmks.hpp.
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
const bool | single = false , |
|||
const bool | naive = false | |||
) |
Create the FastMKS object using the reference set as the query set.
Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
const arma::mat & | querySet, | |||
const bool | single = false , |
|||
const bool | naive = false | |||
) |
Create the FastMKS object using separate reference and query sets.
Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
KernelType & | kernel, | |||
const bool | single = false , |
|||
const bool | naive = false | |||
) |
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
const arma::mat & | querySet, | |||
KernelType & | kernel, | |||
const bool | single = false , |
|||
const bool | naive = false | |||
) |
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
TreeType * | referenceTree, | |||
const bool | single = false , |
|||
const bool | naive = false | |||
) |
Create the FastMKS object with an already-initialized tree built on the reference points.
Be sure that the tree is built with the metric type IPMetric<KernelType>. For this constructor, the reference set and the query set are the same points. Optionally, whether or not to run single-tree search or brute-force (naive) search can be specified.
mlpack::fastmks::FastMKS< KernelType, TreeType >::FastMKS | ( | const arma::mat & | referenceSet, | |
TreeType * | referenceTree, | |||
const arma::mat & | querySet, | |||
TreeType * | queryTree, | |||
const bool | single = false , |
|||
const bool | naive = false | |||
) |
mlpack::fastmks::FastMKS< KernelType, TreeType >::~FastMKS | ( | ) |
Destructor for the FastMKS object.
void mlpack::fastmks::FastMKS< KernelType, TreeType >::InsertNeighbor | ( | arma::Mat< size_t > & | indices, | |
arma::mat & | products, | |||
const size_t | queryIndex, | |||
const size_t | pos, | |||
const size_t | neighbor, | |||
const double | distance | |||
) | [private] |
Utility function. Copied too many times from too many places.
metric::IPMetric<KernelType>& mlpack::fastmks::FastMKS< KernelType, TreeType >::Metric | ( | ) | [inline] |
Modify the inner-product metric induced by the given kernel.
Definition at line 195 of file fastmks.hpp.
References mlpack::fastmks::FastMKS< KernelType, TreeType >::metric.
const metric::IPMetric<KernelType>& mlpack::fastmks::FastMKS< KernelType, TreeType >::Metric | ( | ) | const [inline] |
Get the inner-product metric induced by the given kernel.
Definition at line 193 of file fastmks.hpp.
References mlpack::fastmks::FastMKS< KernelType, TreeType >::metric.
void mlpack::fastmks::FastMKS< KernelType, TreeType >::Search | ( | const size_t | k, | |
arma::Mat< size_t > & | indices, | |||
arma::mat & | products | |||
) |
Search for the maximum inner products of the query set (or if no query set was passed, the reference set is used).
The resulting maximum inner products are stored in the products matrix and the corresponding point indices are stores in the indices matrix. The results for each point in the query set are stored in the corresponding column of the indices and products matrices; for instance, the index of the point with maximum inner product to point 4 in the query set will be stored in row 0 and column 4 of the indices matrix.
k | The number of maximum kernels to find. | |
indices | Matrix to store resulting indices of max-kernel search in. | |
products | Matrix to store resulting max-kernel values in. |
metric::IPMetric<KernelType> mlpack::fastmks::FastMKS< KernelType, TreeType >::metric [private] |
The instantiated inner-product metric induced by the given kernel.
Definition at line 218 of file fastmks.hpp.
Referenced by mlpack::fastmks::FastMKS< KernelType, TreeType >::Metric().
bool mlpack::fastmks::FastMKS< KernelType, TreeType >::naive [private] |
If true, naive (brute-force) search is used.
Definition at line 215 of file fastmks.hpp.
const arma::mat& mlpack::fastmks::FastMKS< KernelType, TreeType >::querySet [private] |
The query dataset.
Definition at line 201 of file fastmks.hpp.
TreeType* mlpack::fastmks::FastMKS< KernelType, TreeType >::queryTree [private] |
The tree built on the query dataset.
This is NULL if there is no query set.
Definition at line 207 of file fastmks.hpp.
const arma::mat& mlpack::fastmks::FastMKS< KernelType, TreeType >::referenceSet [private] |
The reference dataset.
Definition at line 199 of file fastmks.hpp.
TreeType* mlpack::fastmks::FastMKS< KernelType, TreeType >::referenceTree [private] |
The tree built on the reference dataset.
Definition at line 204 of file fastmks.hpp.
bool mlpack::fastmks::FastMKS< KernelType, TreeType >::single [private] |
If true, single-tree search is used.
Definition at line 213 of file fastmks.hpp.
bool mlpack::fastmks::FastMKS< KernelType, TreeType >::treeOwner [private] |
If true, this object created the trees and is responsible for them.
Definition at line 210 of file fastmks.hpp.