MSc Thesis Defence by Sorin Adrian Robert Davidoi – Københavns Universitet

MSc Thesis Defence by Sorin Adrian Robert Davidoi


Nearest-Neighbour Fields Computation via Propagation-Assisted Parallel KD-Trees


In this thesis we propose three techniques for improving the running time of constructing an Approximate Nearest-Neighbour Field (ANNF). Each of them is focused on different parts: taking better advantage of the CPU architecture, exploiting the overlap between queries using propagation and making a tradeoff between accuracy and runtime performace. All these methods are implemented and integrated in the bufferkdtree package. We show that the performance of the propagation techniques is greatly dependent on the dataset, that optimizing memory access patterns does not lead to a significant reduction in running time and that using a metric called branch potential to reduce the search space achieves a dramatic performance increase with a negligible decrease in accuracy.


Fabian Gieseke

External Examiner

Ira Assent