文章基本信息

标题：The One-Way Communication Complexity of Dynamic Time Warping Distance
本地全文：下载
作者：Vladimir Braverman ; Moses Charikar ; William Kuszmaul 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-15
DOI：10.4230/LIPIcs.SoCG.2019.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：dynamic time warping; one-way communication complexity; tree metrics