Starting
over speeds searches
By
Kimberly Patch,
Technology Research News
It 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 wellknown combinatorial
problem is the traveling salesman dilemma: plotting the most efficient
route through even a dozen cities is difficult and timeconsuming.
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 runtimes 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/condmat/0112142
Advertisements:

February
6, 2002
Page
One
Tiny chain revs microdevices
Labsonachip 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:



