TechFest 2008

About

Microsoft Research’s TechFest is an annual event that brings researchers from Microsoft’s labs around the world to Redmond to share their latest work with the product teams. Attendees experienced some of the freshest, most innovative technologies emerging from Microsoft’s research efforts. The event provided a forum in which product teams and researchers can discuss the incredible work occurring in the labs, thereby encouraging effective technology transfer into Microsoft products.

Keynote Speakers: Rick Rashid, senior vice president, Microsoft Research, and Craig Mundie, chief research and strategy officer, Microsoft.

Demos

Emerging Markets and Research Partners

Lingo: Vertical Search Engine for English Writing

English is the most commonly used language in the world, but non-native speakers have difficulty in writing fluent English. We will demo a vertical search engine for English as Second Language writing. We have built a search engine to help the users. A large volume of data―bilingual and monolingual sentences, for instance―is collected and indexed. With the help of sentence retrieval, users can get good example sentences in different domains and different styles. We also will show our technologies for using a paraphrasing engine and a machine-translation engine to extend users’ writing styles.

Bilingual Built-ins That Break Language Barriers

We will present exciting new applications of our translation technology, showing how machine translation, integrated into Microsoft’s products, can help eliminate barriers to worldwide communication and bring users of diverse cultures closer together. Our demo covers interesting user scenarios and presents viable solutions for making cross-language hurdles disappear.

Trident: A Workflow Workbench for Oceanography

Science is undergoing a sea change. Instead of the small, private, periodic data sets currently being used, large, sophisticated, remote-sensor systems soon will bring enormous amounts of real-time data to be shared by multidisciplinary scientists. One such example is Project Neptune for oceanography. To cope with this shift from data-poor to data-rich science, new tools are needed to help scientists work effectively with these systems and with the enormous amount of data that they will generate. Trident is a collaborative scientific and engineering partnership between the University of Washington, the Monterey Bay Aquarium, and Microsoft’s Technical Computing Initiative to provide Project Neptune with a scientific-workflow workbench for oceanography. The Trident workbench is built atop the Windows Workflow Foundation. Trident enables users to automate, explore, and visualize data; to compose, run, and catalog experiments; to create a workflow starter kit that makes it easy for users to extend the functionality of Trident; and to learn by exploring and visualizing ocean and model data. We will illustrate how Trident can be used to author workflows through a visual interface, store workflows in a library for easy reuse, and execute oceanographic workflows to create on-demand visualizations. Our booth will include posters that provide context for both the Neptune project and the Trident workflow workbench.

E-Science: Science in the Cloud

We’ve been working with a number of collaborators on a number of different, yet related, eco-science projects. Common to all of them is helping scientists cope with the landslide of data available today while preparing for tomorrow’s tsunami generated by ubiquitous sensors. For smaller sciences, the ability to tap data in the cloud is ever increasing. The data are more science-friendly: further from the instruments and closer to the science. We’ll demo http://www.hydroseek.org (used to find U.S. Geological Survey, U.S. Environmental Protection Agency, and other data), http://www.fluxdata.org (a SharePoint site used by the global carbon-climate community to access shared synthesis data), http://bwc.berkeley.edu/RussianRiver (a data cube used for hydrologic analysis of the Russian River in California), and other Internet science assets. We’ll also demo a UI used to plan sensor deployments, not the simplest thing for scientists to do! All of these have been developed in conjunction with research partners such as the University of California, Berkeley, the University of Virginia, the San Diego Supercomputer Center, the University of California, Santa Barbara, the University of Washington, and L’Ecole Parapente du Val Louron.

BEE3: Revitalizing Architecture Research

For the last couple of decades, architecture research has been moribund, because people doing it can’t build state-of-the art chips. FPGAs offer an alternative to this. We are helping a number of universities sidestep this problem.

Science for the 21st Century

Epidemics, bioengineering, climate change, species extinction, cancer―at least one is a major daily news headline. These are the defining challenges and opportunities for the 21st century. Addressing them requires major advances in understanding and integrating the natural sciences across a wide range of scales, from molecules, genes, and cells to whole organisms, ecosystems, and our entire biosphere. New kinds of tools in computing will prove critical to achieving this goal. Microsoft Research Cambridge’s computational-science groups are developing conceptual and technological tools to create, enable, and accelerate fundamental advances in these areas. We will present examples of this research:•Genes and networks: Visual Programming of Gene Networks and Biological Pathways.•Ecosystems: Autonomous Monitoring of Vulnerable Ecosystems.•Biosphere: Exploring and Analyzing Structures in Global Forest Dynamics; Visualizing, Modelling and Analyzing Complex Ecological Networks; and Regional Climate Modelling.

Additionally, we will demonstrate our DISCOVERY Toolkit concept―a new framework for hosting and running such models―and two demos from our joint research labs.

Hardware, Devices, and Mobile Computing

Lucid Touch

Touch is a compelling input modality for interactive devices, but touch input on the small screen of a mobile device is problematic because a user’s fingers occlude the desired graphical elements. LucidTouch is a mobile-device interface that addresses this limitation by enabling a user to control an application by touching the back of the device. The key to making this usable is what we call pseudo-transparency: By overlaying an image of the user’s hands onto the screen, we create an illusion of the mobile device itself being semitransparent. This pseudo-transparency enables users to acquire targets accurately while not occluding the screen with their fingers and hand. LucidTouch also supports multitouch input, giving users an ability to operate the device simultaneously with all 10 fingers. We will present initial study results that indicate that many users found touching on the back preferable to touching on the front, because of reduced occlusion, higher precision, and an ability to make multifinger input.

Search, Interaction, and Collaboration

GeoLife: Search Your Life over Maps

GeoLife is a GPS-log-driven application over Web maps. It focuses on visualization, organization, fast retrieval, and effective understanding of GPS track logs for both personal and public use. Given a GPS track log and associated multimedia data people have created, GeoLife helps users visualize their personal events on Web maps and understand their life patterns. By publishing their GPS tracks, users can share their life experiences with others and absorb rich knowledge from others’ GPS tracks. Based on the public data, more knowledge, such as popular travel routes, popular places, and traffic conditions, could be mined. Further, a spatial-temporal search function, which enables a user to give a spatial range over maps and/or temporal intervals as a query, is offered in GeoLife to help people learn effectively about the GPS tracks that interest them. The search function not only facilitates people’s ability to get information efficiently from other people’s life experiences, but also supports each person’s recall of events. Search maps to reflect on your past life, and search maps to plan your future life.

