- P.K. Agarwal, A. Gionis, L. Guibas, and R. Motwani. Rank-based similarity searching. Manuscript, 1998.Google Scholar
- H. Alt and M. Godau. Computing the frechet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 5:75--91, 1995.Google ScholarCross Ref
- H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook on Computational Geometry, pages 121--153. North-Holland, 2000. To appear.Google ScholarCross Ref
- S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 573--582, 1994. Google ScholarDigital Library
- K. Clarkson. A randomized algorithm for closest-point queries. SIAM Journal on Computing, 17:830--847, 1988. Google ScholarDigital Library
- G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2002. Google ScholarDigital Library
- G. Cormode, M. Paterson, C. Sahinalp, and U. Vishkin. Communication complexity of document exchange. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2000. Google ScholarDigital Library
- M. Farach-Colton and P. Indyk. Approximate nearest neighbor algorithms for hausdorff metrics via embeddings. Proceedings of the Symposium on Foundations of Computer Science, 1999. Google ScholarDigital Library
- S. Har-Peled. A replacement for voronoi diagrams of near linear size. Proceedings of the Symposium on Foundations of Computer Science, 2001. Google ScholarDigital Library
- P. Indyk. On approximate nearest neighbors in $l&infty; norm. Journal of Computer and System Sciences, to appear. Preliminary version appeared in Proceedings of the Symposium on Foundations of Computer Science, 1998. Google ScholarDigital Library
- P. Indyk. Dimensionality reduction techniques for proximity problems. Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms, 2000. Google ScholarDigital Library
- P. Indyk and R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality. Proceedings of the Symposium on Theory of Computing, 1998. Google ScholarDigital Library
- J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997. Google ScholarDigital Library
- E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proceedings of the Thirtieth ACM Symposium on Theory of Computing, pages 614--623, 1998. Google ScholarDigital Library
- S. Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106:286--303, 1993. Google ScholarDigital Library
- S. Muthukrishnan and C. Sahinalp. Approximate sequence nearest neighbors. Proceedings of the Symposium on Theory of Computing, 2000.Google Scholar
Index Terms
- Approximate nearest neighbor algorithms for Frechet 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 under edit distance via product metrics
SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithmsWe 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 ...
Comments