Hubert Bernacki

The nearest neighbor search problem asks how to preprocess a set S of n points in ℝ^d, under a given Minkowski metric, to answer the following query: given a point q, find its closest point in S. This problem arises naturally in many branches of computer science, including machine learning, bioinformatics, and computational geometry. Before Arya et al. published “An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions”, much of the focus was on exact search with O(log n) query time and O(n) auxiliary space, but achieving these bounds proved difficult.

The authors considered an approximate version, where the goal is to find a point in S whose distance from q is at most (1 + ε) times the distance to its nearest neighbor. For fixed dimension d and fixed ε > 0, they achieve O(n) space and O(log n) query time. In this presentation, we will look at the BBD-trees that achieve these results.

1. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions (1998).
2. Hubert Bernacki. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. slides. (2026).