This project implements 2 geometric data structures, KD-tree[1] and Ball* Tree[2] and benchmarks their performance on various datasets. For a complete discussion about our project, please see our Report.
For detailed information about the required packages and environment setup, please see the Environment Setup Documentation.
A detailed explanation of the project's directory structure is available here.
Further information about how to conduct experiments is described in Experiments instruction.
This project implements the following data structures as described in these papers:
- KD-Tree by Jon Louis Bentley, Multidimensional Binary Search Trees used for Associative Searching (1975).
- Ball*-Tree by Mohamad Dolatshah, Ali Hadian, and Behrouz Minaei-Bidgoli, Ball-Tree: Efficient Spatial Indexing for Constrained Nearest-Neighbor Search in Metric Spaces* (arXiv:1511.00628).