Query-Specific Portals for Search

We have developed a strategy that leverages entities present in Web documents, such as people, locations, or products, to enrich users’ search experiences. While preserving the simple, keyword-based search paradigm, we enhance the results to include ”super-pages” that display a ranked list of relevant entities. We exploit existing structured data to return additional information about the retrieved entities, such as categories and attributes. The combination of search results and structured data creates a portal-like display of the search results, which the user can refine further. Our strategy uses a mix of online and offline techniques to provide efficient functionality for large data sets. We will present a search interface that showcases our entity-extraction and -categorization techniques in the context of people entities in live.com search.

New Search UIs for Collaboration and Persistence

We will demo three search UIs offering new experiences in persistence and collaboration: SearchBar, SearchTogether, and CoSearch. Today’s UIs treat search as a transient activity, but people often conduct complex, multi-query investigations that span long durations and that are interrupted by other tasks. SearchBar is a new type of browser history that supports complex Web investigations by assisting with task resumption and information re-finding. SearchBar accomplishes these goals by proactively and persistently storing query histories, browsing histories, notes, and ratings in an interrelated fashion. Current UIs also treat search as a solitary experience, but users often need to collaborate on searches, such as students working together on homework or families jointly planning a vacation. SearchTogether enables groups of remote users to collaborate on Web search, synchronously or asynchronously, by providing group query histories, shared comments and ratings, automatic distribution of search results, session summaries, and integrated chat. CoSearch enables groups of collocated users to collaborate when sharing a single PC, as often occurs in schools and libraries, by enabling group members to use their phones as input devices: Users can send text messages to the computer to queue up query terms and can use their phones’ joysticks to operate cursors on the PC to queue up browser tabs for group viewing. Relevant products: IE, Live, Messenger, Communicator.

BLEWS: What the Blogosphere Tells You About News

While typical news-aggregation sites do a good job of clustering news stories according to topic, they leave the reader without information about which stories figure prominently in political discourse. BLEWS uses political blogs to categorize news stories according to their reception in the conservative and liberal blogospheres. It visualizes information about which stories are linked to from conservative and liberal blogs, and it indicates the level of emotional charge in the discussion of the news story or topic at hand in both political camps. BLEWS also offers a “see the view from the other side” functionality, enabling a reader to compare different views on the same story from different sides of the political spectrum. BLEWS achieves this goal by digesting and analyzing a real-time feed of political-blog posts provided by the Live Labs Social Media platform, adding both link analysis and text analysis of the blog posts.

Salsa: Social Networking for Business

Salsa is a business-oriented social-networking system integrated into the user’s Outlook client. E-mail is the core of online communication for most business users. Our goal is to create an active, fun, and productive social network at Microsoft, eventually extending it to external audiences such as alumni, former interns, and partners—and to other companies. Enterprise-oriented social networking typically suffers from a lack of critical mass, because of the ”closed” nature of the network and because new communication tools require learning in an environment already overloaded with information. Salsa serves as a bridge to many existing social networks, aggregating and displaying information from a variety of sources—such as SharePoint, Facebook, Twitter, Windows Live Messenger, and Office Communicator—and provides contextual awareness of people you care about.

C2: Social Networking for the Client

Web 2.0 and social networks give us new models for sharing, aggregating, and discovering new people and content. Facebook makes us think of applications and viral content in new ways. What if the Web could reach into the desktop and change it? What would we need to do to the desktop with regard to aggregation, organization, privacy, and sharing? C2 lets users access data from across different sources, managing private and public information. The project features three parts: aggregation, with a sharing privacy model; user experience; and a unified model for traditional and emerging communication tools, such as e-mail, social networks, and instant messaging.

Software, Theory, and Security

Probability and Networks

Early models for the formation of self-organized networks, such as the Internet and the World Wide Web, were based on preferential attachment: A new site is likely to link to existing sites that are already popular. We analyze refined variants of preferential attachment that incorporate prior fitness and competition effects. We also study geometric representations of disordered networks, where some edges can become faulty. Finally, we consider matching with random inputs: Imagine a collection of servers and clients, located randomly in the plane, that need to pair up. Different pairing schemes produce markedly different results; we will compare globally optimal matching with stable matching, in which individual agents are autonomous.

Algorithms and E-Commerce

We will consider fundamental problems in combinatorial optimization with applications in search and e-commerce, such as the “traveling salesman” problem, satisfiability, and clustering. These are known to be hard in the worst case and extremely time-consuming to solve in practice, even when involving only a few hundred variables. We analyze new algorithms, inspired by statistical physics and information theory, that, in practice, succeed in typical instances with hundreds of thousands of variables. We also will present an innovative approach to page-ranking and Web-spam detection, and a hands-on demonstration of the gap between greedy and global optimization.

Privacy Integrated Queries

The Language Integrated Query (LINQ) framework enables tuple-oriented, unified data access to a large class of data stores; examples include standard C# enumerable, SQL back ends, and even Dryad-backed compute clusters. The tuple-oriented nature of LINQ lends itself easily to several recent privacy technologies aimed at preserving the privacy of any tuple in the input; no one should be able to observe the presence or absence of any specific tuple. With a bit of randomization, scaled to match the maximum influence of any one tuple, privacy can be preserved formally for many LINQ queries. We will present a simple checker that audits queries submitted through LINQ’s IQueryable interface, assesses the impact of tuples, and proposes or applies randomization to ensure privacy.

Privacy in Personalized Search and Shared Sensing

We will present a pair of ways to provide shared data while maintaining users’ privacy preferences. One explores the rich space of possibility where people doing search can opt to share, in an ongoing or real-time manner, personal information in return for expected enhancements in the quality of an online service. We have analyzed a year of toolbar data and, in conjunction, performed a user study with 1,400 participants. We will show that a significant level of personalization can be achieved using only a small amount of information about users. The other provides a mechanism to enable data from privately held sensors, such as GPS systems, to be shared and aggregated within the constraints of privacy preferences of the sensors’ owners. We will show how the methods work on real-world data.

Systems, Networking, and Databases

