A Content-Addressable Network for Similarity Join in Metric Spaces ∗

Similarity join is an interesting complement of the well-established similarity range and nearest neighbors search primitives in metric spaces. However, the quadratic computational complexity of sim-ilarity join prevents from applications on large data col-lections. We present MCAN+, an extension of MCAN (a Content-Addressable Network for metric objects) to support similarity self join queries. The challenge of the proposed ap-proach is to address the problem of the intrinsic quadratic complexity of similarity joins, with the aim of limiting the elaboration time, by involving an increasing number of com-putational nodes as the dataset size grows. To test the scal-ability of MCAN+, we used a real-life dataset of color fea-tures extracted from one million images of the Flickr photo sharing website