Systems able to find a song based on a sung, hummed, or whistled melody are called Query-By-Humming (QBH) systems. Hummed or sung queries are not directly compared to original recordings. Instead, systems employ search keys that are more similar to a cappella singing than the original pieces. Successful, deployed systems use human computation to create search keys: hand-entered midi melodies or recordings of a cappella singing. There are a number of human computation-based approaches that may be used to build a database of QBH search keys, but it is not clear what the best choice is based on cost, computation time, and search performance. In this paper we compare search keys built through human computation using two populations: paid local singers and Amazon Mechanical Turk workers. We evaluate them on quality, cost, computation time, and search performance.