Acquisition time is a major limitation in recovering brain microstructure with diffusion Magnetic Resonance Imaging. Finding a sampling scheme that maximizes signal quality and satisfies given time constraints is NP-hard. We alleviate that by introducing a relaxed probabilistic model of the problem, for which nearly-optimal solutions can be found effectively. Our model is defined in the qt-space, so that it captures both spacial and temporal phenomena. The experiments on in-vivo diffusion images of the C57Bl6 wild-type mice reveal superiority of our technique over random sampling and even distribution in the qt-space.