I think I haven't really completely exhausted the possibilities of the algorithm yet. Consider, for example, these two queries for "Eine kleine Nachtmusik":
http://www.melodyhound.com/search.0.html?sourceid=melody-url&tx_mpsearch_pi1%5bsubmit_button%5d=Search&tx_mpsearch_pi1%5bpc%5d=hum%200.651-0-1/1.332-0-1/1.533-0-1/2.143-0-1/2.354-0-1/2.554-0-1/2.764-0-1/2.955-0-1/3.175-0-1/4.026-0-1/4.707-0-1/4.907-0-1&categories=CPHA&filtertext=&coll=r
and
http://www.melodyhound.com/search.0.html?sourceid=melody-url&tx_mpsearch_pi1%5bsubmit_button%5d=Search&tx_mpsearch_pi1%5bpc%5d=hum%200.671-0-1/1.362-0-1/1.552-0-1/2.163-0-1/2.383-0-1/2.573-0-1/2.774-0-1/2.954-0-1/3.164-0-1/4.026-0-1/4.717-0-1/4.917-0-1/5.538-0-1/5.748-0-1/5.938-0-1/6.139-0-1/6.319-0-1/6.549-0-1&categories=CPHA&filtertext=&coll=r
With the algorithm in its current shape, the second, longer one shows the Nachtmusik already on page one instead of page two like the first one, as one should expect if you add more notes and therefore make it more clear what you want. But I still see some matches ranked higher that should not be there, so I need to do some more debugging and see what goes wrong there.
Of course, even more tweaking still won't change the fact that using pitch and rhythm at the same time means that far fewer notes are necessary for getting far better results, e. g.:
http://www.melodyhound.com/search.0.html?sourceid=melody-url&tx_mpsearch_pi1%5bsubmit_button%5d=Search&tx_mpsearch_pi1%5bpc%5d=lily+g'4.+d'8+g'4.+d'4+g'8+d'8+g'8+b'8&categories=CPHA&filtertext=&coll=m
So there'll probably always be a tradeoff between the minimum skills needed for formulating the query and the result quality you can get.