Better Bug Reporting with Better Privacy

Software vendors collect bug reports from customers to improve the quality of software. These reports should include the inputs that make the software fail, to enable vendors to reproduce the bug. But vendors rarely include these inputs in reports because they might contain private user data. We describe a solution to this problem that provides software vendors with new input values that satisfy the conditions required to make the software follow the same execution path until it fails but are otherwise unrelated with the original inputs. These new inputs enable vendors to reproduce the bug while revealing less private information than existing approaches. Additionally, we provide a mechanism to measure the amount of information revealed in an error report. This mechanism enables users to make informed decisions about whether to submit reports. We have implemented a prototype of our solution and have evaluated it with real errors in real programs. The results show that we can produce error reports that enable software vendors to reproduce bugs while revealing almost no private information. We will show how we generate a bug report for a document that crashes Word. The bug report includes a new document that crashes Word in the exact same way yet contains virtually none of the textual content of the original document.

MashupOS for Web Browsers

The advent of AJAX and client mashups has turned Web browsers into a multiprincipal operating environment. But browser support for Web programmers has lagged behind and remained in a single-principal world: The Same Origin Policy that dictates today’s browser-security model offers either no trust through complete isolation between principals (sites) or full trust by incorporating third-party code as libraries. The consequences of such limited support include cross-site-scripting attacks that seriously plague today’s Web and undesirable programming practices that make tradeoffs between security and functionality. In the MashupOS project, we address this deficiency. Our goal is to enable a browser to be a multiprincipal OS. Our initial focus is on protection and communication abstractions. Protection is to provide default isolation boundaries among principals (sites), while communication enables custom, fine-grained access control. We have designed our abstractions to be backward-compatible and easily adoptable. We have built a MashupOS prototype that we will demonstrate. Our experience and evaluation show that our abstractions make it easy to build more secure and robust client-side Web mashups and can be implemented easily in browsers with negligible performance overhead.

Reliable Wireless Connectivity on the Go

Many people want to stay connected while traveling and commuting, which is driving the demand for network access from moving vehicles. But the reliability and performance of such connectivity today is severely limited by frequent “blackouts” that the vehicle-to-infrastructure backhaul links suffer. We have designed a system that, unlike existing “commuter networks,” such as Sound Transit or the Microsoft Connector system, uses multiple backhaul links for added reliability and performance. Our system fuses these links together using novel striping mechanisms that intelligently decide which link individual packets must use, based on current performance and load. We have instantiated our design in the context of providing CorpNet access on Microsoft shuttles and the Connector service. Unlike the current Wi-Fi service on the Connector, our system does not require users to log in via the RAS service to access internal sites. To them, it appears as if they are directly attached to the corporate wireless network, just as they would be from their offices. We have partnered with the Microsoft shuttle service to demonstrate our system on the shuttles that will ferry TechFest attendees.

Rethinking Spectrum Allocation in Wi-Fi Networks

IEEE 802.11 divides the frequency spectrum into channels of fixed width. For example, 802.11bg divides 80 MHz of the 2.4-GHz spectrum into 11 channels, each of 20MHz width, three of which are non-overlapping. Over the past six months, we have been exploring the feasibility and the benefits of varying the channel width. In our demo, we will show that changing the channel width is achievable even with current hardware and beneficial in a number of scenarios. For example, contrary to popular belief that increasing communication range requires an increase in battery-power consumption, we will show that reducing channel width increases communication range while actually reducing battery-power consumption. We will explore the design challenges in a Zune-like system and show that such systems can benefit from adapting channel widths. We also will discuss various challenges and present a solution that performs better than any non-adaptive channelization scheme.

SixthSense: RFID-Based Enterprise Intelligence

SixthSense is an RFID-based enterprise-intelligence system. We consider an enterprise environment where people and their personal objects are tagged with cheap, passive RFID tags and there is good coverage of RFID readers in the workspace. SixthSense is an integrated system that combines information from RFID-based sensing with data from other sensors, such as cameras and Wi-Fi, as well as enterprise systems, such as calendar and presence, to draw inferences about people, objects, and their association and interaction. We are building several applications atop this substrate, including a lost-object finder, video-event tagging, and enhanced calendar and presence, while safeguarding user privacy. We will demo the SixthSense system and some of these applications.

Mobile-Systems Distributed Operation for Sensing

While mobile phones quickly are becoming the primary computing platform for many users, these devices are programmed and used in a manner akin to miniature PCs, each in a silo and interacting primarily with the cloud. We will propose a distributed software platform to break out of this mold and enable capabilities and applications that take advantage of the computing, communication, and sensing capabilities of an ensemble of mobiles, whether in proximity or across a wide area. For instance, a traffic-monitoring application could have a set of mobile nodes in particular locations gather data from their GPS, accelerometer, and microphone sensors, perform custom processing of the sensed data in their local neighborhood to detect unusual traffic conditions, and report the processed data back to a server for aggregation and reporting. Our technology consists of a trusted core that includes services such as localization, communication, and accounting, and a software sandbox for securely executing untrusted application code that builds on these services. We will demo the system in operation and show a couple of applications that illustrate its capabilities: rich traffic monitoring and an on-demand Webcam.

HomeMaestro: Order from Chaos in Home Networks

Home networks constantly are increasing in complexity: Multiple devices, such as desktops, laptops, IP phones, and game consoles, running applications such as e-mail, Web access, peer-to-peer, voice-over IP, video streaming, online gaming, media sharing, and telecommuting, are expected to be part of the next generation of the home ecosystem. Such applications are characterized by different performance goals, and they fight for the same network resources, such as the broadband-access link and the in-home wireless medium. Moreover, home users have different, often conflicting, performance objectives and priorities; for example, a file-sharing application of one home user can degrade the performance of the voice communication of another. HomeMaestro aims to provide a distributed system for monitoring and instrumentation of home networks. HomeMaestro performs extensive measurements at the host level to infer application types and network requirements, and to identify significant changes in application behavior, such as problems stemming from limited available capacity of the wireless link. By correlating metrics across devices, HomeMaestro can infer how applications affect each other and then use prioritization as a first stage of a distributed-control mechanism. HomeMaestro strives to put order into our home networks by identifying network problems and enabling users to prioritize application traffic. We will show the benefits of HomeMaestro in typical home scenarios.

