Multi-relational data mining algorithms search a large hypothesis space in order to find a suitable model for a given data set. During this search, a huge number of complex queries has to be evaluated on the data set. This explains why multi-relational data mining algorithms (e.g. ILP algorithms) typically have high run times. In this text we give an overview of two techniques designed to reduce these run times. We show that this is possible by exploiting similarities in both queries and data sets. The first technique is query-pack evaluation and the second one is parallel cross-validation.