Abstract Consistency-based feature selection is an important category of feature selection research yet is de?ned only intuitively in the literature. First, we formally de?ne a consistency measure, and then using this de?nition, evaluate 19 feature selection measures from the literature. While only 5 of these were labeled as consistency measures by their original authors, by our de?nition, an additional 9 measures should be classi?ed as consistency measures. To compare these 14 consistency measures in terms of sensitivity, we introduce the concept of quasilinear compatibility order, and partially determine the order among the measures. Next, we propose a new fast algorithm for consistency-based feature selection. We ran experiments using eleven large datasets to compare the performance of our algorithm against INTERACT and LCC, the only two instances of consistency-based algorithms with potential real world application. Our algorithm shows vast improvement in time ef?ciency, while its performance in accuracy is comparable with that of INTERACT and LCC.