wtwolfe@hubcap.clemson.edu (Bill Wolfe) (09/04/89)
Here are some other articles which may be of interest to readers
of this group; I probably won't have time to review them, but they
do seem to be quite interesting, so here's a brief summary of each:
Cascading Divide & Conquer:
A Technique For Designing Parallel Algorithms
(SIAM Journal on Computing, Vol. 18, No. 3, pp. 499-512, 5/89)
This paper presents a number of general techniques for parallel
divide-and-conquer which can be applied to any problem solvable
by a divide-and-conquer method such that the subproblem merging
step can be implemented using a restricted, but powerful, set of
operations, which include (i) merging sorted lists, (ii) computing
the values of labeling functionf on elements stored in sorted lists,
and (iii) changing the identity of elements in a sorted list
monotonically. The elements stored in such sorted lists need not
belong to a total order, so long as the computation can be specified
so that we will never try to compare two incomparable elements.
Efficient parallel algorithms are then presented for solving a
number of fundamental problems from computational geometry, such
as finding maxima in three dimensions; several of these algorithms
are optimal in that their time complexity per processor, multiplied
by the number of processors, is equal to the sequential lower bound
for the problem.
New Trie Data Structures Which Support Very Fast Search Operations
(Journal of Computer & System Sciences,
Vol. 28, No. 3, pp. 379-394, June 1984)
A new data structure called the q-fast trie is introduced. Given
a set of N records whose keys are distinct nonnegative integers
less than some initially specified bound M, a q-fast trie uses
space O(N) and time O(square_root(log(M))) for insertions,
deletions, and all the retrieval operations commonly associated
with binary trees. A simpler but less space efficient data
structure called the p-fast trie is defined.
Bill Wolfe, wtwolfe@hubcap.clemson.edu