Methods, apparatus, systems, and articles of manufacture are disclosed to improve media identification. An example apparatus includes a hash handler to generate a first set of reference matches by performing hash functions on a subset of media data associated with media to generate hashed media data based on a first bucket size, a candidate determiner to identify a second set of reference matches that include ones of the first set, the second set including ones having first quantities of hits that did not satisfy a threshold, determine second quantities of hits for ones of the second set by matching ones to the hash tables based on a second bucket size, and identify one or more candidate matches based on at least one of (1) ones of the first set or (2) ones of the second set, and a report generator to generate a report including a media identification.