Diagnosing Home-Networking Problems with NetPrints

Today’s home networks include a number of components―multiple desktops and laptops, wireless-access points, routers, printers, and modems. In such a setting, it is not uncommon for users to be stymied by configuration problems. Today, the debugging process for such problems is largely manual―trial and error, searching the Web, posting on mailing lists, calling tech support―with the consequent cost in time, money, and user frustration. NetPrints seeks to automate this debugging process by tapping into the ”shared wisdom” of participating clients. The client component of NetPrints periodically gathers network signatures of successful and unsuccessful application runs and reports these to the NetPrints server, along with configuration information, such as network-address-translation or firewall settings, gathered from the client host and the home router. The NetPrints server sorts through this mass of data to identify configuration settings associated with successful application runs, which are then used to identify misconfigurations when a new client reports a problem. We shall demonstrate the NetPrints system in action in the context of a few common configuration problems that arise in home networks to illustrate the power of this approach.

Tiny Web Services

We will demonstrate a low-power, low-cost Web-service implementation for devices that must run on batteries for several years, such as smoke detectors and window-break sensors. In particular, we will show a prototype system of WSDL/TCP/IP over a low data rate 802.15.4 radio used in home automation. The Web-service interface makes it easy for multiple programmers to develop home-control applications using devices manufactured by different OEMs without learning new programming technologies. Our system also provides a uniform setup experience for users, enabling them to integrate multiple home devices into a single network. We also will demonstrate how a home network can be connected safely to the Internet to be accessed from cloud services. We will present a feedback-based, multiradio scheduling algorithm for energy-efficient communication among battery-operated devices. Finally, we will demonstrate an energy-management application that saves energy by actively monitoring weather and energy price variations using cloud services without compromising user comfort. This example application can be used to connect the 166 million U.S. homes and several million more worldwide to the Microsoft cloud for providing energy management. This application can generate a steady revenue stream for Live services that does not depend on user clicks. It also reduces our carbon footprint and leads to a greener lifestyle.

Auto-Shift: Energy-Aware Server Positioning

With the explosive growth of Internet services, the energy consumed by computer servers and data centers is skyrocketing. Dynamic server provisioning can turn off unnecessary servers to save energy, but such techniques face challenges for connection-intensive servers that host lots of long-lived TCP connections, such as in Windows Live Messenger. Such servers limit the number of new connections they can accept per second, so they cannot be fully utilized immediately after being turned on. Turning off servers also might involve many migrations or reconnections. We have a systematic approach for joint analysis and design of dynamic server-provisioning and load-dispatching algorithms for connection-intensive servers, and we will show their effectiveness on Windows Live Messenger. Our techniques provide significant energy saving—as much as 30 percent—without sacrificing user experiences.

UI, Graphics, and Media

Adding Detail to Low-Dynamic-Range Images

We will introduce high-dynamic-range image hallucination for adding high-dynamic-range details to overexposed and underexposed regions of a low–dynamic-range image. Our method is based on a simple assumption: High-quality patches exist in the image with similar textures to the regions that are poorly exposed. Hence, we can add high-dynamic-range details to a region simply by transferring texture details from another patch that might be under different illumination levels. In our approach, a user needs only to annotate the image with a few strokes to indicate textures that can be applied to the corresponding poorly exposed regions, and these regions automatically are hallucinated by our algorithm. Experiments demonstrate that our simple, yet effective approach can significantly increase the amount of texture detail in a wide range of common scenarios with only a modest amount of user interaction.

Music Steering

By “music steering,” we mean interactive music-playlist generation through music-content analysis, music recommendation, and music filtering. With thousands of songs stored in our portable devices, such as smartphones and Zunes, selecting songs to hear has become a challenge. Music steering helps us explore and enjoy our personal song collection in a new way.

Multichannel Acoustic-Echo Cancellation

This demo presents newly developed technology for multichannel acoustic-echo cancellation, assisted with a microphone array. This technology enables removing the sound from multiple loudspeakers, such as stereo and surround sound, from the signal captured by the microphones. The potential scenarios are a voice-controlled Media Center and high-end communication systems.

In-Depth Image Editing

We propose new techniques for manipulating conventional photographs. Uninteresting images are populated with objects or people borrowed from other pictures to create a much more compelling composition. High-quality, automatic color balancing also will be demonstrated.

An HMM-Based Talking and Singing Head

This demo will show a trainable, audio-visual synthesis system. In the training and adaptation phase, audio and/or video features, along with the corresponding scripts—text, lyrics, and melodies—are used to drive a statistical, hidden Markov model (HMM)-based training procedure. The HMM thus trained can be adapted further with data from a specific speaker or singer to give it a new, personalized flavor. In the audio-visual synthesis phase, scripts of text, lyrics, and melody are inputted into a script-analysis module that generates a sequence of consecutive units. The parameters of the HMMs are retrieved, and final audio-visual data, speech, or singing with facial expressions and head movements are synthesized. The HMM-based talking and singing head is based on a 3-D model. The audio-visual models are parametric and statistically trained. They can capture a person’s characteristics. They are also easy to modify to meet a specific vocal requirement.

Video Collage

Video Collage is a compact representation of video. It uses one automatically synthesized image to summarize the content of a video. Video Collage selects the most representative frames from a video, extracts salient regions of interest (ROI) from these frames, and seamlessly arranges ROIs on a given canvas. Furthermore, Video Collage can be printed into booklets or albums. Users thus can browse those booklets or albums just as if they were browsing ordinary photo albums. When they want to watch a certain segment indicated by a thumbnail in the booklet, they can use a camera phone or a similar device to capture the corresponding thumbnail. Then the captured image is sent to a computer via a wireless network, automatically retrieved in a video library, and the corresponding video segment is presented to the user. Video Collage provides a novel user interface that enables users to browse video content in a more compact, visually appealing, and natural way, in contrast to many existing video browsers. Video Collage can be integrated easily into existing video-management systems, video-sharing sites, and video search engines to support an attractive video-browsing and -sharing experience.

Real-Time Soft Global Illumination

In previous TechFests, we demoed fast soft shadows on the GPU. We have made the technique simpler, faster, and more robust by accumulating the blocking effect of dynamic objects such as moving characters in image space instead of over mesh vertices. We also include indirect reflections, as well as shadowing. The result is realistic global illumination effects that can be rendered in real time and are practical for current 3-D games and visualization applications.

