On measuring the distance between histograms

A distance measure between two histograms has applications in feature selection, image indexing and retrieval, pattern classification and clustering, etc. We propose a distance between sets of measurement values as a measure of dissimilarity of two histograms. The proposed measure has the advantage over the traditional distance measures regarding the overlap between two distributions; it takes the similarity of the non-overlapping parts into account as well as that of overlapping parts. We consider three versions of the univariate histogram, corresponding to whether the type of measurement is nominal, ordinal, and modulo and their computational time complexities are Θ(b), Θ(b) and O(b²) for each type of measurements, respectively, where b is the number of levels in histograms.