I'd say having spelling agnostic search would be crucial. I searched yesterday on google play music for an artist I'd heard of that sounded something like "n do

I'd say having spelling agnostic search would be crucial. I searched yesterday on google play music for an artist I'd heard of that sounded something like "n door" so I typed that and he came up as the top hit... "Youssou N'Dour". For this ferret search engine all I get is "Nas".