In a broad range of data mining tasks, the fundamental challenge is to efficiently explore a very large space of alternatives. The difficulty is two-fold: first, the size of the space raises computational challenges, and second, it can introduce data sparsity issues even in the presence of very large datasets. In this talk, we'll consider how the use of hierarchies (e.g., taxonomies, or the OLAP multi-dimensional model) can help mitigate the problem.