The One-Way Communication Complexity of Dynamic Time Warping Distance

Authors Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.16.pdf
  • Filesize: 473 kB
  • 15 pages

Document Identifiers

Author Details

Vladimir Braverman
  • Johns Hopkins University, Baltimore MD, USA
Moses Charikar
  • Stanford University, Stanford CA, USA
William Kuszmaul
  • Massachusetts Institute of Technology, Cambridge MA, USA
David P. Woodruff
  • Carnegie Mellon University, Pittsburgh PA, USA
Lin F. Yang
  • Princeton University, Princeton NJ, USA

Acknowledgements

David P. Woodruff would like to thank the Simons Institute for the Theory of Computing where part of this work was done.

Cite AsGet BibTex

Vladimir Braverman, 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 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.16

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • dynamic time warping
  • one-way communication complexity
  • tree metrics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. John Aach and George M Church. Aligning gene expression time series with time warping algorithms. Bioinformatics, 17(6):495-508, 2001. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 59-78. IEEE, 2015. Google Scholar
  3. Pankaj K Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating dynamic time warping and edit distance for a pair of point sequences. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.01876.
  4. Ghazi Al-Naymat, Sanjay Chawla, and Javid Taheri. Sparsedtw: A novel approach to speed up dynamic time warping. In Proceedings of the Eighth Australasian Data Mining Conference-Volume 101, pages 117-127. Australian Computer Society, Inc., 2009. Google Scholar
  5. Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff. Efficient sketches for earth-mover distance, with applications. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 324-330. IEEE, 2009. Google Scholar
  6. Nurjahan Begum, Liudmila Ulanova, Jun Wang, and Eamonn J. Keogh. Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 49-58, 2015. Google Scholar
  7. D. Belazzougui and Q. Zhang. Edit Distance: Sketching, Streaming and Document Exchange. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1607.04200.
  8. Djamal Belazzougui. Efficient deterministic single round document exchange for edit distance. arXiv preprint, 2015. URL: http://arxiv.org/abs/1511.09229.
  9. Donald J. Berndt and James Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. In Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, July 1994. Technical Report WS-94-03, pages 359-370, 1994. Google Scholar
  10. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 79-97. IEEE, 2015. Google Scholar
  11. EG Caiani, A Porta, G Baselli, M Turiel, S Muzzupappa, F Pieruzzi, C Crema, A Malliani, and S Cerutti. Warped-average template technique to track on a cycle-by-cycle basis the cardiac filling phases on left ventricular volume. In Computers in Cardiology 1998, pages 73-76. IEEE, 1998. Google Scholar
  12. Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouckỳ. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 712-725. ACM, 2016. Google Scholar
  13. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a finite metric by a small number of tree metrics. In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 379-388. IEEE, 1998. Google Scholar
  14. Alexander De Luca, Alina Hang, Frederik Brudy, Christian Lindner, and Heinrich Hussmann. Touch me once and i know it’s you!: implicit authentication based on touch screen patterns. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 987-996. ACM, 2012. Google Scholar
  15. Anne Driemel and Francesco Silvestri. Locality-Sensitive Hashing of Curves. In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, pages 37:1-37:16, 2017. Google Scholar
  16. Ioannis Z Emiris and Ioannis Psarros. Products of Euclidean metrics and applications to proximity questions among curves. arXiv preprint, 2017. URL: http://arxiv.org/abs/1712.06471.
  17. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004. Google Scholar
  18. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. arXiv preprint, 2016. URL: http://arxiv.org/abs/1607.05994.
  19. Daniel S. Hirschberg. A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM, 18(6):341-343, 1975. Google Scholar
  20. Utku Irmak, Svilen Mihaylov, and Torsten Suel. Improved single-round protocols for remote file synchronization. In INFOCOM, pages 1665-1676, 2005. Google Scholar
  21. Utku Irmak, Svilen Mihaylov, and Torsten Suel. Improved single-round protocols for remote file synchronization. Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., 3:1665-1676 vol. 3, 2005. Google Scholar
  22. Thathachar S Jayram and David P Woodruff. Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. ACM Transactions on Algorithms (TALG), 9(3):26, 2013. Google Scholar
  23. Hossein Jowhari. Efficient communication protocols for deciding edit distance. In European Symposium on Algorithms, pages 648-658. Springer, 2012. Google Scholar
  24. Eamonn J. Keogh. Exact Indexing of Dynamic Time Warping. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong, China, pages 406-417, 2002. Google Scholar
  25. Eamonn J. Keogh and Michael J. Pazzani. Scaling up Dynamic Time Warping to Massive Dataset. In Principles of Data Mining and Knowledge Discovery, Third European Conference, PKDD '99, Prague, Czech Republic, September 15-18, 1999, Proceedings, pages 1-11, 1999. Google Scholar
  26. Eamonn J. Keogh and Michael J. Pazzani. Scaling up dynamic time warping for datamining applications. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, Boston, MA, USA, August 20-23, 2000, pages 285-289, 2000. Google Scholar
  27. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 596-605. ACM, 1995. Google Scholar
  28. Lindasalwa Muda, Mumtaj Begam, and Irraivan Elamvazuthi. Voice recognition algorithms using mel frequency cepstral coefficient (MFCC) and dynamic time warping (DTW) techniques. arXiv preprint, 2010. URL: http://arxiv.org/abs/1003.4083.
  29. Mario E Munich and Pietro Perona. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, volume 1, pages 108-115. IEEE, 1999. Google Scholar
  30. Assaf Naor. Probabilistic clustering of high dimensional norms. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 690-709. SIAM, 2017. Google Scholar
  31. Ofer Neiman. On Stochastic Decompositions of Metric Spaces. Google Scholar
  32. Alon Orlitsky. Interactive communication: Balanced distributions, correlated files, and average-case complexity. In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 228-238. IEEE, 1991. Google Scholar
  33. François Petitjean, Germain Forestier, Geoffrey I. Webb, Ann E. Nicholson, Yanping Chen, and Eamonn J. Keogh. Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm. Knowl. Inf. Syst., 47(1):1-26, 2016. Google Scholar
  34. Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing, 26(1):43-49, 1978. Google Scholar
  35. Yasushi Sakurai, Masatoshi Yoshikawa, and Christos Faloutsos. FTW: fast similarity search under the time warping distance. In Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA, pages 326-337, 2005. Google Scholar
  36. Braverman Vladimir, Moses Charikar, William Kuszmaul, David P. Woodruff, and Liu F. Yang. The One-Way Communication Complexity of Dynamic time Warping Distance. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.03520.
  37. Rex Ying, Jiangwei Pan, Kyle Fox, and Pankaj K Agarwal. A simple efficient approximation algorithm for dynamic time warping. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 21. ACM, 2016. Google Scholar
  38. Yunyue Zhu and Dennis Shasha. Warping indexes with envelope transforms for query by humming. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 181-192. ACM, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail