# Why don't we use space filling curves for high-dimensional nearest neighbor search?

Some space filling curves like the Hilbert Curve are able to map an n-dimensional space to a one dimensional line whilst preserving locality. Does that mean that we could map a dataset of high dimensional points to a line and expect the order of the nearest neighbors to be preserved?

If so, wouldn't that be more efficient than building a Ball tree?

The idea is as follows. Let $$f$$ be a space-filling curve. Given a point $$x$$, index it as $$f^{-1}(x)$$.* Given a query point $$y$$, return all points indexed in an interval around $$f^{-1}(y)$$. If $$y$$ is close to $$x$$, there is a good chance that $$x$$ will be returned so long as $$f^{-1}$$ tends to preserve locality. Different space filling curves have this property to different degrees.
* Note that space-filling curves are not injective so the inverse is not uniquely defined. But in practice we choose a finite grid on $$[0, 1]^n$$ and an appropriate iterate that is bijective so we don't have a problem.