The search of novel materials using in-silico high-throughput screening is emerging as a fundamental step in the pipeline of materials discovery, but its low yields in terms of synthesisable structures limit its effectiveness. In order to isolate configurations that show promise to be stable at experimental conditions, scientists have traditionally relied on a convex hull construction, which finds the phases that are favourable under known thermodynamic boundary conditions (i.e. pressure, compositions). While this scheme is robust and computationally inexpensive, it is severely limited: it can only isolate phases which exhibit stability to well known thermodynamic variables and does not provide a systematic way of dealing with the inevitable uncertainties in the computationally determined formation energies of the candidate phases, or with the presence of multiple similar phases that only differ because of disorder or defects. In this thesis, we introduce a novel thermodynamic framework which aims at enhancing the exploratory power of structure searches by generalising the convex hull construction (GCH). This scheme relies on a set of data-driven, structural descriptors which correlate with the systems' responses to external thermodynamic conditions. Moreover, it is probabilistic, thus offering a way to assign a probability to every configuration of becoming stabilisable by application of a given thermodynamic constraint, rather than classifying in a binary manner synthesisable and non-synthesisable phases. We first benchmark the predictive power of this scheme in a series of increasingly complex structure searches tasks, ranging from high-pressure hydrogen crystals to detection of molecular crystals stabilisation through chemical substitution. We then show how the probabilistic character of our proposed scheme increases the robustness of the convex hull constructions to differences in the choice of potential energy surfaces and atomistic description of the system. Finally, we show the results of a fully explorative search on the phase diagram of ice. The GCH constructions re-discovers all the known 17 phases included in the set and further proposes a set of candidates for meta-stability. To test the novel phases stability range we analyse their enthalpies at various pressures, finding regimes where novel candidates appear to be favourable over the already known phases. The results presented in this thesis show that the GCH can effectively enhance structure searches schemes with a robust and far-sighted probe for potentially synthesisable configuration.