We describe a new method for query completion for Bollywood song search without using query logs. Since song titles in non-English languages (Hindi in our case) are mostly present as Roman transliterations of the native script, both the queries and documents have a large number of valid variations. We address this problem by using a Roman to Hindi transliteration engine coupled with appropriate ranking and implementation strategies. Out of 100 test cases, our system could generate the correct suggestion for 91 queries.