comparing kd-Tree and cover tree performance

main.cpp

#include "ofMain.h"
#include "ofxCoverTree.h"
#include "ofxKDTree.h"

float squaredDistance(vector<double> & v1, vector<double> & v2) {
    float dist=0;
    for (int i=0; i<v1.size(); i++) {
        float d = v2[i]-v1[i];
        dist += (d*d);
    }
    return dist;
}


int main( ){
    
    int nSamples = 10000;
    int dim = 200;

    // Generate random points
    vector<vector<double> > samples;
    for (int i=0; i<nSamples; i++) {
        float val = floor(ofRandom(100));
        vector<double> sample(dim);
        for (int d=0;d<dim;d++) {
            sample[d] = ofRandom(1);//val + ofRandom(-0.5, 0.5);
        }
        samples.push_back(sample);
    }
    
    vector<ofxCoverTree::item> items;
    ofxKDTree kdTree;
    
    for (int i=0; i<samples.size(); i++)
    {
        // add to cover tree
        ofxCoverTree::item item(dim);
        for (int j=0; j<samples[i].size(); j++) {
            item[j] = samples[i][j];
        }
        item.id = i;
        items.push_back(item);
        
        // add to kd-tree
        kdTree.addPoint(samples[i]);
    }
    
    
    // construct KD Tree
    clock_t t1 = clock();
    kdTree.constructKDTree();
    clock_t t2 = clock();
    
    // construct cover tree
    clock_t t3 = clock();
    ofxCoverTree::Default plant(items, 1.5);
    clock_t t4 = clock();
    
    
    cout << "kd-Tree construction time: "<<int(t2-t1)<<endl;
    cout << "CoverTree construction time: "<<int(t4-t3)<<endl;
    
    
    // generate random point for query
    vector<double> query_pt(dim);
    float val = floor(ofRandom(100));
    for (int d=0; d<dim; d++) {
        query_pt[d] = ofRandom(1);//val + ofRandom(-0.5, 5);
    }
    cout << "query point: "<<ofToString(query_pt) <<endl;
    
    // query kd-Tree
    vector<size_t> indexes;
    vector<double> dists;
    kdTree.getKNN(query_pt, 3, indexes, dists);
    for (int i=0; i<3; i++) {
        float dist = squaredDistance(query_pt, samples[indexes[i]]);
        cout << "nearest point (kd-tree): index "<<indexes[i]<<", distance: "<<dist<<endl;
        //        cout << ofToString(samples[indexes[i]]) << endl;
    }
    
    // query cover tree
    ofxCoverTree::item search_item(dim);
    for(size_t i = 0; i < dim; i++) {
        search_item[i] = query_pt[i];
    }
    vector<ofxCoverTree::item> results = plant.nearNeighbors(search_item, 3);
    for (auto r : results) {
        vector<double> p(dim);
        for (int i=0; i<dim; i++) {p[i] = r[i];}
        float dist = squaredDistance(query_pt, p);
        cout << "nearest point (cover tree): index "<<r.id<<", distance: "<<dist<<endl;
        //        cout << ofToString(r) << endl;
    }
    
}