Lower bounds for embedding edit distance into normed spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for embedding edit distance into normed spaces

Full text

Pdf (353 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 8B table of contents

Pages: 523 - 526

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

A. Andoni	MIT
M. Deza	ENS, France
A. Gupta	Bell Labs
P. Indyk	MIT
S. Raskhodnikova	MIT

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 64, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

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

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	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
	2	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
	3	{DL76} D. Dobkin and R. Lipton. Multidimensional search problems. SIAM Journal on Computing, 5:181--186, 1976.
	4	{DL97} M. M. Deza and M. Laurent. Geometry of Cuts and Metrics. Algorithms and Combinatorics 15. Springer-Verlag, Berlin etc., 1997.
	5	{LLR94} N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
	6	Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
	7	S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335353]

CITED BY 8

	Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	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
	Tuğkan Batu , Funda Ergun , Cenk Sahinalp, Oblivious string embeddings and edit distance approximations, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.792-801, January 22-26, 2006, Miami, Florida
	Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida
	Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Parikshit Gopalan , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Estimating the sortedness of a data stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.318-327, January 07-09, 2007, New Orleans, Louisiana
	Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Journal of the ACM (JACM), v.54 n.5, p.23-es, October 2007
	Chuan Xiao , Wei Wang , Xuemin Lin, Ed-Join: an efficient algorithm for similarity joins with edit distance constraints, Proceedings of the VLDB Endowment, v.1 n.1, August 2008