A parallel solution to the extended set union problem with unlimited backtracking

摘要

We study on the EREW-PRAM model a parallel solution to the extended set union problem with unlimited backtracking which maintains a dynamic partition /spl Pi/ of an n-element set S subject to the usual operations Find, Union, Backtrack and Restore as well as the new operations SetUnion, MultiUnion. The SetUnion operation as a special case of the commonly known Union operation aimed to unify two pre-specified set-names, while MultiUnion operation deals with a batch of Union operations. A new data structure, called k-Parallel Union Find (or, k-PUF) trees, is introduced to represent a disjoint set in /spl Pi/. The structure is defined for a wide range for the parameter k, but the more interesting results are achieved for k=log n/log log n. In this case, using the k-PUF trees, both SetUnion and Restore operations are performed in constant parallel time requiring optimal work O(k). This constant-time performance is not achievable parallelizing the existing data structures. Moreover, using p=O(k) processors, MultiUnion for a batch of p operations is performed in O(k) time, requiring optimal work O(pk).