An Improved Hierarchical Datastructure for Nearest Neighbor Search

Mengdie Nie, Zhi-Jie Wang, Chunjing Gan, Zhe Quan, Bin Yao, Jian YinAAAI 2019 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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)$.

Ablation study showing the cumulative impact of individual pruning strategies (QI, RI, DI) on the final query cost of the Proposed Method (PM).

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 corel dataset, 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.
Comparison of normalized query costs across three datasets for CT, SNACT, and the proposed method (PM), highlighting the superior performance of PM.

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

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.
BibTeX
@inproceedings{nie2019improved,
  author = {Mengdie Nie and Zhi-Jie Wang and Chunjing Gan and Zhe Quan and Bin Yao and Jian Yin},
  title = {{An Improved Hierarchical Datastructure for Nearest Neighbor Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=sSNhY0P04z},
}
Figure