Skip to main content

The One-Way Communication Complexity of Dynamic Time Warping Distance

Author(s): Braverman, Vladimir; Charikar, Moses; Kuszmaul, William; Woodruff, David P; Yang, Lin F

To refer to this page use:
Abstract: 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 O~(n/alpha) bits for the problem of computing an alpha-approximation for DTW between strings x and y of length n, and we prove a lower bound of Omega(n / alpha) bits for the same problem. Our communication protocol works for strings over an arbitrary metric of polynomial size and aspect ratio, and we optimize the logarithmic factors depending on properties of the underlying metric, such as when the points are low-dimensional integer vectors equipped with various metrics or have bounded doubling dimension. We also consider linear sketches of DTW, showing that such sketches must have size Omega(n).
Publication Date: 2019
Citation: Braverman, Vladimir, Moses Charikar, William Kuszmaul, David P. Woodruff, and Lin F. Yang. "The One-Way Communication Complexity of Dynamic Time Warping Distance." In 35th International Symposium on Computational Geometry (SoCG), 129 (2019): 16:1-16:15. doi:10.4230/LIPIcs.SoCG.2019.16
DOI: 10.4230/LIPIcs.SoCG.2019.16
ISSN: 1868-8969
Pages: 16:1 - 16:15
Type of Material: Conference Article
Series/Report no.: Leibniz International Proceedings in Informatics (LIPIcs);
Journal/Proceeding Title: 35th International Symposium on Computational Geometry (SoCG)
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.