Do startups like Bop.fm, SoundWave, and Listn have their own proprietary matching algorithms that allow them to convert a YouTube link into an Rdio or Spotify link, or do they use a third party?
I don't know any specifics about how these companies do things, but this part of what they do doesn't seem like it'd be especially hard. The various music service APIs provide ways to search their libraries for a string so you could do a reasonable first stab that way. Youtube's API provides the metadata so as long as the video has accurate metadata you can search on that.
