Time-space optimal parallel set operations

摘要

The authors present parallel algorithms for the elementary binarynset operations that, given an EREW PRAM (exclusive-read, exclusive-writenparallel random-access memory) with k processors, operate onntwo sorted lists of total length n innO(n/k+log n) time and O(k) extranspace, and are thus time-space optimal for any fixed value ofnk⩽n/(log n). Moreover, the methods arencompletely general in that they are stable (records with identical keysnretain their original relative order), they do not modify records (evenntemporarily) as they execute, and they require no information other thanna record's key