Real-Time Rendering of Smoke Animation

Rendering of smoke presents a challenging problem in computer graphics because of its complicated effects on light propagation. Within a smoke volume, light undergoes absorption and scattering interactions that vary from point to point because of the spatial non-uniformity of smoke. In static participating media, the number and the complexity of scattering interactions lead to a substantial expense in computation. For a dynamic medium such as smoke, the intricate volumetric structure of which changes with time, the computational costs can be prohibitive. Despite the practical difficulties of smoke rendering, it nevertheless remains a popular element in many applications, such as films and games. To achieve the desired visual effects of smoke, a designer should be afforded real-time control over the lighting environment and vantage point, as well as the volumetric distribution and optical properties of the smoke. We present a real-time algorithm for rendering of smoke under dynamic low-frequency environment lighting. Our algorithm can be implemented easily on a GPU, thus enabling real-time manipulation of viewpoint and lighting, as well as interactive editing of smoke attributes, such as extinction cross section, scattering albedo, and phase function. With only moderate preprocessing time and storage, this technique generates rendering results comparable to those from offline rendering algorithms such as ray tracing.

WorldWide Telescope

The WorldWide Telescope (WWT) is a rich visualization environment that functions as a virtual telescope, bringing together imagery from the best ground- and space-based telescopes in the worldto enableseamless, guided explorations of the universe. WorldWide Telescope, created with Microsoft’s high-performance Visual Experience Engine, enables seamless panning and zooming across the night sky blending terabytes of images, data, and stories from multiple sources over the Internet into a media-rich immersive experience.

Feature Stories

Translating the Web for the Entire World

By Rob Knies

windows_live_translator_73_73People all over the world use the Internet every day, to purchase goods or services, to search for information, to find diversions.

But is the World Wide Web truly worldwide?

It’s difficult to make the case. Estimates claim that approximately 70 percent of Web pages today are created in the English language, while the percentage of non-English speakers is growing faster than that of English speakers. So what if you don’t speak English? Or what if you do and you find an interesting page written in German? Or Russian? Or Chinese?

Microsoft Research aims to please.

Windows Live Translator, a free translation portal and a Web service that powers many other translation scenarios, is the result of more than eight years of diligent machine-translation effort within Microsoft Research. With it, Microsoft Research offers a simple, intuitive translation service—while making ongoing improvements to translation quality. In addition to the portal, its Bilingual Viewer features a unique, side-by-side Web-page viewer that translates entire Web pages with blinding speed between 25 sets of language pairs.

For Stephen Richardson and Heather Thorne, who are leading an effort to evangelize Microsoft Research’s machine-translation work for incorporation into a bevy of other Microsoft products and services, Windows Live Translator points the way to a future when the contents of the entire Web will be free of language-based limitations and it will be easy for users to communicate with people everywhere, from within any Microsoft product or Web service.

“This,” says Richardson, principal researcher in the Natural Language Processing (NLP) group within Microsoft Research Redmond, “is a technology that will literally change the way the world works. We’re in a place, here at Microsoft, where that can happen.”

The group’s machine-translation technology was showcased during a couple of events in early March. MIX08, Microsoft’s ongoing conversation with next-generation Web and interactive-agency professionals, scheduled in Las Vegas from March 5 to 7, featured the integration of Windows Live Translator with the upcoming version of Internet Explorer. And during TechFest 2008, an annual gathering set in Redmond on March 5-6 in which Microsoft employees and media representatives from around the world got a chance to observe and discuss the latest projects from Microsoft Research’s worldwide labs, current features and services, as well as future plans, were on display.

“Our vision,” Richardson says, “is to produce a machine-translation system and technology that can provide translation across all of the potential scenarios we can imagine, with Microsoft products and services around the world.”

It’s been a long journey for Richardson, who began working on machine translation while an undergraduate in the 1970s.

“I was a junior in college,” he recalls, “and I was on a project where we trying to create a machine-translation system that we felt would change the world. Everybody’s dream, right?

“Of course, it took a lot longer than I ever dreamt. But to be here now, involved with this great group of people putting out something that just has killer-app potential …”

Thorne, director of business strategy for the Machine Translation product team, comes to the project from an entirely different direction. Having studied Russian and International Studies during her undergraduate days, she found herself working on translation and interpretation while working for NASA on its joint space program with the Russians, and that led her to explore the state of the art of machine translation.

“Granted,” she says, “this was 15 years ago. I remember discovering that quality was quite low. It was not able to replace the need for human translators.”

For certain uses, though, this is slowly changing.

Four years ago, Thorne found her way to Microsoft, working for the Windows organization. Then she heard about Microsoft Research’s machine-translation work.

“When I discovered this team and what they were looking to do, that was a perfect fit for my background and my area of interest,” she says. “I realized that this would be a great opportunity to bring the experiences I’d had in much bigger businesses into this small team, which felt much more like a startup.”

She joined NLP in March 2007 and has played an integral role in guiding the team’s strategy toward integration of machine-translation technology into Microsoft offerings. For example, the team’s scalable Web service is being applied to address specific user scenarios, such as integration into Live Search, Internet Explorer, Windows Live Messenger, Office, and many other products and services. Users can download a widget that they can employ to add Translator to their own Web sites, and individuals can install a Windows Live Translator toolbar button for translations with a mere click. With twice the number of downloads from non-English-speaking markets compared with English-speaking markets, it’s clear that this service meets a need for international audiences.

Still, it’s been a formidable challenge to reach this point. Machine translation is a tough nut to crack. For a long time, machine translation was seen as largely unhelpful; users became frustrated with technology that often turned text in one language to gobbledygook in another.

“Machine translation had this bad reputation,” Richardson recalls, “of being unreadable sometimes.”

Perfection was proving stubbornly elusive. As it turns out, perfection itself was part of the problem.

“There was an acronym from the 1960s: FAHQT—fully automatic high-quality translation of general text,” Richardson says. “That was the holy grail of machine translation. That’s what everybody was trying for.”

FAHQT, though, turned out to be unrealistic. A couple of years ago, Jaap van der Meer, a pioneer in the translation industry, coined a new, more achievable acronym: FAUT—fully automatic useful translation. Instead of trying to devise a system robust enough to fool your school’s infallible French teacher, how about developing one sufficiently accurate to provide translations that could provide real value to real users in real time?

“What we’re trying to do is say, ‘You know, machine translation as a science is not perfect,’ “ Richardson says. “It’s far from perfect—just as search is far from perfect today. But there are a lot of things you can do to mitigate the imperfections and help customers get to the results they’re looking for.”

On one hand, there are user-interface improvements, such as the Bilingual Viewer, showing side-by-side Web-page translations that enable a user to compare a translation to the original. On the other hand, there are ways to improve the research process itself to deliver the right degree of accuracy to the right user in the right situation.

Enter MSR-MT, Microsoft Research’s machine-translation project.

MSR-MT is a data-driven machine-translation system behind Windows Live Translator that automatically acquires translation knowledge from previously human-translated text, combining linguistic knowledge and statistical processing into a hybrid approach. Using as input data millions of sentences from Microsoft technical materials that have been translated by humans, MSR-MT is capable of producing output in a single night that is on a qualitative par with systems that require months of human customization.

The system already has proven its value within Microsoft, having been used in 2003 to translate nearly 140,000 customer-support Knowledge Base articles into Spanish. The effort was extended to Japanese the next year and to French and German in 2005. Now, Microsoft’s Knowledge Base materials have been translated into nine languages by MSR-MT.

Such success has lowered the cost barrier to obtaining customized, higher-quality machine translation and is able to provide weekly updates and additions, a goal heretofore impossible to achieve. Bill Gates, Microsoft chairman, gave the mature technology the green light in 2005, and things took off from there.

“What we focused on the past year or two was to take the work we’ve used internally here at Microsoft and make it available outside the company in the most compelling initial scenario we could identify, which turned out to be Search,” Richardson says, “and then build a backbone system, a Web service that could not only supply translations to Search, but also would be the basis for anything else that we did in the future.”

The data-driven approach, Thorne adds, also enables Microsoft Research’s machine-translation efforts to focus on customer needs.

“Given that we probably can’t translate everything well,” she says, “we need to do a good job of understanding which Web sites people are looking at and what they are asking us to translate. What are the areas of the Web that people are really interested in?

“If we have limited resources and limited amounts of data we can get, where do we need to focus our efforts? It’s a combination of the technology getting better and us doing a better job of understanding the customer need.”

Such efforts, of course, require the efforts of many, as Richardson and Thorne are quick to note. Andreas Bode, the team’s development lead, has been instrumental in creating the Web-service infrastructure and leading all development. Chris Wendt, lead program manager, has worked closely with the other product teams to ensure successful integration of the Windows Live Translator Web service into their products. David Darnell has overseen the testing of the technology, and Arul Menezes and Chris Quirk were key contributors to the MSR-MT technology itself.

In addition, collaboration with the Live Search team has proved essential, and the Windows International organization has provided avid support.

“The reason why we have so many languages and gotten all the data we’ve gotten across Microsoft,” Richardson says, “is because of the effort by the internal localization community, which was spearheaded by the Windows International group.”

That team also devised the side-by-side interface that makes Windows Live Translator so easy to use. Initially, the user interface was called the Flipper Flopper. That whimsical contribution has evolved into one of the technology’s most popular features, the Bilingual Viewer.

It’s no surprise that much remains to be accomplished. New subject domains are being investigated, and product integration remains central to ongoing efforts.

“We’re always looking at improving the quality,” Richardson says, “and the more of the right kind of data that you have, and the more you do with it, the better quality you can get.”

For Thorne, it’s been an invigorating experience.

“It’s really, really exciting to be so close to a product where the people I sit next to are literally the guys who wrote the code,” she says. “It’s a very complicated space, and yet it’s still something that you can see and touch in this very tangible way. Everybody takes a lot of pride in what they do, and it’s really exciting to see the progress and to see everybody’s commitment to it.”

Richardson agrees wholeheartedly.

“We’ve always been a tight-knit group at NLP,” he says, “but our machine-translation incubation group has worked their tails off to produce something that has jumped to the forefront of what people have said is cool about machine translation. That makes me incredibly proud and grateful.”

BEE3: Putting the Buzz Back into Computer Architecture

By Rob Knies

bee3_73_73There was a time, years ago, when computer architecture was a most exciting area to explore. Talented, young computer scientists labored on the digital frontier to devise the optimal design, structure, and implementation of computer systems. The crux of that work led directly to the PC revolution from which hundreds of millions benefit today. Computer architecture was sexy.

These days? Not so much. But Chuck Thacker aims to change that.

Thacker, a Microsoft technical fellow regarded as a pioneer in the computing industry, is working with colleague John Davis to build a hardware platform called BEE3, designed to return architecture to the cutting edge of computer-science research.

“I was in computer-architecture research for several decades and built a number of interesting computer systems,” says Thacker, who in the 1970s and early ’80s led hardware development for the Computer Science Laboratory at Xerox’s renowned Palo Alto Research Center. “But you can’t really do that anymore, because you have to design chips, and it’s just too expensive.”

In addition, simulation techniques became too slow to enable full-system experiments using real software. As time went on, interest in computer architecture began to dwindle. Those projects and papers that were devoted to the area were increasingly focused on small, incremental advances. Relevant research slowed to a crawl.

“You can count the number of people in academia today who actually do chip building,” Thacker says, “on the fingers of one hand.”

Thus, the BEE3 mission: Change the game.

BEE3, engineered by Celestica, a leading manufacturing firm, employs field-programmable gate arrays (FPGAs), semiconductors with programmable logic components, along with 64 gigabytes of DDR2 DRAM memory and a variety of high-bandwidth interfaces, all combined in a chassis that looks like a computer but is in fact a platform to emulate architectures and changes to standard architectures.

b3_boards_030John Davis (left) and Chuck Thacker of Microsoft Research Silicon Valley collaborate on the BEE3 computer-architecture hardware platform.

“If you want to try out a new architecture or a new feature,” Thacker says, “it’s very difficult to do these days, because you have to actually build chips to build anything of substantial size. Using FPGAs, you don’t have to build chips. You can design the thing and load the FPGA with some bytes that tell it what it’s supposed to do logically.”

At that point, hardware once again begins to play a significant role in computer-architecture research.

