Alex Zaharov-Reutt
Sunday, 25 May 2008 14:05
Opinion and Analysis
Page 2 of 3
Microsoft Research senior vice president, Roy Levin, “examined a handful of projects selected to provide a glimpse into the depth and the breadth of what the lab has to offer”, explaining that: “We don’t divide researchers into any particular formalized subgroups, and that works out extremely well, producing results that wouldn’t happen if you focused your research within individual groups.”
Six focus areas for the labs include: Algorithms and Theory, Distributed Systems, Security and Privacy, Software Tools, System Architecture and Web Search and Data Mining.
The full details of Microsoft’s Research Lab learnings for the Road Show can be found at Microsoft’s Labs
website.
One highlight was the “Shortest Path Algorithms project, which already has provided technology for Microsoft’s MapPoint products, provides results 10,000 times faster than the traditional approach. This is achieved by the use of “landmarks,” points on the periphery of the graph, and preprocessing techniques.”
Levin said “We do a lot of precomputing to figure out distances between the source destination and these landmarks, and then exploit that pre-computation to make the individual searches very fast, and it’s done in a way that can be implemented on a server or on a desktop or on a portable device, so that this becomes a real-time computation, which might be important to you as you’re driving down the freeway and you discover that the traffic is bad and you want to find an alternate route right now.”
Another interesting topic is the lab’s “burgeoning work on Electronic Market Design, which addresses marketplace competition, such as ad auctions for sponsored search, though online examples proliferate.”
Doubly relevant search and query-dependent ranking is yet another to “improve relevance in Web queries” as it is a “critical element in search”.
Levin explain: “This is obviously a very important thing. You go to a search engine, you type in a bunch of words, you get back a bunch of query results, and you’d very much like to have those ordered by relevance so that the ones at the top are the ones that are most important or interesting to you.”
“There have been various algorithms designed where you take the query results and rank them based on some relationship of the pages that came back from the search engine and their relationship on the Web graph,” Levin added. “But actually implementing these things at scale and understanding how well they do better is fairly hard.”
The Query-Dependent Ranking project implements a specialized infrastructure to analyze a variety of such algorithms at scale, making it efficient to measure and to analyze algorithmic performance to see which ones work best.
In recent tests, this infrastructure has indicated that some search algorithms can double relevance performance.
“This is a huge improvement,” Levin said.”People rejoice for a few percent in this area. Something that actually doubles the relevance is extremely attractive, and what that tells us is that Query-Dependent Ranking really does work. Now you can afford to invest in building infrastructure that will support that on a production scale.”
What about privacy, something we’re usually suspicious about with Microsoft? Please read on to page 3.
