ANN queries: covering Voronoi diagram with hyperboxes

Details ANN queries: covering Voronoi diagram with hyperboxes ANN queries: covering Voronoi diagram with hyperboxes

2011-11-25

arxiv.org/abs/1111.5893v1

Computer Science

Computational Geometry

Scientific paper

Given a set $S$ of $n$ points in $d$-dimensional Euclidean metric space $X$ and a small positive real number $\epsilon$, we present an algorithm to preprocess $S$ and answer queries that require finding a set $S' \subseteq S$ of $\epsilon$-approximate nearest neighbors (ANNs) to a given query point $q \in X$. The following are the characteristics of points belonging to set $S'$: - $\forall s \in S'$, $\exists$ a point $p \in X$ such that $|pq| \le \epsilon$ and the nearest neighbor of $p$ is $s$, and - $\exists$ a $s' \in S'$ such that $s'$ is a nearest neighbor of $q$. During the preprocessing phase, from the Voronoi diagram of $S$ we construct a set of box trees of size $O(4^d\frac{V}{\delta}(\frac{\pi}{\epsilon})^{d-1})$ which facilitate in querying ANNs of any input query point in $O(\frac{1}{d}lg \frac{V}{\delta} + (\frac{\pi}{\epsilon})^{d-1})$ time. Here $\delta$ equals to $(\frac{\epsilon}{2\sqrt{d}})^d$, and $V$ is the volume of a large bounding box that contains all the points of set $S$. The average case cardinality of $S'$ is shown to rely on $S$ and $\epsilon$.

Affiliated with

Also associated with

No associations

Rating

ANN queries: covering Voronoi diagram with hyperboxes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with ANN queries: covering Voronoi diagram with hyperboxes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ANN queries: covering Voronoi diagram with hyperboxes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-173581