Often, big or imbalanced datasets are subject to undersampling in order to improve the overall accuracy of the underlying predictive model. In this paper, we study undersampling from the perspective of information content and propose and analyze a Monte-Carlo search methodology to obtain high quality, low redundancy data subsets from large datasets. Our strategy is to transform the data redundancy structure into a graph theoretic format and assign importance to each data point in terms of vertex degrees. We then extract low redundancy data points via iteration, allowing for random exploration in the intermediate steps. Our simulation results indicate that if the redundancy graph is sufficiently sparse, then there is a non-trivial exploration probability that maximizes the quality of the final dataset. We illustrate our methodologies using the zoo animal dataset available in Kaggle and also discuss theoretical questions for potential future research, regarding the properties of the optimal exploration probability.