“This is a very exciting opportunity,” says Davis, a research hardware-design engineer based, like Thacker, at Microsoft Research Silicon Valley, “especially in the academic research arena, which has been missing because it is so expensive to build chips from an actual real-cost standpoint.”

Hence, the rationale for the BEE3 project—or at least part of it.

“The project was set up for two reasons,” Thacker says. “One is to help the university community, which is one of the things we try to do a lot here in Microsoft Research. The other was that we want the machines for our own research.”

The timing is right because of the increasing maturity of FPGAs.

“They are now large enough and design tools are good enough that you can build very complex things,” Thacker states. “You can use them both for architectural experimentation and for accelerating a CPU for algorithms that don’t fit very well into [sequential] architecture.”

The viability of the FPGA approach was demonstrated last summer, when Zhangxi Tan, then an intern at Microsoft Research Silicon Valley, built a system for solving the problem of binary satisfiability, commonly used in design automation.

“He got much faster speed than what a computer could do,” Thacker reports, “because the algorithm is exactly suited for what can be done in FPGAs.”

Indeed, speed and power are the two attributes Thacker hopes the BEE3 system can help address.

“One of the big problems that we face as a company is that it’s become increasingly clear that processors aren’t going to get faster,” he says. “They dissipate too much power now, and it’s a real challenge to get rid of it. We want to look at some of these new architectures as possibilities for solving those two problems, the speed problem and the power problem.”

And Thacker and Davis have specific ideas on how BEE3 could help.

“We want to try some new techniques in internal communication within a multicore processor,” Thacker says. “In particular, we have some ideas for how to do the switch networks on such a chip and on how to use message passing as something that is available directly to programs.

“One of the nice things about these systems is that they can be very intricately instrumented, so we can get a lot of data.”

That instrumentation is an area in which Davis can help. He began working with Thacker about a year ago upon joining Microsoft Research, having developed a similar type of board as part of his Ph.D. thesis project, making him a natural to step into a project like BEE3.

“Chuck and I work together on all the aspects of the board and related gateware,” Davis says, “while interacting with our partners in terms of the prototype board manufacturing.”

The BEE3 name, incidentally, stands for the Berkeley Emulation Engine, version 3. Its predecessors, BEE and BEE2, were designed by the University of California’s Berkeley Wireless Research Center, and Thacker had used FPGAs for some projects while working at the Systems Research Center at Digital Equipment Corp before joining Microsoft Research. At the time, though, FPGAs were not sufficiently mature for the kind of architectural use BEE3 enables.

The academic connection is significant, because not only is Microsoft Research working with a variety of academic and industrial partners on BEE3, but academia also stands to be one of the prime beneficiaries. The hardware platform will be shared with academic researchers performing computer-architecture research.

“These things always go better if there are more people using them,” Thacker explains. “We decided that in order to actually benefit the way computer-architecture research is done, it would be better to just share this.”

Celestica provided the board layout and fabrication.

“The actual engineering effort … they did the schematic, the layout, the routing,” Davis says. “They’ve been a great help.”

As it turns out, there are real benefits in working with a professional hardware firm, as opposed to having the work done by academic partners.

“If you do a large-scale design like this with graduate students,” Thacker says, “you don’t get an optimal result, because it’s typically their first design. They spend a long time mastering the design tools, and they just don’t know the tricks that a professional board designer knows.

“This isn’t a matter of graduate students being dumb. They’re very smart. It’s just that, No. 1, they’re inexperienced, and No. 2, it’s not really good pedagogy, because they spend a lot of time doing the design, and as a result, they don’t have a very broad education when they graduate. I said at the beginning of the project that it was likely that the pros could get something that is half the cost and considerably more reliable in half the time, and it’s worked out that way exactly.”

Academia will, though, play a key role in BEE3’s future success. Thacker and Davis have worked closely with researchers from the University of California, Berkeley, which started the Research Accelerator for Multiple Processors (RAMP) consortium, along with the Massachusetts Institute of Technology, Stanford University, Carnegie Mellon University, the University of Texas at Austin, and the University of Washington. RAMP will provide the conduit by which BEE3 can be shared with the academic community.

“It’s six universities working together,” Davis says, “with the goal of enabling large-scale multiprocessor research.”

Other partners are contributing to BEE3, as well. Function Engineering, of Palo Alto, Calif., performed thermal modeling to ensure that the airflow in the hardware was working appropriately.

“They designed the case of the system,” Thacker says. “They designed the heat sinks for the FPGAs and did all the computational fluid-dynamic modeling to make sure that it would all work. That is one of the largest mistakes you can make in designing a computer system, to get the thermal properties wrong, because then it overheats and doesn’t work. Function was enormously helpful in this area.”

Xilinx, of San José, Calif., manufactures the FPGAs themselves, the chips and the tools to design them.

labeledbee3The BEE3 hardware with components labeled. The Virtex 5 LX110T components are the platform’s field-programmable gate arrays.

But Celestica has been the most significant partner in bringing BEE3 to fruition. Celestica had the design expertise. Microsoft was interested in the potential of such a hardware platform, not in providing the hardware itself.

“Celestica has reduced a lot of the complexity in terms of the actual board design and the resulting prototypes, which were fabulous,” Davis reports. “When we got them back, within a couple of days, we had test software and processors in the FPGAs up and running.”

It’s an unusual project for Celestica, Thacker notes, but the firm’s close relationship with Microsoft didn’t hurt. Celestica is a major manufacturer of Xbox 360 consoles.

“Celestica would not normally take something like this on,” Thacker observes, “because when they do engineering, they want to have a large manufacturing follow-on. But our business relationship with them is already very, very deep. They were willing to do it for us because they found it an interesting project.”

They will get the satisfaction, however, of helping ensure that BEE3 is tangible and provides immediate value.

“The system essentially works,” Thacker says. “We found one problem in the original board design and are having it redesigned, at which point we will transition it into production and we will start using it in our own research. Up until now, this has been a project in infrastructure development, not actual research, but now we can actually begin to use it.”

That prospect has Thacker and Davis enthused.

“The coolest part of this project,” Davis says, “is the board design actually is better than the devices that are on it. We’re actually able to look at signals at a higher frequency than the FPGAs are supposed to operate at, and that’s pretty exciting.

