48 std::vector<ScalarType>
_x;
81 for(
int d = 0; d < t1.
dimensionality(); d++) dd += (t1.
x(d) - t2.
x(d)) * (t1.
x(d) - t2.
x(d));
86 template<
typename T, ScalarType (*distance)( const T&, const T& )>
92 VpTree() : _items(), _tau(0.0), _root(0) {}
100 void create(
const std::vector<T>& items) {
103 _root = buildFromPoints(0, items.size());
107 void search(
const T& target,
int k, std::vector<T>* results, std::vector<ScalarType>* distances)
111 std::priority_queue<HeapItem> heap;
117 search(_root, target, k, heap);
120 results->clear(); distances->clear();
121 while(!heap.empty()) {
122 results->push_back(_items[heap.top().index]);
123 distances->push_back(heap.top().dist);
128 std::reverse(results->begin(), results->end());
129 std::reverse(distances->begin(), distances->end());
148 Node() : index(0), threshold(0.), left(0), right(0) {}
165 index(indexv), dist(distv) {}
169 return dist < o.
dist;
186 if (upper == lower) {
194 if (upper - lower > 1) {
198 std::swap(_items[lower], _items[i]);
201 int median = (upper + lower) / 2;
202 std::nth_element(_items.begin() + lower + 1,
203 _items.begin() + median,
204 _items.begin() + upper,
212 node->
left = buildFromPoints(lower + 1, median);
213 node->
right = buildFromPoints(median, upper);
221 void search(
Node* node,
const T& target,
int k, std::priority_queue<HeapItem>& heap)
223 if(node == NULL)
return;
230 if(heap.size() ==
static_cast<size_t>(k)) heap.pop();
232 if(heap.size() ==
static_cast<size_t>(k)) _tau = heap.top().dist;
236 if(node->
left == NULL && node->
right == NULL) {
241 if(dist < node->threshold) {
242 search(node->
left, target, k, heap);
245 search(node->
right, target, k, heap);
250 search(node->
right, target, k, heap);
252 if (dist - _tau <= node->threshold) {
253 search(node->
left, target, k, heap);
ScalarType distance(Callback &cb, const CoverTreePoint< RandomAccessIterator > &l, const CoverTreePoint< RandomAccessIterator > &r, ScalarType upper_bound)
Namespace containing implementation of t-SNE algorithm.
bool operator()(const T &a, const T &b)
bool operator<(const HeapItem &o) const
DataPoint(const DataPoint &other)
HeapItem(int indexv, ScalarType distv)
void search(const T &target, int k, std::vector< T > *results, std::vector< ScalarType > *distances)
ScalarType uniform_random()
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
DistanceComparator(const T &itemv)
std::vector< ScalarType > _x
ScalarType x(int d) const
void search(Node *node, const T &target, int k, std::priority_queue< HeapItem > &heap)
int dimensionality() const
ScalarType euclidean_distance(const DataPoint &t1, const DataPoint &t2)
void create(const std::vector< T > &items)
DataPoint(int Dv, int indv, ScalarType *xv)
DataPoint & operator=(const DataPoint &other)
Node * buildFromPoints(int lower, int upper)
static const NeighborsMethod VpTree("Vantage point tree")
Vantage point tree -based method.