Quantum Monte Carlo (QMC) simulations constitute nowadays one of the most powerful methods to study strongly correlated quantum systems, provided that no" sign problem" arises. However, many systems of interest, including highly frustrated magnets, suffer from an average sign that is close to zero in standard QMC simulations. Nevertheless, a possible sign problem depends on the simulation basis, and here we demonstrate how a suitable choice of cluster basis can be used to eliminate or at least reduce the sign problem in highly frustrated magnets that were so far inaccessible to efficient QMC simulations. We focus in particular on the application of a two-spin (dimer)-based QMC method to the thermodynamics of the spin-1/2 Shastry-Sutherland model for SrCu 2 (BO 3) 2.