Embodiments relate to constructing a tree-shaped Bayesian network from variables associated with conditional dependencies in a given data set, the constructing being performed by a plurality of processors in parallel. An aspect includes assigning a plurality of variables as nodes to a respective plurality of processors. Another aspect includes operating the plurality of processors in a parallel manner to determine a correlation for each pair of nodes. Another aspect includes M variables that are randomly selected as primary nodes defining (M+1) sub-trees. Another aspect includes in each sub-tree the plurality of processors are operated in a parallel manner to determine a correlation for the remaining nodes with each of the primary nodes and to allocate each remaining node to one of the (M+1) sub-trees.