University of California

Telcordia Technologies, Inc.

The Trdf Research & Development Foundation Ltd

Yuval Rabani

Rafail Ostrovsky

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.

Method for low distortion embedding of edit distance to Hamming distance

A method and system identify in a database one or more data entries that are the nearest neighbors of a query. The database prebuilds a first set of strings by probabilistically selecting values of respective bits in each of the first set of strings based on a probability that depends on a first hamming distance. Based on the first set of strings, the database predetermines the trace values of each data entry in the database, respectively, and stores the predetermined trace values as entries in a trace table. For each trace value entry, the database identifies the data entries whose trace values are within a second hamming distance of the trace value entry, and stores the addresses of the identified data entries in the trace value entry. When the database receives a query, by identifying the trace value entry in the trace table that match the trace value of the query, the database identifies the data entries that are within the first hamming distance of the query. In addition, a method and system estimate the hamming distance between two strings in a network.

Growing community of inventors

Haifa, Israel

Yuval Rabani