turi::nearest_neighbors::ball_tree_neighbors Class Reference

#include <toolkits/nearest_neighbors/ball_tree_neighbors.hpp>

Public Member Functions
	~ball_tree_neighbors ()
void	init_options (const std::map< std::string, flexible_type > &_opts) override
void	train (const sframe &X, const std::vector< flexible_type > &ref_labels, const std::vector< dist_component_type > &composite_distance_params, const std::map< std::string, flexible_type > &opts) override
sframe	query (const v2::ml_data &mld_queries, const std::vector< flexible_type > &query_labels, const size_t k, const double radius, const bool include_self_edges) const override
size_t	get_version () const override
void	save_impl (turi::oarchive &oarc) const override
void	load_version (turi::iarchive &iarc, size_t version) override

Static Public Attributes
static constexpr size_t	BALL_TREE_NEIGHBORS_VERSION = 2

Protected Member Functions
bool	activate_query_node (size_t k, double radius, double min_poss_dist, size_t num_current_neighbors, double max_current_dist) const

Detailed Description

Ball tree nearest neighbors class

Implements the ball tree method for k-nearest neighbors search.

The ball tree works by partitioning the reference data into into successively smaller balls, and recording the center (i.e. pivot) and radius of each ball. A ball tree query uses the pivots and radii to exclude many of the balls from the k-nearest neighbor search, allowing it to run in sub-linear time.

In addition to the objects contained in the nearest_neighbors_model base class, the ball tree contains the following:

• membership: Each element of this vector indicates which node the corresponding reference data point belongs to. After the tree is constructed, the elements in this vector correspond to leaf nodes of the tree only.
• pivots: The reference data point at the center of each tree node.
• node_radii: The distance from the pivot of each node to the most distant reference point belonging to the tree node.

Definition at line 46 of file ball_tree_neighbors.hpp.

Constructor & Destructor Documentation

~ball_tree_neighbors()

turi::nearest_neighbors::ball_tree_neighbors::~ball_tree_neighbors

(

)

Destructor. Make sure bad things don't happen

Member Function Documentation

activate_query_node()

bool turi::nearest_neighbors::ball_tree_neighbors::activate_query_node ( size_t  k, double  radius, double  min_poss_dist, size_t  num_current_neighbors, double  max_current_dist  ) const

protected

Decide if a node should be activated for a query. Activating a node means it will be traversed in the search for a query's nearest neighbors. For internal nodes, this means the search will in turn check if each child node should be activated. For leaf nodes, it means the distances between the query and all members of the node will be computed (and potentially added to the set of candidate nearest neighbors).

Parameters

[in]	k	size_t Max number of neighbors
[in]	radius	double Max distance for a neighbor
[in]	min_poss_dist	double Minimum possible distance from the query point to the node in question.
[in]	num_current_neighbors	size_t Current number of neighbors
[in]	max_current_dist	double Max distance to the current neighbors set. Note that if the neighbor candidates set is empty, this will be -1.0.
[out]	activate	bool If true, the node should be activated.

get_version()

size_t turi::nearest_neighbors::ball_tree_neighbors::get_version ( ) const

inlineoverride

Gets the model version number

Definition at line 142 of file ball_tree_neighbors.hpp.

init_options()

void turi::nearest_neighbors::ball_tree_neighbors::init_options ( const std::map< std::string, flexible_type > &  _opts )

override

Set the model options. Use the option manager to set these options. The option manager should throw errors if the options do not satisfy the option manager's conditions.

Parameters

[in]

opts

Options to set

load_version()

void turi::nearest_neighbors::ball_tree_neighbors::load_version ( turi::iarchive &  iarc, size_t  version  )

override

Turi serialization save

query()

sframe turi::nearest_neighbors::ball_tree_neighbors::query ( const v2::ml_data &  mld_queries, const std::vector< flexible_type > &  query_labels, const size_t  k, const double  radius, const bool  include_self_edges  ) const

override

Find neighbors of queries in a created ball tree model.

For each query, the method keeps track of the current k-nearest neighbors in the ball tree. At each node, the closest possible point in each child node to the query is computed, and if this distance is further than the current k'th nearest neighbor, that child node (and its descendants) is skpped in the traversal.

Parameters

[in]	mld_queries	query data
[in]	query_labels	sframe query labels
[in]	k	size_t max number of neighbors to return for each query
[in]	radius	double max distance for returned neighbors to each query
[out]	ret	sframe SFrame with four columns: query label, reference label, distance, and rank.

Note

Assumes that data is already in the right shape.

save_impl()

void turi::nearest_neighbors::ball_tree_neighbors::save_impl ( turi::oarchive &  oarc ) const

override

Turi serialization save

train()

void turi::nearest_neighbors::ball_tree_neighbors::train ( const sframe &  X, const std::vector< flexible_type > &  ref_labels, const std::vector< dist_component_type > &  composite_distance_params, const std::map< std::string, flexible_type > &  opts  )

override

Create a ball tree nearest neighbors model.

Parameters

[in]	X	sframe input feature data
[in]	ref_labels	row labels for the reference dataset
[in]	composite_distance_params
[in]	y	sframe input labels

Member Data Documentation

BALL_TREE_NEIGHBORS_VERSION

constexpr size_t turi::nearest_neighbors::ball_tree_neighbors::BALL_TREE_NEIGHBORS_VERSION = 2

static

version 3 (GLC 1.6/sprint 1509): Add the original_row_index member, to facilitate the 'include_self_edges' flag.

Definition at line 86 of file ball_tree_neighbors.hpp.

---

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

• toolkits/nearest_neighbors/ball_tree_neighbors.hpp