The paper introduces a new data structure called a *cover tree* for efficient nearest neighbor (NNS) operations in general metric spaces. The cover tree is designed to be space-efficient, requiring only $O(n)$ space, where $n$ is the number of points in the dataset. The construction time is $O(c^2 n \log n)$ if the dataset has an expansion constant $c \geq 2$, and the query time for finding the nearest neighbor is $O(c^{2.5} \log n)$. The paper also presents batch construction and lazy query variants of the cover tree, which offer further improvements in performance. Experimental results on various machine learning datasets show that the cover tree can achieve speedups ranging from 1 to 2000 compared to brute force search. The cover tree is particularly effective for datasets with low intrinsic dimensionality, as measured by the Karger-Ruhl or Krauthgamer-Lee dimensions. The paper provides a detailed analysis of the cover tree's runtime complexity and compares it to other algorithms, demonstrating its competitive performance in practical applications.The paper introduces a new data structure called a *cover tree* for efficient nearest neighbor (NNS) operations in general metric spaces. The cover tree is designed to be space-efficient, requiring only $O(n)$ space, where $n$ is the number of points in the dataset. The construction time is $O(c^2 n \log n)$ if the dataset has an expansion constant $c \geq 2$, and the query time for finding the nearest neighbor is $O(c^{2.5} \log n)$. The paper also presents batch construction and lazy query variants of the cover tree, which offer further improvements in performance. Experimental results on various machine learning datasets show that the cover tree can achieve speedups ranging from 1 to 2000 compared to brute force search. The cover tree is particularly effective for datasets with low intrinsic dimensionality, as measured by the Karger-Ruhl or Krauthgamer-Lee dimensions. The paper provides a detailed analysis of the cover tree's runtime complexity and compares it to other algorithms, demonstrating its competitive performance in practical applications.