Signatures versus histograms: Definitions, distances and algorithms

The aim of this paper is to present a new method to compare histograms. The main advantage is that there is an important time-complexity reduction with respect to the methods presented before. This reduction is statistically and analytically demonstrated in the paper.The distances between histograms that we presented are defined on a structure called signature, which is a lossless representation of histograms. Moreover, the type of the elements of the sets that the histograms represent are ordinal, nominal and modulo.We show that the computational cost of these distances is O(z′)O(z′) for the ordinal and nominal types and O(z′2)O(z′2)