1. A computer-implemented method for adding reference fingerprints to a database to balance the search loads on the database by a media identification system, the method comprising: maintaining a reference database comprising a plurality of partitions, each partition storing a set of reference fingerprints generated from known media samples; monitoring access rates of the partitions by a media identification system; receiving a request to store one or more new reference fingerprints in the reference database; selecting a partition of the reference database based at least in part on the access rates of the partitions; and storing the new reference fingerprints in the selected partition of the reference database.