paper critique & summarization :Algorithm for Fast Vector Quantization

Title : Algorithms for Fast Vector Quantization
Authors : Sunil Arya, David M. Mount

summarization:

This paper proposed three algorithms:

The first is the standard K-d tree with incremental distance calculation, which use a offset technique, to examine surrounding buckets to check that if any point is more near but in different buckets, to find the really nearly neighbor points with query point.

The second algorithm is the priority k-d three search, which try to find the nearly neighbor before run to the all algorithm termination. It maintains a priority queue which record the priority of every possibly subtree, and search will terminate when the queue empty(means that all tree have been traversed) or the highest priority subtree has larger distance to query point than the closest point we find in the sequence step.

And the third algorithm is the Neighborhood graphs, which is a simple and greedy algorithm.
It builds graph from data points by the rule that if any two points, we can't find any point which has both shorter distance to this two point than the distance between these two points, then they have a edge. And the algorithm expand the points that is closest to the query point recursively, until arrive at a point which its neighbor are all expanded or get a predefined number. Then output the closest data point visited.

critique:

Actually, what I care about of this issue is how they perform on the high dimensions domain, the dimensions of their test data are just 8~16, for my research, the dimensions always over then 100, and we have known that at least for the standard K-d tree, we have worse performance in time issue, so maybe we need to find another quantization method in image retrieval domain.