How can I make k nearest neighbor queries fast on unit hypersphere?

Question

I have $m$ points $D = \{x_1, \dots, x_m\}$ with $x_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y_i \in \mathbb{R}^n$ with $i=1, \dots, T$. Each query comes at a time and independently. The datastructures for the queries should not be modified by the past queries. After receiving an query $y_i$, the $k$ nearest neighbors

$$NN_k(y_i) \subset D \text{ with } |NN_k(y_i)| = k \text{ and }$$ $$\forall x_a \in NN_k(y_i) \forall x_b \in D \setminus NN_k(y_i) : \|x_a - y_j\|_2 \leq \|x_b - y_j\|_2$$

All points $x_i$ and all queries $y_j$ are on the unit hypersphere, so $\|x_i\|_2 = \|y_i\|_2 = 1$.

How do I process those queries fast?

Limits

To get a feeling for what matters, here are some orders of magnitude:

• $100 \leq n \leq 1000$: Dimension of points
• $m \geq 100\,000$: Candidates
• $T \geq 10\,000\,000$: Number of queries
• $3 \leq k \leq 20$: Expected number of returned points
• Reasonable memory consumption (e.g. less than 2GB for the data structure)

The query time for a single brute force approach is in $\mathcal{O}(m \cdot n)$ as it just compares every candidate point in $D$ with the query and stores the closest $k$ of them.

Misc

I've just implemented this with Python (see code).

• k=5, n=128, m=100000, T=100: 0.56s per query. (Brute force approach)

That is actually much better than I expected. However, I guess this could be an order of magnitude faster with a good data structure / smarter algorithm. I wrote the Python script in a way which should make it easy to run your own experiments on your tests, if you like.

Answer 1

As a rule of thumb, when the number of dimensions $n$ is less than about 10, fancy data structures (like k-d trees) work well; when the number of dimensions is greater than about 30, fancy data structures typically perform poorly and may be no better than a brute-force linear scan. Wikipedia lists a similar rule of thumb: if $m \gg 2^n$ (where $m$ is the number of points in the data structure and $n$ is the number of dimensions), then k-d trees work well, otherwise they won't. Exceptions exist, e.g., where your data is "structured" and non-random, but this is probably a good first guideline.

In your example, the number of dimensions is at least 100. Therefore, I wouldn't expect any of the fancy data structures (k-d trees, M-trees, etc.) to be better than the simple linear scan.

Essentially, you are suffering from the curse of dimensionality.

You mention that your points are all on the surface of the hypersphere. Unfortunately, this doesn't help much. Heuristically, points on the surface of a $n$-dimensional hypersphere are a lot like points in a $n-1$-dimensional space.

Answer 2

Points of an high-dimensional metric space may efficiently be indexed by an M-tree. An in-depth discussion of the data structure and of your problem may be found in this paper.