The nearest neighbor problem which is also known as post-office
problem [30] has been studied extensively in the past.
There are efficient query algorithms
for two- or three- dimensional cases [9, 19].
However, there is still a lack of efficient solutions for
the dimensionality higher than three.
k-d tree based nearest neighbor algorithms have been widely used
in computer vision [2, 45]. k-d trees are extremely
versatile and efficient to use in low dimensional cases. However, the
performance degrades exponentially in high dimensional cases.
R-tree and its variants [25, 37, 1] have similar
performance of nearest neighbor searches in high dimensions.
In [17], we present an efficient algorithm which uses
a hierarchical quasi-Voronoi diagram
to search for the nearest neighbor.
Table 3 shows average computation time for each sequence on the SGI INDIGO 2. The time was obtained based on the two different nearest neighbor query approaches, namely, the linear search and the hierarchical quasi-Voronoi diagram in [17]. As shown in the figure, the use of the hierarchical quasi-Voronoi diagram approach dramatically improves the query time.
Table 3: Time of two nearest neighbor query approaches