Chest radiographs are complex, heterogeneous medical images that depict many different types of tissues, and many different types of abnormalities. A radiologist develops a sense of what visual textures are typical for each anatomic region within chest radiographs by viewing a large set of "normal" radiographs over a period of years. As a result, an expert radiologist is able to readily detect atypical features. In our previous research, we modeled this type of learning by (1) collecting a large set of "normal" chest radiographs, (2) extracting local textural and contour features from anatomical regions within these radiographs, in the form of high-dimensional feature vectors, (3) using a distance-based transductive machine learning method to learn what it typical for each anatomical region, and (4) computing atypicality scores for the anatomical regions in test radiographs. That research demonstrated that the transductive One-Nearest-Neighbor (1NN) method was effective for identifying atypical regions in chest radiographs. However, the large set of training instances (and the need to compute a distance to each of these instances in a high dimensional space) made the transductive method computationally expensive. This paper discusses a novel online Variance Based Instance Selection (VBIS) method for use with the Nearest Neighbor classifier, that (1) substantially reduced the computational cost of the transductive 1NN method, while maintaining a high level of effectiveness in identifying regions of chest radiographs with atypical content, and (2) allowed the incremental incorporation of training data from new informative chest radiographs as they are encountered in day-to-day clinical work. © 2012 SPIE.