MLPACK  1.0.11
Public Member Functions | Private Member Functions | Private Attributes | List of all members
mlpack::fastmks::FastMKS< KernelType, TreeType > Class Template Reference

An implementation of fast exact max-kernel search. More...

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. More...
 
 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. More...
 
 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. More...
 
 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. More...
 
 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. More...
 
 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. More...
 
 ~FastMKS ()
 Destructor for the FastMKS object. More...
 
const metric::IPMetric< KernelType > & Metric () const
 Get the inner-product metric induced by the given kernel. More...
 
metric::IPMetric< KernelType > & Metric ()
 Modify the inner-product metric induced by the given kernel. More...
 
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). More...
 
std::string ToString () const
 Returns a string representation of this object. More...
 

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

Private Attributes

metric::IPMetric< KernelType > metric
 The instantiated inner-product metric induced by the given kernel. More...
 
bool naive
 If true, naive (brute-force) search is used. More...
 
const arma::mat & querySet
 The query dataset. More...
 
TreeType * queryTree
 The tree built on the query dataset. More...
 
const arma::mat & referenceSet
 The reference dataset. More...
 
TreeType * referenceTree
 The tree built on the reference dataset. More...
 
bool single
 If true, single-tree search is used. More...
 
bool treeOwner
 If true, this object created the trees and is responsible for them. More...
 

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
KernelTypeType of kernel to run FastMKS with.
TreeTypeType 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>>
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.

Parameters
referenceSetSet of data to run FastMKS on.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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.

Parameters
referenceSetReference set of data for FastMKS.
querySetSet of query points for FastMKS.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
mlpack::fastmks::FastMKS< KernelType, TreeType >::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.

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
referenceSetReference set of data for FastMKS.
kernelInitialized kernel.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
mlpack::fastmks::FastMKS< KernelType, TreeType >::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.

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
referenceSetReference set of data for FastMKS.
querySetSet of query points for FastMKS.
kernelInitialized kernel.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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.

Parameters
referenceSetReference set of data for FastMKS.
referenceTreeTree built on reference data.
singleWhether or not to run single-tree search.
naiveWhether or not to run brute-force (naive) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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 
)

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
referenceSetReference set of data for FastMKS.
referenceTreeTree built on reference data.
querySetSet of query points for FastMKS.
queryTreeTree built on query data.
singleWhether or not to use single-tree search.
naiveWhether or not to use naive (brute-force) search.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
mlpack::fastmks::FastMKS< KernelType, TreeType >::~FastMKS ( )

Destructor for the FastMKS object.

Member Function Documentation

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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, and mlpack::fastmks::FastMKS< KernelType, TreeType >::ToString().

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
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.

Parameters
kThe number of maximum kernels to find.
indicesMatrix to store resulting indices of max-kernel search in.
productsMatrix to store resulting max-kernel values in.
template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
std::string mlpack::fastmks::FastMKS< KernelType, TreeType >::ToString ( ) const

Returns a string representation of this object.

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

Member Data Documentation

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

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 mlpack::fastmks::FastMKS< KernelType, TreeType >::naive
private

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& mlpack::fastmks::FastMKS< KernelType, TreeType >::querySet
private

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* 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 212 of file fastmks.hpp.

template<typename KernelType, typename TreeType = tree::CoverTree<metric::IPMetric<KernelType>, tree::FirstPointIsRoot, FastMKSStat>>
const arma::mat& mlpack::fastmks::FastMKS< KernelType, TreeType >::referenceSet
private

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* mlpack::fastmks::FastMKS< KernelType, TreeType >::referenceTree
private

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 mlpack::fastmks::FastMKS< KernelType, TreeType >::single
private

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 mlpack::fastmks::FastMKS< KernelType, TreeType >::treeOwner
private

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

Definition at line 215 of file fastmks.hpp.


The documentation for this class was generated from the following file: