Title :
Sorting on a parallel pointer machine with applications to set expression evaluation
Author :
Goodrich, Michael T. ; Kosaraju, S. Rao
Author_Institution :
Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
Optimal algorithms for sorting on parallel CREW (concurrent read, exclusive write) and EREW (exclusive read, exclusive write) versions of the pointer machine model are presented. Intuitively, these methods can be viewed as being based on the use of linked lists rather than arrays (the usual parallel data structure). It is shown how to exploit the `locality´ of the approach to solve a problem with applications to database querying and logic programming (set-expression evaluation) in O(log n) time using O(n) processors
Keywords :
data structures; information retrieval; logic programming; sorting; EREW; database querying; linked lists; logic programming; optimal algorithms; parallel CREW; parallel data structure; parallel pointer machine; set expression evaluation; sorting; Application software; Arithmetic; Data structures; Databases; Graph theory; Joining processes; Phase change random access memory; Read-write memory; Sorting; Writing;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63477
