KNN Classifier in C++
Project Description
A high-performance implementation of the K-Nearest Neighbors (KNN) algorithm in C++, built from scratch with a focus on modularity, extensibility, and computational efficiency. Supports both brute-force and KD-Tree–based approaches with OpenMP parallelization, benchmarked on Fashion MNIST.
Features
- Custom Vector Class: Abstraction over
std::vector<double>with dot product, L2 norm, and Euclidean distance - Brute-Force KNN: Exact neighbor search with optional OpenMP parallelization
- KD-Tree Accelerator: Recursive construction with heap-based k-NN querying for fast high-dimensional search
- CLI Interface: Built with
cxxopts— configure algorithm, neighbors, dataset path, OpenMP toggle at runtime - Data Utilities: CSV loading, train-test splitting, accuracy evaluation with chrono benchmarking
Benchmarks (Fashion MNIST, 10K samples, 734-D)
- Brute-Force (OpenMP): ~6.5s at 84.04% accuracy vs ~362s serial (≈55× speedup)
- KD-Tree (OpenMP): ~7.5s vs ~19s serial (≈2.5× speedup)
Technical Stack
- Language: C++17
- Libraries: OpenMP, C++ STL, cxxopts
- Tools: g++, CMake, VS Code, Makefile