Parallel Exploration of an Unknown Random Forest

Konferenz: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
09.04.2018 - 12.04.2018 in Braunschweig, Germany

Tagungsband: ARCS 2018

Seiten: 4Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

Keller, Joerg; Eitschberger, Patrick (Faculty of Mathematics and Computer Science, FernUniversität in Hagen, 58084 Hagen, Germany)

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