Method for low distortion embedding of edit distance to...

Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C714S755000, C714S786000

Reexamination Certificate

active

08060808

ABSTRACT:
A method of embedding the edit distance metric into the Hamming distance metric with low distortion. In other words, two input character strings are mapped to two corresponding output bit strings such that the Hamming distance between the output strings is approximately proportional to the edit distance between the two corresponding input strings.

REFERENCES:
patent: 4490811 (1984-12-01), Yianilos et al.
patent: 4888779 (1989-12-01), Karabed et al.
patent: 5289391 (1994-02-01), Ibrahim et al.
patent: 5432803 (1995-07-01), Liu et al.
patent: 5865637 (1999-02-01), Shinozaki et al.
patent: 6084535 (2000-07-01), Karabed et al.
patent: 6119124 (2000-09-01), Broder et al.
patent: 6226640 (2001-05-01), Ostrovsky et al.
patent: 6452985 (2002-09-01), Hatakeyama et al.
patent: 7321995 (2008-01-01), Kikuchi et al.
patent: 2006/0212860 (2006-09-01), Benedikt et al.
(Qin Lv, Kai Li and Mosses charikar) Image Similarity Search with Compact Data Structures, Nov. 8, 2004, Department of Computer Science princeton University, pp. 1-10.
PCT International Search Report for PCT/US06/07183, Applicant: The Regents of the University of California, Forms PCT/ISA/210 and 220, dated Dec. 31, 2007 (5 pages).
PCT Written Opinion of the International Search Authority for PCT/US06/07183, Applicant: The Regents of the University of California, Form PCT/ISA/237, dated Dec. 31, 2007 (5 pages).
Corrected PCT International Search Report for PCT/US06/07183, Applicant: The Regents of the University of California, Forms PCT/ISA/224 and 210, dated Mar. 24, 2009 (4 pages).
Corrected PCT Written Opinion of the International Search Authority for PCT/US06/07183, Applicant: The Regents of the University of California, Forms PCT/ISA/224 and 237, dated Mar. 24, 2009 (4 pages).
PCT International Preliminary Report on Patentability (Chapter I of the Patent Cooperation Treaty) for PCT/US2006/007183, Applicant: The Regents of the University of California, Form PCT/IB/326 and 373, dated Apr. 9, 2009 (5 pages).
Ostrovsky, R., et al., “Low Distortion Embedding for Edit Distance”, Preliminary. The proceedings version appeared at STOC 2005, Computer Science Department, University of California at Los Angeles, 90095, USA and Computer Science Department, Technion—Israel Institute of Technology, Haifa, 32000, Israel, Aug. 2005 (16 pages).
Andoni, A., et al., “Lower Bounds for Embeddings of Edit Distance into Normed Spaces”, Jan. 2003 (4 pages).

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method for low distortion embedding of edit distance to... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for low distortion embedding of edit distance to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for low distortion embedding of edit distance to... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4312108

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.