Piotr Indyk
ABSTRACT
We present a data structure for the approximate nearest neighbor problem under edit metric (which is defined as the minimum number of insertions, deletions and character substitutions needed to transform one string into another). For any l ≥ 1 and a set of n strings of length d, the data structure reports a 3l-approximate Nearest Neighbor for any given query string q in O(d) time. The space requirement of this data structure is roughly O(nd1/(l+1)), i.e., strongly subexponential. To our knowledge, this is the first data structure for this problem with both o(n) query time and storage subexponential in d.
- Approximate Nearest Neighbor under edit distance via product metrics
Recommendations
Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings
FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer ScienceHausdorff metrics are used in geometric settings for measuring the distance between sets of points. They have been used extensively in areas such as computer vision, pattern recognition and computational chemistry.While computing the distance between a ...
Nearest neighbour distance matrix classification
ADMA'10: Proceedings of the 6th international conference on Advanced data mining and applications: Part IA distance based classification is one of the popular methods for classifying instances using a point-to-point distance based on the nearest neighbour or k-NEAREST NEIGHBOUR (k-NN). The representation of distance measure can be one of the various ...
Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance
ISAAC '08: Proceedings of the 19th International Symposium on Algorithms and ComputationThe Hausdorff distance is a measure for the resemblance of two geometric objects. Given a set of n point patterns and a query point pattern Q , the nearest neighbor of Q under the Hausdorff distance is the point pattern which minimizes this distance to Q . ...
Comments