Disclosed example methods to determine a time offset between a first media signature having a first sequence of first data pairs and a second media signature having a second sequence of second data pairs include comparing ones of the first data pairs in the first sequence with ones of the second data pairs in the second sequence to determine original time differences between respective combinations of the ones of the first data pairs and the ones of the second data pairs. Such example methods also include scaling and truncating the original time differences to determine scaled time differences between respective combinations of the ones of the first data pairs and the ones of the second data pairs. Such example methods further include determining a histogram comprising bins representative of the scaled time differences, and selecting a histogram bin to correspond to the time offset between the first and second signatures.