HMLP: High-performance Machine Learning Primitives
Public Types | Public Member Functions | Public Attributes | Static Public Attributes | List of all members
hmlp::tree::Node< SETUP, NODEDATA > Class Template Reference

This is the default ball tree splitter. Given coordinates, compute the direction from the two most far away points. Project all points to this line and split into two groups using a median select. More...

#include <tree.hpp>

Inheritance diagram for hmlp::tree::Node< SETUP, NODEDATA >:
hmlp::ReadWrite hmlp::mpitree::Node< SETUP, NODEDATA >

Public Types

typedef SETUP::T T
 

Public Member Functions

 Node (SETUP *setup, size_t n, size_t l, Node *parent, unordered_map< size_t, Node * > *morton2node, Lock *treelock)
 
 Node (SETUP *setup, int n, int l, vector< size_t > gids, Node *parent, unordered_map< size_t, Node * > *morton2node, Lock *treelock)
 
 Node (size_t morton)
 
 ~Node ()
 
void Resize (int n)
 
void Split ()
 
bool ContainAny (vector< size_t > &queries)
 Check if this node contain any query using morton. Notice that queries[] contains gids; thus, morton[] needs to be accessed using gids. More...
 
bool ContainAny (set< Node * > &querys)
 
void Print ()
 
void DependOnChildren (Task *task)
 
void DependOnParent (Task *task)
 
void DependOnNoOne (Task *task)
 
- Public Member Functions inherited from hmlp::ReadWrite
 ReadWrite ()
 
void DependencyAnalysis (ReadWriteType type, Task *task)
 This is the key function that encode the dependency. More...
 
void DependencyCleanUp ()
 

Public Attributes

SETUP * setup = NULL
 
NODEDATA data
 
size_t n
 
size_t l
 
size_t morton = 0
 
size_t offset = 0
 
size_t treelist_id
 
vector< size_t > gids
 
set< size_t > FarIDs
 
set< Node * > FarNodes
 
set< size_t > FarNodeMortonIDs
 
set< size_t > NearIDs
 
set< Node * > NearNodes
 
set< size_t > NearNodeMortonIDs
 
set< size_t > NNFarIDs
 
set< Node * > NNFarNodes
 
set< Node * > ProposedNNFarNodes
 
set< size_t > NNFarNodeMortonIDs
 
set< size_t > NNNearIDs
 
set< Node * > NNNearNodes
 
set< Node * > ProposedNNNearNodes
 
set< size_t > NNNearNodeMortonIDs
 
vector< map< size_t, Data< T > > > DistFar
 
vector< map< size_t, Data< T > > > DistNear
 
Lock * treelock = NULL
 
Node * kids [N_CHILDREN]
 
Node * lchild = NULL
 
Node * rchild = NULL
 
Node * sibling = NULL
 
Node * parent = NULL
 
unordered_map< size_t, Node * > * morton2node = NULL
 
bool isleaf
 
- Public Attributes inherited from hmlp::ReadWrite
deque< Task * > read
 
deque< Task * > write
 

Static Public Attributes

static const int N_CHILDREN = 2
 

Detailed Description

template<typename SETUP, typename NODEDATA>
class hmlp::tree::Node< SETUP, NODEDATA >

This is the default ball tree splitter. Given coordinates, compute the direction from the two most far away points. Project all points to this line and split into two groups using a median select.

end class SplitTask

Need to explit the parallelism.closure Parallel median search TODO: Can be parallelized This is the splitter used in the randomized tree. Given coordinates, project all points onto a random direction and split into two groups using a median select.

Need to explit the parallelism.Closure TODO: Can be parallelized

Member Typedef Documentation

template<typename SETUP , typename NODEDATA >
typedef SETUP::T hmlp::tree::Node< SETUP, NODEDATA >::T

Deduce data type from SETUP.

Constructor & Destructor Documentation

template<typename SETUP , typename NODEDATA >
hmlp::tree::Node< SETUP, NODEDATA >::Node ( size_t  morton)
inline

Constructor of local essential tree (LET) node: This constructor will only be used in the distributed environment.

