Abstract
Nearest neighbor search is a fundamental computational tool and has wide applications. In past decades, many datastructures have been developed to speed up this operation. In this paper, we propose a novel hierarchical datastructure for nearest neighbor search in moderately high dimension. Our proposed method maintains good run time guarantees, and it outperforms several state-of-the-art methods in practice.
Introduction
Nearest Neighbor (NN) search—finding the closest point in a dataset to a given query—is a cornerstone of machine learning, utilized in applications ranging from $k$-NN classification to reinforcement learning. While a simple linear scan is sufficient for small datasets, it becomes computationally expensive ($O(n)$) as data scales.
Existing solutions like kd-trees struggle in high-dimensional spaces. Hierarchical structures such as Cover Trees (CT) and the Simplified Nearest Ancestor Cover Tree (SNACT) were designed to handle "moderately high" dimensions more efficiently by organizing data into leveled trees. However, even these advanced structures often perform more distance calculations than necessary. This paper introduces more aggressive pruning techniques to bridge the gap between theoretical efficiency and practical performance, discarding large portions of the search space earlier in the query process.
Proposed Methodology
The proposed method (PM) builds upon the SNACT framework, which ensures every node is its own nearest ancestor. To this foundation, three novel pruning innovations are integrated:
- Range List ($rl$): Instead of a single maximum distance for descendants, the method stores a list of maximum distances categorized by hierarchy level. This allows for precise pruning of specific level ranges within a subtree.
- Opposite Quadrant Pruning: By treating a parent node as the origin of a $d$-dimensional coordinate system, child nodes are assigned to one of $2^d$ quadrants. If a query point and a candidate node reside in "opposite quadrants" relative to the parent, the node can often be safely ignored.
- Vectorial Angle Cosine ($vac$): This technique uses the geometry of the current search. If $p$ is the best neighbor found so far for query $q$, the algorithm prunes points on the "far side" of a hyperplane passing through $p$ perpendicular to $pq$ using a computationally cheap cosine calculation.
Crucially, these modifications do not alter the fundamental tree structure, allowing the algorithm to retain a logarithmic runtime bound of $O(c^6 \log n)$.
Experimental Evaluation
The researchers evaluated the PM against the standard Cover Tree (CT) and SNACT using three benchmark datasets representing moderately high dimensionality: yearpredict (90 dimensions), corel (32 dimensions), and artificial40 (40 dimensions).
Key Results
The proposed method consistently outperformed competitors across all test cases. When results were normalized against the standard Cover Tree (CT = 1.0), the PM achieved significant reductions in query costs:
- Efficiency Gains: On the
coreldataset, the PM achieved a score of 0.33, making it approximately 3x faster than a standard Cover Tree and 44% faster than SNACT (0.59). - Consistency: Across all datasets, the PM reduced query costs by 38%–67% compared to CT and 24%–46% compared to SNACT.
An ablation study confirmed that each component contributed to the overall performance: Quadrant Info (QI) provided an ~8% boost, Range Lists (RI) ~20%, and Directional Info (DI) ~30%. Their combination in the PM yielded the full synergistic improvement of approximately 46% over SNACT.
Discussion and Conclusion
While the proposed method shows impressive practical gains in moderately high dimensions, some limitations remain. As dimensionality reaches into the hundreds or thousands, hierarchical structures may still degrade toward linear scan performance. Additionally, the quadrant method's reliance on $2^d$ partitions may face overhead as $d$ increases. Future work could involve extending these geometric heuristics to general metric spaces where only distances, rather than explicit coordinates, are available. Nevertheless, the PM represents a significant advancement in practical nearest neighbor search efficiency.
Summary updated