We focus on feature selection algorithms that extract minimal subsets of features relevant to class labels from categorical data with high dimensional feature space. Filter-based feature selection consists of two important components; consistency measures between feature sets and class labels, and search strategies for minimal feature sets . Through theoretical and empirical analysis on these two components, we designed and implemented a very fast feature selection algorithm with high accuracy and scalability. We applied this algorithm to two applications; topic extraction from tweets, and pattern acquisition from graph-structured data.