Computing that would normally take five million years to complete now takes five minutes, thanks to research at the University of Toronto.

A paper in the February edition of Science describes how U of T researchers created a new way of computing called "affinity propagation," which can be used to organize information in areas such as medical imaging, drug discovery, genetics, telecommunications, automobile traffic planning, school access planning and astrophysics.

Image: Brendan Frey

"Affinity propagation works by considering all possible interpretations of the data at once," says Professor Brendan Frey of the Edward S. Rogers Sr. Department of Electrical and Computer Engineering. "All possible hypotheses are considered and these many, many hypotheses exchange messages in a manner similar to messages exchanged between neurons in the brain or between traders on the stock exchange floor until a good set of hypotheses is found. This is quite unlike the standard approach, which was stuck on the idea that information should be analysed by repeatedly refining a small number of hypotheses."

To illustrate its potential, researchers showed the system thousands of images of hand-written numbers taken from postal codes. It took only five minutes to find a small collection of pictures that accurately account for the various styles of handwriting. The standard computing approach, which is currently used in many areas all around the world, would take about five million years to account for the writing styles as accurately. The system works by first scanning the data and then finding items called "exemplars" or "hypotheses," which do a good job of reflecting the content of all the data. What sets it apart from other computing paradigms is that it is able to take all the material presented and find exemplars by exchanging messages between all the data items.

"The data items are able to bounce ideas off the others and say, No, this data stays with me, or, This data fits better with you," Frey says. "It is essentially making up its own mind on how to make sense of the information presented."

Frey and graduate student, Delbert Dueck, used their technique to explore the problem of identifying a restricted number of Canadian and American cities that are most easily accessible by other cities in terms of estimated commercial airline travel time. By taking into account a variety of factors - headwinds, estimated stopovers, heavy air traffic - the system was able to quickly determine alternative flight routes that significantly reduce travel time and emissions.

"This new approach to processing information could potentially be used to reduce airline emissions," Dueck says, who notes that U of T students have used the method to discover new things about basketball statistics, robotic navigation, computer networks, automobile traffic patterns, e-mail traffic patterns, international trade, HIV vaccines and the frog genome.

Frey says that this research came about due to a recent convergence of ideas in the fields of electrical engineering, computer science, statistical physics, genomics and economics.

"It turns out that in the past 40 years, pioneers in several fields of research have been inventing techniques that work by creating networks connecting data together, and transmitting messages back and forth inside these networks," he says. "Recently, researchers at U of T and a couple other leading universities have recognized the similarities in these pioneering pieces of research and have come up with a general purpose paradigm for solving data organization problems." By mimicking how the human brain works, the approach brings science one step closer to a free-thinking technology. Says Frey, "This computing paradigm will likely lead to breakthroughs that will impact society in several ways."

The research was funded by the Natural Sciences and Engineering Research Council of Canada, the Canadian Institutes of Health Research and Genome Canada/Ontario Genomics Institute. Frey is a fellow of the Canadian Institute for Advanced Research.

This article was written from a news release by University of Toronto