Journal of the ACM Bibliography

Abstract

We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel data structure). We also show how to exploit the ``locality'' of our approach to solve the set expression evaluation problem, a problem with applications to database querying and logic-programming, in O(log n) time using O(n) processors. Interestingly, this is an asymptotic improvement over what seems possible using previous techniques.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in: Michael T. Goodrich and S. Rao Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation (preliminary version). In 30th Annual Symposium on Foundations of Computer Science, pages 190-195, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

Categories and Subject Descriptors: E.1 [Data Structures] -- arrays, lists; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sorting and searching

General Terms: Algorithms, Theory, Verification

Additional Key Words and Phrases: Cascade merging, expression evaluation, linking automaton, mergesort, parallel algorithms, pointer machine, PRAM

Selected references

• K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka. A simple parallel tree contraction algorithm. Journal of Algorithms, 10(2):287-302, June 1989.

• Mikhail J. Atallah, Richard Cole, and Michael T. Goodrich. Cascading divide-and-conquer: A technique for designing parallel algorithms. SIAM Journal on Computing, 18(3):499-532, June 1989.

• Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 80-86, Boston, Massachusetts, 25-27 April 1983.

• Gianfranco Bilardi and Alexandru Nicolau. Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines. SIAM Journal on Computing, 18(2):216-228, April 1989.

• Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427-462, June 1988.

• Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1(2):133-162, 1986.

• Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, August 1988.

• Jia-Wei Hong, Kurt Mehlhorn, and Arnold L. Rosenberg. Cost trade-offs in graph embeddings, with applications. Journal of the ACM, 30(4):709-728, October 1983.

• Gary L. Miller and John H. Reif. Parallel tree contraction, part 2: Further applications. SIAM Journal on Computing, 20(6):1128-1147, December 1991.

• Michael S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5:65-92, 1990.

• Yossi Shiloach and Uzi Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. Journal of Algorithms, 2(1):88-102, March 1981.

• Robert Endre Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences, 18(2):110-127, April 1979.

Shortcuts: