Sahinalp. Oblivious string embeddings and edit distance approximations (2005)
Abstract We introduce an oblivious embedding that maps stringsof length n under edit distance to strings of length atmost n/r under edit distance for any value of parameter r. For any given r, our...
Oblivious String Embeddings and Edit Distance Approximations (2005)
Tugkan Batu Funda, Funda Ergun, Cenk Sahinalp
We introduce an oblivious embedding that maps any string of length n to a string of length at most n/r for any user specified value of r. For any given r, our embedding provides a distortion of O(r...
Oblivious String Embeddings and Edit Distance Approximations (2005)
Tugkan Batu Funda, Funda Ergun, Cenk Sahinalp
We introduce an oblivious embedding that maps any string of length n to a string of length at most n/r for any user specified value of r. For any given r, our embedding provides a distortion of O(r...
The structure and evolution of centromeric transition regions within the human genome (2004)
Xinwei She, Julie E. Horvath, Zhaoshi Jiang, Ge Liu, Terrence S. Furey, Laurie Christ, ...
Obliviously Approximating Sequence Distances (2000)
There are several applications for schemes which approximately find the distance between two sequences in a way that is `oblivious' of one of the sequences up until a final sublinear number of...