template<typename SETUP , typename NODEDATA >
hmlp::tree::Node< SETUP, NODEDATA >::~Node ( )
inline

(Default) destructor

Member Function Documentation

template<typename SETUP , typename NODEDATA >
bool hmlp::tree::Node< SETUP, NODEDATA >::ContainAny ( vector< size_t > &  queries)
inline

Check if this node contain any query using morton. Notice that queries[] contains gids; thus, morton[] needs to be accessed using gids.

end Split()

template<typename SETUP , typename NODEDATA >
bool hmlp::tree::Node< SETUP, NODEDATA >::ContainAny ( set< Node< SETUP, NODEDATA > * > &  querys)
inline

end ContainAny()

template<typename SETUP , typename NODEDATA >
void hmlp::tree::Node< SETUP, NODEDATA >::DependOnChildren ( Task *  task)
inline

Support dependency analysis.

Try to enqueue if there is no dependency.

template<typename SETUP , typename NODEDATA >
void hmlp::tree::Node< SETUP, NODEDATA >::DependOnNoOne ( Task *  task)
inline

Try to enqueue if there is no dependency.

template<typename SETUP , typename NODEDATA >
void hmlp::tree::Node< SETUP, NODEDATA >::DependOnParent ( Task *  task)
inline

Try to enqueue if there is no dependency.

template<typename SETUP , typename NODEDATA >
void hmlp::tree::Node< SETUP, NODEDATA >::Print ( )
inline

end ContainAny()

template<typename SETUP , typename NODEDATA >
void hmlp::tree::Node< SETUP, NODEDATA >::Split ( )
inline

Early return if this is a leaf node.

TODO: need a better way

Member Data Documentation

template<typename SETUP , typename NODEDATA >
NODEDATA hmlp::tree::Node< SETUP, NODEDATA >::data

Per node private data

template<typename SETUP , typename NODEDATA >
vector<map<size_t, Data<T> > > hmlp::tree::Node< SETUP, NODEDATA >::DistFar

Node interaction lists recorded in MortonID. DistFar[ p ] contains a pair of gid and cached KIJ received from p.

template<typename SETUP , typename NODEDATA >
set<size_t> hmlp::tree::Node< SETUP, NODEDATA >::FarIDs

These two prunning lists are used when no NN pruning.

template<typename SETUP , typename NODEDATA >
Node* hmlp::tree::Node< SETUP, NODEDATA >::kids[N_CHILDREN]

All points to other tree nodes.

template<typename SETUP , typename NODEDATA >
size_t hmlp::tree::Node< SETUP, NODEDATA >::l

Level in the tree

template<typename SETUP , typename NODEDATA >
size_t hmlp::tree::Node< SETUP, NODEDATA >::morton = 0

Morton ID and offset.

template<typename SETUP , typename NODEDATA >
size_t hmlp::tree::Node< SETUP, NODEDATA >::n

Number of points in this node.

template<typename SETUP , typename NODEDATA >
const int hmlp::tree::Node< SETUP, NODEDATA >::N_CHILDREN = 2
static

Use binary trees.

template<typename SETUP , typename NODEDATA >
set<size_t> hmlp::tree::Node< SETUP, NODEDATA >::NearIDs

Only leaf nodes will have this list.

template<typename SETUP , typename NODEDATA >
set<size_t> hmlp::tree::Node< SETUP, NODEDATA >::NNFarIDs

These two prunning lists are used when in NN pruning.

template<typename SETUP , typename NODEDATA >
set<size_t> hmlp::tree::Node< SETUP, NODEDATA >::NNNearIDs

Only leaf nodes will have this list.

template<typename SETUP , typename NODEDATA >
SETUP* hmlp::tree::Node< SETUP, NODEDATA >::setup = NULL

This is the call back pointer to the shared setup.

template<typename SETUP , typename NODEDATA >
size_t hmlp::tree::Node< SETUP, NODEDATA >::treelist_id

ID in top-down topology order.

template<typename SETUP , typename NODEDATA >
Lock* hmlp::tree::Node< SETUP, NODEDATA >::treelock = NULL

Lock for exclusively modifying or accessing the tree.

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