3 papers
cs.DS2019
The One-Way Communication Complexity of Dynamic Time Warping Distance
Vladimir Braverman, Moses Charikar, William Kuszmaul +2
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetil…
cs.DS2018
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
Moses Charikar, Ofir Geri, Michael P. Kim +1
Edit distance is a fundamental measure of distance between strings and has been widely studied in computer science. While the problem of estimating edit distance has been studied e…
cs.DS2016
Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables
William Kuszmaul
Cuckoo hashing guarantees constant-time lookups regardless of table density, making it a viable candidate for high-density tables. Cuckoo hashing insertions perform poorly at high…