“With this platform, you’re able to validate your work and enable technology transfer from academia to industry much, much quicker. That’s a very exciting place to be.”

For Thacker, the excitement lies in the prospect of returning computer architecture to an esteemed place at the forefront of computer science.

“We want,” he says, “to revitalize computer-architecture research.”

Singularity: Rethinking Dependable System Design

What would software look like if it were designed from scratch with dependability and trustworthiness as the primary goal?

That’s the question Microsoft Research’s Galen Hunt, Jim Larus, and a team of colleagues asked themselves when they embarked on an ambitious research project in 2003. Five years later, they’re ready to propose an answer: It would look like Singularity, a new system-architecture and operating system built on advances in programming languages and tools.

Hunt, a principal researcher and manager of Microsoft Research Redmond’s Operating Systems Group, and Larus, a research-area manager in the Software Improvement Group, aimed to rethink system design in light of many research advances and a changed computing environment. And now that Singularity has reached a useful level of stability and functionality, they think it’s time that other researchers in academia and industry have an opportunity to build on their research.

On March 4, Microsoft Research made the Singularity source code available at no charge for academic, non-commercial use by releasing it to CodePlex, an online portal created in 2006 to foster collaborative software-development projects and to host shared source code. Hunt and Larus hope the research prototype will be used as a laboratory for experimentation and innovation, much as it has been within Microsoft Research. Over the years, more than 40 Microsoft Research researchers and interns have collaborated on the project, which incorporated their ideas on security, programming languages, tools, and operating systems—and accelerated their own research.

galen_hunt“Our goal was to make Singularity small enough, simple enough, and well-designed enough that you can try out radical new ideas quickly,” Hunt says. “Our thinking is that a researcher with a great new idea for improving operating systems could get from idea to published paper in under a year using Singularity.”

Rethinking 1960s-Era Design Decisions

The Singularity research project began with the idea of building more dependable software. Hunt, who specializes in operating-system development, and Larus, an expert in tools and programming languages, realized that to accomplish this, they would need better tools and a better system architecture.

The status quo that confronted them was the decades-long tradition of designing operating systems and development tools. Contemporary operating systems—including Microsoft Windows, MacOS X, Linux, and UNIX—all trace their lineage back to an operating system called Multics that originated in the mid-1960s. As a result, the researchers reasoned, current systems still are being designed using criteria from 40 years ago, when the world of computing looked much different than it does today.

“We asked ourselves: If we were going to start over, how could we make systems more reliable and robust?” Larus says. “We weren’t under the illusion that we’d make them perfect, but we wanted them to behave more predictably and remain operating longer, and we wanted people to experience fewer interruptions when using them.”

The researchers set out to design a simple, minimalist system. They were clear from the beginning that Singularity would bear no resemblance to a full-fledged operating system such as Windows, nor was it ever intended to replace Windows. They sought to create an operating system for the research environment, structured to embody the design criteria of dependability and robustness, and to demonstrate the practicality of new technologies and architectural decisions.

Technically Speaking, Singularity Is Different

Singularity differs fundamentally from other operating systems in that it is written almost entirely in an extension of C#, a modern, high-level programming language. This enables a more dependable overall computing environment because C# gives Singularity security advantages over operating systems written in lower-level languages such as C or C++. For example, by using C#, the researchers prevented a class of errors known as buffer overruns, thereby eliminating an area of vulnerability typically exploited by worms and viruses.

jim_larusSingularity also incorporates three key architectural features to improve system dependability. First, Singularity pioneers the use of software-isolated processes (SIPs) to help protect programs and system services. SIPs enable programs to be broken down into components that are isolated from other software components running on the same device. This enables pieces of a system to fail without risking a total system failure. Consider this analogy: In a car, the brakes don’t fail if the radio stops working.

“In the past, creating many processes in an operating system was impractical from a cost perspective, largely because they required special support from the hardware,” Hunt says. “Rather than use hardware to build boundaries between processes, we figured out a way to build processes using a software technology called static analysis.”

Static analysis, a large and important research area at Microsoft Research, inspects a program’s source code in advance to make sure a process obeys certain rules that guarantee it’s isolated from the rest of the system. Traditionally, programs were checked at run time, using hardware mechanisms that date to the less-disciplined code of the mid-’60s.

Singularity’s second noteworthy architectural feature relates to the fact that a program’s many SIPs need to communicate and share information because they work toward shared objectives. To avoid miscommunications that can lead to errors and breakdowns, the Singularity researchers developed what they call “contract-based channels” for communications.

“We figured out how to describe the form in which communications should take place between two processes, and using static analysis, we can check the codes of the processes at compile time,” Hunt explains. “So before the code ever runs, we can confirm that the processes communicate correctly.”

Singularity’s third unique architectural feature, called “manifest-based programs,” represents another shift in orientation. Traditionally, operating systems have had no “knowledge” of a program’s composition, its purpose, or the resources it uses. Presented with a set of bits, the operating system would simply run them. Singularity, with its emphasis on overall system dependability, takes a different approach to ensure that a new program won’t “break” the programs already on board.

“We basically say, if you want to install a program to run on a Singularity system, you have to provide some information about it so we can preserve certain properties that make the system more reliable,” Larus explains. “You have to provide a manifest of the program pieces and how they fit together, and we’re going to check it. More important, we reserve the right to say ‘no.’ If a certain program doesn’t follow the rules set down for the system, you can’t install or run it.”

This ability to start with a clean slate and to retool how software is written—from the ground up—is a testament to the spirit of innovation that permeates Microsoft Research, Hunt and Larus say.

“Singularity was only possible because the environment at Microsoft Research allowed us to collect a diverse group of researchers eager to participate in a project to fundamentally rethink a basic part of everyday computing,” Larus says. “Applying everyone’s research perspectives helped us understand and demonstrate a new way to construct software systems.”

Video

Videos

Videos

Microsoft Research blog

Translating the Web for the Entire World

By Rob Knies, Managing Editor, Microsoft Research People all over the world use the Internet every day, to purchase goods or services, to search for information, to find diversions. But is the World Wide Web truly worldwide? It’s difficult to make the case. Estimates claim that approximately 70 percent of Web pages today are created in the English language, while the percentage of non-English speakers is growing faster than that of English speakers. So what…

March 2008

Microsoft Research Blog