On Asymmetric Similarity Search

Similarity, and the strongly related inverse concept of distance, plays an important role in many data mining techniques. Typically, the definitions of similarity/distance measures are restricted to being symmetric. In this paper, however, we consider asymmetric measures and show that there are justifiable reasons in many domains for preferring asymmetric measures. Our review of the literature indicates that these ideas have occasionally been considered in various guises, but not formalized. In this context, we use our proposed Contains concept to represent an asymmetric relation. We show how asymmetry can be introduced into some widely used binary similarity/distance measures and evaluate their performance on data sets from multiple domains. The results show that asymmetric Contains measures can yield better performance, and are never worse than the corresponding symmetric measures.