Example systems and methods are audio identification based on data structure are disclosed. An example apparatus includes memory, and one or more processors to execute instructions to execute a constant Q transform on query time slices of query audio, binarize the constant Q transformed query time slices, execute a two-dimensional Fourier transform on query time windows within the binarized and constant Q transformed query time slices to generate two-dimensional Fourier transforms of the query time windows, sequentially order the two-dimensional Fourier transforms in a query data structure, and identify the query audio as a cover rendition of reference audio based on a comparison between the query data structure and a reference data structure associated with the reference audio.