Boosting the Efficiency in Similarity Search on Signature
C. Jong, Seon Wook Kim · 2013
Computing all signature pairs whose bit differences are less than or equal to a given threshold in large signature collections is an important problem in many applications. In this paper, we leverage MapReduce-based parallelization in order to enable scalable similarity search on the signatures. A road-block in using MapReduce framework in this problem, however, is that the cost of merging and sorting intermediate key-value pairs produced by multiple mappers can be prohibitively expensive when they do not fit into the main memory. Thus, in this paper, we propose S 4 igpart (Scalable Similarity Search on the Signatures), a novel MapReduce-based technique for computing similarity search over large signature collections. In particular, the approach presented in this paper relies on a data partitioning scheme which enables to avoid costly disk-based merge and sort operations. The experiment results show that the proposed technique, S 4 igpart, significantly improves the efficiency.