Accelerating Metric Space Similarity Joins with Multi-core and Many-core Processors

摘要

The similarity join finds all pairs of similar objects in a large collection. This search problem could be successfully divided into many sub-problems by an algorithm called Quickjoin recently. Besides, this algorithm could be extended to a wide range of application areas as it is based on metric spaces instead of vector spaces only. When the volume of a dataset reaches to a certain degree or the distance measure of the similarity is complex enough, however, Quickjoin still takes much time to accomplish the similarity join task, which leads us to develop a parallel version of the algorithm. In this paper, we present two parallel versions of the Quickjoin algorithm exploiting multi-core and many-core processors respectively as well as evaluate them. Experiments show that the parallelization of this algorithm in our many-core processor yields speedup to 22 at most compared with its non-parallel version.