  A common form of MapReduce application involves discovering relationships
between certain pairs of inputs. Similarity joins serve as a good example of
this type of problem, which we call a "some-pairs" problem. In the framework of
Afrati et al. (VLDB 2013), algorithms are measured by the tradeoff between
reducer size (maximum number of inputs a reducer can handle) and the
replication rate (average number of reducers to which an input must be sent.
There are two obvious approaches to solving some-pairs problems in general. We
show that no general-purpose MapReduce algorithm can beat both of these two
algorithms in the worst case. We then explore a recursive algorithm for solving
some-pairs problems and heuristics for beating the lower bound on common
instances of the some-pairs class of problems.
