SYNOPSIS

Public Member Functions

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 (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, 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, 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, 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, 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 ()

Destructor for the FastMKS object. const metric::IPMetric

< KernelType > & Metric () const "

Get the inner-product metric induced by the given kernel. metric::IPMetric< KernelType > & Metric ()

Modify 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). std::string ToString () const

Returns a string representation of this object.

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.

Detailed Description

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>class mlpack::fastmks::FastMKS< KernelType, TreeType >

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).

Template Parameters:

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.

Constructor & Destructor Documentation

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

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.

Parameters:

referenceSet Set of data to run FastMKS on.

single Whether or not to run single-tree search.

naive Whether or not to run brute-force (naive) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, const arma::mat &querySet, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

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.

Parameters:

referenceSet Reference set of data for FastMKS.

querySet Set of query points for FastMKS.

single Whether or not to run single-tree search.

naive Whether or not to run brute-force (naive) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, KernelType &kernel, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

Create the FastMKS object using the reference set as the query set, and with an initialized kernel. This is useful for when the kernel stores state. Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.

Parameters:

referenceSet Reference set of data for FastMKS.

kernel Initialized kernel.

single Whether or not to run single-tree search.

naive Whether or not to run brute-force (naive) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, const arma::mat &querySet, KernelType &kernel, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

Create the FastMKS object using separate reference and query sets, and with an initialized kernel. This is useful for when the kernel stores state. Optionally, specify whether or not single-tree search or naive (brute-force) search should be used.

Parameters:

referenceSet Reference set of data for FastMKS.

querySet Set of query points for FastMKS.

kernel Initialized kernel.

single Whether or not to run single-tree search.

naive Whether or not to run brute-force (naive) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, TreeType *referenceTree, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

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.

Parameters:

referenceSet Reference set of data for FastMKS.

referenceTree Tree built on reference data.

single Whether or not to run single-tree search.

naive Whether or not to run brute-force (naive) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::\fBFastMKS\fP (const arma::mat &referenceSet, TreeType *referenceTree, const arma::mat &querySet, TreeType *queryTree, const boolsingle = \fCfalse\fP, const boolnaive = \fCfalse\fP)

Create the FastMKS object with already-initialized trees built on the reference and query points. Be sure that the trees are built with the metric type IPMetric<KernelType>. Optionally, whether or not to run single-tree search or naive (brute-force) search can be specified.

Parameters:

referenceSet Reference set of data for FastMKS.

referenceTree Tree built on reference data.

querySet Set of query points for FastMKS.

queryTree Tree built on query data.

single Whether or not to use single-tree search.

naive Whether or not to use naive (brute-force) search.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::~\fBFastMKS\fP ()

Destructor for the FastMKS object.

Member Function Documentation

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> void \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::InsertNeighbor (arma::Mat< size_t > &indices, arma::mat &products, const size_tqueryIndex, const size_tpos, const size_tneighbor, const doubledistance)\fC [private]\fP

Utility function. Copied too many times from too many places.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> const \fBmetric::IPMetric\fP<KernelType>& \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::Metric () const\fC [inline]\fP

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.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmetric::IPMetric\fP<KernelType>& \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::Metric ()\fC [inline]\fP

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.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> void \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::Search (const size_tk, 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.

Parameters:

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.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> std::string \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::ToString () const

Returns a string representation of this object.

Member Data Documentation

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> \fBmetric::IPMetric\fP<KernelType> \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::metric\fC [private]\fP

The instantiated inner-product metric induced by the given kernel.

Definition at line 223 of file fastmks.hpp.

Referenced by mlpack::fastmks::FastMKS< KernelType, TreeType >::Metric().

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> bool \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::naive\fC [private]\fP

If true, naive (brute-force) search is used.

Definition at line 220 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> const arma::mat& \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::querySet\fC [private]\fP

The query dataset.

Definition at line 206 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> TreeType* \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::queryTree\fC [private]\fP

The tree built on the query dataset. This is NULL if there is no query set.

Definition at line 212 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> const arma::mat& \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::referenceSet\fC [private]\fP

The reference dataset.

Definition at line 204 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> TreeType* \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::referenceTree\fC [private]\fP

The tree built on the reference dataset.

Definition at line 209 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> bool \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::single\fC [private]\fP

If true, single-tree search is used.

Definition at line 218 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>> bool \fBmlpack::fastmks::FastMKS\fP< KernelType, TreeType >::treeOwner\fC [private]\fP

If true, this object created the trees and is responsible for them.

Definition at line 215 of file fastmks.hpp.

Author

Generated automatically by Doxygen for MLPACK from the source code.