An appearance-based approach for visual mapping and localization is proposed in this paper. On the one hand, a new image similarity measure between images based on number of matchings and their associated distances is introduced. On the other hand, to optimize running times, matchings between the current image and previous visited places are determined using an index based on a set of randomized KD-trees. Further, a discrete Bayes filter is used for predicting loop candidates, taking into account the previous relationships between visual locations. The approach has been validated using image sequences from several environments. Whereas most other approaches use omnidirectional cameras, a single-view configuration has been selected for our experiments.