MOUNTAIN VIEW, Calif.—Finding the shortest distance between two points sounds easy enough, but computing that route takes too long and consumes too much computer memory.
Researchers at Microsoft Corp. are tackling the problem so that, in the next few years, computers can map the fastest route as well as make fast adjustments for road work or traffic jams, said Michael Schroeder, assistant director of Microsoft Researchs Silicon Valley lab here.
It comes down to developing a better mapping algorithm, one efficient enough to do massive computations in the palm of someones hand.
“It may be possible to put in a PDA and use for real-time reports of road outages,” Schroeder said.
Microsoft Researchs quest to find the shortest path was one of 10 projects on display here on Wednesday during an open house of one of its five research labs. Among the other projects demonstrated were ones focused on ridding Web search of spam, automatically creating summaries of news stories and blocking Internet worms.
While research projects are developed outside of Microsofts product development, the end results ultimately can make their way into features for everyday users, said Dan Ling, corporate vice president of Microsoft Research.
“Its important for us to take some of research we work on and have it benefit the 100s of millions of Microsoft customers around world,” Ling said. “At this point, every single Microsoft product has been touched by Microsoft Research.”
Ling and other researchers were careful to point out that nothing on display was specifically slated for a product, but the possible connections between some of the projects and Microsofts product plans were apparent.
Take for example a project aimed at battling the rise of Web page spam, where sites use methods such as machine generation of pages and links to mislead search engines. It could directly impact popular Web search engines, such as Microsofts MSN Search, said researcher Marc Najork said.
“Any search engine could and should apply this,” Najork said.
Microsoft has said it plans as early as the end of this year to launch its own algorithmic search engine for MSN Search. MSN today is using search results from Yahoo Inc.s engine.
The Web page spam research is based on two different crawls of the Web conducted almost two years ago, Najork said. Using the results from the crawl of 150 million Web pages conducted over the course of 11 weeks, researchers found that 8.1 percent of the pages were spam and that various statistical techniques could identify about 75 percent of those spam pages.
The statistical techniques look for such anomalies as a high number of host names being associated with the same IP address, a large number of characters or words being used in a host name, and an unusual distribution of links.
The Microsoft Research team plans to present its findings in a paper called “Spam, Damn Spam, and Statistics” during a Paris workshop next week. Next up is analyzing Web page content and words to weed out spamlike patterns, Najork said.
Researchers also are working to use natural language processing to automatically write summaries of news stories and items in a newsbot application. The ability for a computer to generate a summary could be important as more search sites attempt to crawl and sort news sources. MSN, for instance, is planning to launch a new news search service later this year.
To thwart Internet worms, researchers are proposing a line of defense in the network stack that could prevent the spread of worms even before software patches are available or deployed. Called Shield, the project uses network filters to monitor the incoming and outgoing traffic of vulnerable applications in order to stop traffic using an exploit.