This paper presents a number of new algorithms for discovering the Markov Blanket of a target variable T, denoted as MB(T), from training data. The MB(T) can be used both for variable selection for classification, for causal discovery, and for Bayesian Network learning. We introduce a low-order polynomial algorithm and several variants that soundly induce the MB(T) under certain broad conditions in datasets with thousands of variables and compare them to other state-of-the-art local and global methods with excellent results.