In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures. June 1998.

78k compressed postscript 361k pdf

**Abstract:**
We present parallel algorithms for union, intersection and difference
on ordered sets using random balanced binary trees (treaps). For two
sets of size *n* and *m* (*m <= n*) the
algorithms run in expected *O(m* log *(n/m))* work and
*O(*log *n)* depth (parallel time) on an EREW PRAM with
scan operations (implying *O(* log * ^{2} n)*
depth on a plain EREW PRAM). As with the sequential algorithms on
treaps for insertion and deletion, the main advantage of our algorithms
are their simplicity. In fact, our algorithms for set operations seem
simpler than previous sequential algorithms with the same work bounds,
and might therefore also be useful in a sequential context. To
analyze the effectiveness of the algorithms we implemented both
sequential and parallel versions of the algorithms and ran several
experiments on them. Our parallel implementation uses the Cilk shared
memory runtime system on a 16 processor SGI Power Challenge and a 6
processor Sun Ultra Enterprise. It shows reasonable speedup: 6.3 to
6.8 speedup on 8 processors of the SGI, and 4.1 to 4.4 speedup on 5
processors of the Sun.

@inproceedings{BlRM98, author = "Guy E.~Blelloch and Margaret Reid-Miller", title = "Fast Set Operations Using Treaps", booktitle = "Proceedings of the 10th Annual {ACM} Symposium on Parallel Algorithms and Architectures", pages = "16--26", address = "Puerto Vallarta, Mexico", month = jun, year = 1998}

Margaret Reid-Miller Last modified: Fri Jan 17 17:31:54 EST 2003