Thumbnail
Access Restriction
Open

Author Ostrovsky, Rafail ♦ Rabani, Yuval ♦ Matching, Pattern
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Edit Distance ♦ Low Distortion Embeddings ♦ Various Computational Problem ♦ Previous Bound ♦ Communication Complexity ♦ Neighbor Search ♦ Cient Implementation
Abstract We show that endowed with edit distance embeds into #1 with distortion 2 . We further show e#cient implementations of the embedding that yield solutions to various computational problems involving edit distance. These include sketching, communication complexity, nearest neighbor search. For all these problems, we improve upon previous bounds.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2005-01-01