Parallel Preprocessing for Path Queries without Concurrent Reading

We consider the problem of preprocessing a tree T with edge labels drawn from a semigroup such that subsequent queries for the semigroup product of the edge labels on a path in T can be answered efficiently. A sequential algorithm exhibiting an optimal trade-off between preprocessing time and query time was described by Chazelle. A parallelization of the preprocessing part of Chazelle's algorithm for the exclusive-read exclusive-write parallel RAM (EREW PRAM) was announced by Alon and Schieber, but few details were provided. Later a different solution, complete with all details, was described by Thorup, but it requires the stronger concurrent-read exclusive-write PRAM. We describe a simple algorithm for the EREW PRAM.

Authors

• Torben Hagerup

Keywords

No keywords are indexed for this paper.