One of the basic tasks for Bayesian networks (BNs) is that of learning a
network structure from data. The BN-learning problem is NP- hard, so the
standard solution is heuristic search. Many approaches have been proposed
for this task, but only a very small number outperform the baseline of
greedy hill-climbing with tabu lists; moreover, many of the proposed
algorithms are quite complex and hard to implement. In this paper, we
propose a very simple and easy-to-implement method for addressing this
task. Our approach is based on the well-known fact that the best network (of
bounded in-degree) consistent with a given node ordering can be found very
efficiently. We therefore propose a search not over the space of structures,
but over the space of orderings, selecting for each ordering the best
network consistent with it. This search space is much smaller, makes more
global search steps, has a lower branching factor, and avoids costly
acyclicity checks. We present results for this algorithm on both synthetic
and real data sets, evaluating both the score of the network found and in
the running time. We show that ordering-based search outperforms the
standard baseline, and is competitive with recent algorithms that are much
harder to implement.