Printer Friendly
The Free Library
22,728,043 articles and books

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.

 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.[3] It is a Public Ivy. [1] 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.

 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.


 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:
is true for sufficiently large
. "The complicated nature of these algorithms, as they are currently constituted, does not allow for improved efficiency unless they are being applied to vastly large amounts of data," Fredman says. "Nevertheless, these results suggest that future avenues of research may eventually benefit from the discovery."

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.
COPYRIGHT 1991 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1991, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

 Reader Opinion




Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:an algorithm that speeds up how fast computers can sort information
Author:Peterson, Ivars
Publication:Science News
Date:Jun 29, 1991
Previous Article:Do some SIDS victims actually suffocate?
Next Article:Record-breaking brightness poses enigma.

Related Articles
A parallel path for speedy solutions.
Record speedups for parallel processing.
Quantum-quick queries: using quantum computation, in theory, to speed up database searches.
Determine product quality reliably.
Michael Joo. (Reviews).
Use of relational and conceptual graphs in supporting e-learning tasks.
Mentor Graphics Announces New Bit-Accurate C++ Datatypes that Accelerate Algorithm Validation by 10x.

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters