The MAESTRA project (http://maestra-project.eu/) addresses the ambitious task of predicting different types of structured outputs in several challenging settings, such as semi-supervised learning, mining data streams and mining network data. It develops machine learning methods that work in each of these settings, as well as combinations thereof. The techniques developed are applied to problems from the area of biology and bioinformatics, sensor data analysis, multimedia annotation and retrieval, and social network analysis. The talk will give an introduction to the project and the topics it addresses, an overview of the results of the project, and a detailed description of selected techniques and applications: Semi-supervised learning for structured-output prediction (SOP) and SOP on data streams will be discussed for the task of multitarget regression (MTR), as well as applications of MTR for the annotation/retrieval of images.