Starting
over speeds searches
By
Kimberly Patch,
Technology Research NewsIt may sound counterintuitive, but starting over from the beginning may actually speed up certain types of search algorithms.
A pair of researchers in France have found that it is possible to speed search algorithms by recognizing when things are not going so well, and starting over again. The research may help speed up searches on networks like the Internet.
The scheme is analogous to a puzzle whose pieces can fit together in several different ways, causing someone putting it together to fit the wrong pieces together without realizing it, said Andrea Montanari, a theoretical physics researcher at the École Normale Supérieure in France.
There are two basic strategies in doing a puzzle like this, Montanari said. One strategy is "completing the puzzle, realizing that it is [not] correct and then trying to correct all your choices in reverse order," she said. The trouble with this strategy is if a mistake was made early on, correcting it will take a lot of time.
A second strategy is to try to correct the very last steps, but if this does not work, to begin again.
"This may seem a crazy choice since you waste a lot of work, but it gives you the time for many different trials," said Montanari.
The researchers determined when it makes sense to use the second strategy on hard, combinatorial problems, which show up frequently in science and technology and are a ubiquitous aspect of large random structures like networks. There are no shortcuts to solving combinatorial problems. For each step in this type of problem, combinatorial algorithms randomly search through all the possibilities to find an answer. A well-known combinatorial problem is the traveling salesman dilemma: plotting the most efficient route through even a dozen cities is difficult and time-consuming.
The researchers' work combined aspects of coding theory, which must deal with rare events in the form of transmission errors that cause loss of information, and combinatorial optimization problems, which vary widely in running times of randomized algorithms, said Montanari. A chart of the run-times of a search algorithms shows a few situations where the algorithm took a very long time to find the answer, but also a few situations where it found the correct answer answer very quickly.
"The idea [is] to discard bad fluctuations, and try to exploit the good ones in backtrack algorithms. These algorithms proceed by fixing one by one the variables of the problem. Good fluctuations appear when [a problem] is easily solvable without correcting the choices made so far," she said.
The research showed that the second strategy is the better one if the probability for a rare event -- like happening to correctly put together the puzzle pieces -- is not too small, said Montanari.
The researchers showed that the running times of search algorithms can be greatly reduced using this strategy, according to Montanari. "One can analyze quite accurately... exceptional fluctuations and exploit them [to improve] search algorithms," she said.
The idea of starting over in random searches is not new, said Edward Tsang, a computer science professor at the University of Essex in England. The researchers' contribution has to do with timing. "The key question is when to restart -- when to give up the current search," he said.
The researchers are currently looking at how their method works with more sophisticated problems. "Having efficient tools for solving [combinatorial problems] and understanding the behavior of such tools is crucial" in a world where networks are important, said Montanari.
Montanari's research colleague was Ricardo Zecchina of the International Centre for Theoretical Physics in Italy. The research was funded by at the École Normale Supérieure in France and the International Centre for Theoretical Physics.
Timeline: Now
Funding: University
TRN Categories: Data Structures and Algorithms; Databases and Information Retrieval; Internet
Story Type: News
Related Elements: Technical paper, "Boosting Search by Rare Events," posted in the Computing Research Repository at http://xxx.lanl.gov/abs/cond-mat/0112142
Advertisements:
February 6, 2002
Page One
Tiny chain revs microdevices
Labs-on-a-chip gain micro mixer
Starting over speeds searches
Nudged nested nanotubes may oscillate
Portfolios boost quantum computing
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
