eduzhai > Applied Sciences > Engineering >

Exact Parallelizable Dynamic Time Warping Alignment with Linear Memory

  • king
  • (0) Download
  • 20210507
  • Save

... pages left unread,continue reading

Document pages: 12 pages

Abstract: Audio alignment is a fundamental preprocessing step in many MIR pipelines.For two audio clips with M and N frames, respectively, the most popularapproach, dynamic time warping (DTW), has O(MN) requirements in both memory andcomputation, which is prohibitive for frame-level alignments at reasonablerates. To address this, a variety of memory efficient algorithms exist toapproximate the optimal alignment under the DTW cost. To our knowledge,however, no exact algorithms exist that are guaranteed to break the quadraticmemory barrier. In this work, we present a divide and conquer algorithm thatcomputes the exact globally optimal DTW alignment using O(M+N) memory. Itsruntime is still O(MN), trading off memory for a 2x increase in computation.However, the algorithm can be parallelized up to a factor of min(M, N) with thesame memory constraints, so it can still run more efficiently than the textbookversion with an adequate GPU. We use our algorithm to compute exact alignmentson a collection of orchestral music, which we use as ground truth to benchmarkthe alignment accuracy of several popular approximate alignment schemes atscales that were not previously possible.

Please select stars to rate!

         

0 comments Sign in to leave a comment.

    Data loading, please wait...
×