Name
Abstract | ||
|---|---|---|
We give an efficient protocol for sequence comparisons of the edit-distance kind, such that neither party reveals anything about their private sequence to the other party (other than what can be inferred from the edit distance between their two sequences - which is unavoidable because computing that distance is the purpose of the protocol). The amount of communication done by our protocol is proportional to the time complexity of the best-known algorithm for performing the sequence comparison.The problem of determining the similarity between two sequences arises in a large number of applications, in particular in bioinformatics. In these application areas, the edit distance is one of the most widely used notions of sequence similarity: It is the least-cost set of insertions, deletions, and substitutions required to transform one string into the other. The generalizations of edit distance that are solved by the same kind of dynamic programming recurrence relation as the one for edit distance, cover an even wider domain of applications. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1145/1005140.1005147 | WPES |
Keywords | Field | DocType |
private sequence,least-cost set,best-known algorithm,large number,private sequence comparison,dynamic programming recurrence relation,application area,sequence similarity,sequence comparison,edit-distance kind,efficient protocol,dynamic programming,edit distance,longest common subsequence,time complexity,recurrence relation,privacy,string matching,secure multi party computation | String searching algorithm,Edit distance,String-to-string correction problem,Longest common subsequence problem,Computer science,Wagner–Fischer algorithm,Jaro–Winkler distance,Algorithm,Theoretical computer science,Damerau–Levenshtein distance,Time complexity | Conference |
ISBN | Citations | PageRank |
1-58113-776-1 | 103 | 4.77 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikhail J. Atallah | 1 | 3828 | 340.54 |
| Florian Kerschbaum | 2 | 1186 | 89.43 |
| wenliang du | 3 | 4906 | 241.77 |