Computing 'fusion trees' to explode barriers.
Most computers spend only a small fraction of their time as calculators. Instead, they serve as gigantic gi·gan·tic
1. Relating to or suggestive of a giant.
a. Exceedingly large of its kind: a gigantic toadstool.
b. filing systems, searching for records or sorting data into manageable forms. Now, two computer scientists have discovered a method for hurdling a theoretical barrier that appeared to limit how fast a computer can sort or search.
Developed by Michael L. Fredman of the University of California, San Diego UCSD is consistently ranked among the top ten public universities for undergraduate education in the United States by U.S. News & World Report. It is a Public Ivy.  For graduate studies, most of UCSD's Ph.D. , and Dan E. Willard of the State University of New York (body) State University of New York - (SUNY) The public university system of New York State, USA, with campuses throughout the state. at Albany, this mathematical recipe, or algorithm, theoretically could speed the process of shuffling data by circumventing a key step in traditional sorting and searching methods. Whereas standard methods compare two numerically encoded items at a time, the new approach provides a way to compare many numbers at once.
Although not yet applicable to any practical situation, this theoretical result overturns long-held notions, described in nearly every computer-science textbook, concerning the speed of certain algorithms. "When Fredman and I originally made this discovery, people continually asked us where we were cheating," Willard says.
Computer scientists have generally assumed that sorting involves successively comparing two items or numbers at a time to see which one should precede the other. In the worst possible case for a given selection of items, such a process requires making a specific number of comparisons that can be calculated for any number of items. That number represents a kind of minimum speed limit for sorting.
In effect, Fredman and Willard found a way to raise that minimum speed limit. Instead of relying solely on comparisons of number pairs, they manipulate the data and organize the numbers into a new form, dubbed dub 1
tr.v. dubbed, dub·bing, dubs
1. To tap lightly on the shoulder by way of conferring knighthood.
2. To honor with a new title or description.
3. a "fusion tree The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help [ improve the introduction] to meet Wikipedia's layout standards. You can discuss the issue on the talk page. ," which enables them to compare one number against many others during a single computational Having to do with calculations. Something that is "highly computational" requires a large number of calculations. step. A saving results because the number of instructions needed to manipulate the data is less than the number of comparisons normally required in sorting.
The algorithm developed by Fredman and Willard performs this feat by considering only a small portion of the string of ones and zeros Ones and Zeros is the second full-length release by Canadian indie rock group Immaculate Machine. It is their first official release through Mint Records. Music videos were released for the songs "Broken Ship" and "So Cynical". , or bits, used to express each number. "We noticed that when you want to compare one number with several, you don't need all the bits of each of the numbers you are comparing," Willard says.
Their sorting method provides a way to select the relevant bits from a given set of numbers, group these subsets into a single expression and perform certain arithmetical operations to make multiple comparisons in a single step. A similar approach raises the minimum speed limit for searching.
At present, the new algorithms significantly outpace out·pace
tr.v. out·paced, out·pac·ing, out·pac·es
To surpass or outdo (another), as in speed, growth, or performance.
[-pacing, standard methods only when the number of items in the database is sufficiently large In mathematics, the phrase sufficiently large is used in contexts such as:
That research could lead to practical, efficient methods for sorting items in databases much larger than any in existence today. Fredman and Willard are also exploring the possibility that their approach can speed other algorithms developed in the past to solve various problems, such as finding the shortest or least costly telephone or transportation network to link a number of cities.
"Their work . . . will have profound influence on theoretical computer science for years to come," comments B. Gopinath of Rutgers University Rutgers University, main campus at New Brunswick, N.J.; land-grant and state supported; coeducational except for Douglass College; chartered 1766 as Queen's College, opened 1771. Campuses and Facilities
Rutgers maintains three campuses. in Piscataway, N.J.
A paper describing the new algorithms has been accepted for publication in the JOURNAL OF COMPUTER AND SYSTEM SCIENCES.