1. A method for providing natural language query translation, the method comprising: training a statistical machine translation model according to a plurality of mined query pairs, wherein training the statistical machine translation model comprises: identifying a set of previously received keyword type queries that are semantically similar to a set of previously received natural language type queries utilizing a query click graph, pairing at least one keyword type query with a natural language type query that is most semantically similar to form the mined query pairs; receiving a new natural language type query; mapping the new natural language type query into a new keyword-based type query according to the trained statistical machine translation model; performing a search query according to the new keyword-based type query; and providing at least one result from the search query.