Parallel implemetation of vpTree

Description

This project aims to implement and parallelize the construction of a vantage-point tree, a data structure used for k-nearest neighbor (kNN) search, in the C programming language.

The project is divided into several tasks:

1. Implement Vantage-Point Tree in C

Sequential implementation of vpTree in C.

2. Parallelization with Pthreads:

In this step, the implementation is parallelized using Pthreads (POSIX Threads). There are two primary areas for parallelization:

• Computing distances between points in parallel.
  
• Computing the inner and outer sets in parallel.

3. Thresholding Parallel Calls:

The code was modified to switch to sequential execution for small workloads and restrict the maximum number of live threads to optimize performance.

4. Reimplementation with OpenMP and Cilk

In the final step, the project explores high-level parallelism expressions using Cilk and OpenMP.