Parallel Exploration of an Unknown Random Forest

Abstract:
We investigate how to explore with a parallel machine a random and unknown forest, of which we only know an upper bound on the total size, some leaves to start from, and the roots. The size of the forest is too large to represent it explicitly in the machine’s main memory. Instead for each node, its parent node is given by an oracle, i.e. a piece of code of which no particulars may be known. We present a parallel algorithm, and use experiments to find parameter settings that influence the runtime favorably