Approximate nearest neighbor algorithms for Frechet distance via product metrics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate nearest neighbor algorithms for Frechet distance via product metrics

Full text

Pdf (156 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eighteenth annual symposium on Computational geometry table of contents

Barcelona, Spain

Pages: 102 - 106

Year of Publication: 2002

ISBN:1-58113-504-1

Author

Piotr Indyk

MIT

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 27, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/513400.513414 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P.K. Agarwal, A. Gionis, L. Guibas, and R. Motwani. Rank-based similarity searching. Manuscript, 1998.
	2	H. Alt and M. Godau. Computing the frechet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 5:75--91, 1995.
	3	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.
	4	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	5	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	6	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	7	Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
	8	Martin Farach-Colton , Piotr Indyk, Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.171, October 17-18, 1999
	9	S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
	10	Piotr Indyk, On approximate nearest neighbors under I norm, Journal of Computer and System Sciences, v.63 n.4, p.627-638, December 2001 [doi>10.1006/jcss.2001.1781]
	11	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	12	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	13	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
	14	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	15	S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057]
	16	S. Muthukrishnan and C. Sahinalp. Approximate sequence nearest neighbors. Proceedings of the Symposium on Theory of Computing, 2000.

CITED BY 5

	Piotr Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Piotr Indyk, Approximate Nearest Neighbor under edit distance via product metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida
	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Overcoming the l₁ non-embeddability barrier: algorithms for product metrics, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.865-874, January 04-06, 2009, New York, New York
	Kevin Buchin , Maike Buchin , Yusu Wang, Exact algorithms for partial curve matching via the Fréchet distance, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.645-654, January 04-06, 2009, New York, New York