Time complexity evaluation of cover song identification algorithms. (April 2021)

• Record Type: Journal Article
• Authors: Ferreira, Martha Dais; de Mello, Rodrigo Fernandes
• Is Part Of: Applied acoustics. Volume 175(2021)
• Publication Date: 2021-04
• Subjects: Cover song identification -- Time complexity -- MIREX -- Music information retrieval -- Algorithms; Acoustical engineering -- Periodicals; Periodicals; 620.2
• DOI: 10.1016/j.apacoust.2020.107777
• Languages: English
• ISSNs: 0003-682X

Abstract

Highlights: A time complexity evaluation of two popular frameworks for cover song identification. A brief explanation of the comparison method used by both frameworks. The asymptotic complexity is defined for both frameworks. Abstract: Cover Song Identification (CSI) is a task in Music Information Retrieval (MIR) that attempts to identify other versions of a song containing different structures, tonalities, and tempos, what brings several challenges to this task. Some of frameworks proposed to identify cover songs were evaluated through the Music Information Retrieval Evaluation eXchange (MIREX) competition that aims to assess algorithms for MIR tasks. Among the problems faced by researchers is the time complexity of the algorithms considered in the context of CSI, what limits or makes unfeasible their application in real-world scenarios. Considering this challenge, we present a time complexity evaluation of the two most popular frameworks presented and ranked at the MIREX competition. This assessment confirms both algorithms have the same worst-case scenario of O ( n 2 ), besides a significant difference in terms of their constants, which impact in overall processing time. Finally, this analysis can support researchers to improve algorithms for the CSI task, thus leading to more suitable frameworks for real-world scenarios.