stavrosfil / distributed-knn Goto Github PK

This is a followup issue for discussion on the benchmarks and plots to be created for the report. Refer to #22 for the initial discussion.

On each process, after receiving the new serialized tree, the kNN heap is missing, as it is a member of the VPT object of the previous process and kNN update fails.

Should be addressed by #6

Investigate better suited routines for calculating all-to-all euclidean distance matrix. Report speedups.

In the current state, the vp-tree is created by having at least b points linked to every leaf. When, for example a leaf has 100 points, kNN search must validate the query point against all 100.

• Use matrix multiplication (probably using BLAS) to calculate the distances more efficiently.
• Sort the resulting array, and then add points to heap one by one until the max is reached.

For large values of m, n, block the query Y and compute the distance matrix one block at a time, to avoid storing large intermediate distance matrices.

Need to fix the case that X and Y have some common points. In that case, y should reject adding itself to its kNN.

Originally posted by @georgegito in #1 (comment)