Gates told a media briefing in Sydney the company had "several milestones with its search site" on the way.
"In July, the format of the site will change -- and so will the quality of what you get -- and the way it'll look is dramatically improved," Gates said.
"It'll be later this year that we actually roll out what's entirely our own back end driving the search".
Gates said the way search was currently done was "very low-tech," based around taking "a bunch of words and making an index.
"You're not actually understanding the documents and so some of the false hits you get are almost humourous," he told journalists. "A human would not make those mistakes because a human can understand the document".
Gates said Microsoft had been doing linguistic research for more than a decade "that actually lets us parse and understand documents.
"That's where you can bring in the idea, don't show this person a restaurant if it's not nearby [or] don't show this person something about ... potato chips if they mean computer chips.
Gates said search moving forward encompassed personalisation, understanding local information, being able to parse in to the semantics of a document, being able to browse databases and being able to attach domain knowledge.
"Say if I want to know if a flight is on time.
"Generic Web search today is actually terrible for that, but we should be able to look at your query and say hey, that's a flight number and give a response that's basically just a direct answer to the question, not a list of random Web sites".
He described Google and Microsoft as being "fairly unique" in the way they both hired a lot of computer science Phds. "So the rate of improvement between us and them will be highly beneficial to the consumer as we compete".
