Summary:
Nearest neighbor searching (NNS) is a fundamental problem with several
important applications.
To accelerate the queries, we exploit the fact that
data often exhibits highly nonrandom spatial patterns.
We consider input points almost lying on about $\log^t n$ unknown lines
in a space of constant dimension $d$,
where $n$ is the number of points and $t$ constant.
The lines are distributed uniformly in a bounding sphere,
the points are distributed uniformly on each line, and their number
per line varies from $\Omega (\log^t n)$ to $O(n)$.
Queries take $O( \log \log n / \epsilon^{O(d^2)})$ expected time, which is
exponentially faster than without structure,
using optimal space $O(n)$, and return a
$(1+\epsilon)$-approximate nearest neighbor, for any given $\epsilon>0$.
Ignoring the step of NNS on a line, queries take
$O( \log^2 \log n / \epsilon^{O(d^2)})$ with high probability.
Our key step is to employ a reduction of determining the nearest line
to NNS among points.
Keywords:
Nearest line, Aligned points, Structured data, Exponential speedup, Optimal space
