### Some Pairs Problems

**2016-02-03**

1602.01443 | cs.DB

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-01-20**

1901.06740 | cs.IT

Group testing is a well-known search problem that consists in detecting of
$s$ defective members of … show more

**2019-05-17**

1905.07342 | stat.ML

The pair-matching problem appears in many applications where one wants to
discover good matches betw… show more

**2019-02-23**

1902.08723 | cs.CC

A central problem in parameterized algorithms is to obtain algorithms
with running time $f(k)\cdot… show more

**2018-07-16**

1807.05803 | cs.DS

The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a
minimum $s$-$t$ cut (or jus… show more

**2019-01-07**

1901.01630 | cs.DC

This paper proves strong lower bounds for distributed computing in the
CONGEST model, by presenting … show more

**2018-02-18**

1802.06440 | cs.DS

One of the most fundamental problems in Computer Science is the Knapsack
problem. Given a set of n i… show more

**2018-06-16**

1806.06223 | cs.DS

The priority model of "greedy-like" algorithms was introduced by Borodin,
Nielsen, and Rackoff in 20… show more

**2015-04-27**

1504.07056 | cs.DC

We present a deterministic $(1+o(1))$-approximation
$(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for s… show more

**2018-09-18**

1809.06950 | math.CO

Consider algorithms with unbounded computation time that probe the entries of
the adjacency matrix o… show more

**2019-03-28**

1903.12050 | math.CO

We consider a variant of the planted clique problem where we are allowed
unbounded computational tim… show more

**2019-02-26**

1902.09958 | cs.DC

Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed
Lov\'asz Local Lemma, whi… show more

**2017-02-21**

1702.06548 | cs.DS

The task of listing all triangles in an undirected graph is a fundamental
graph primitive with numer… show more

**2019-02-21**

1902.08299 | cs.CC

This chapter provides a hands-on tutorial on the important technique known as
self-reducibility. Thr… show more

**2018-07-18**

1807.06933 | cs.CG

We study exact algorithms for {\sc Euclidean TSP} in $\mathbb{R}^d$. In the
early 1990s algorithms w… show more

**2018-12-07**

1812.03155 | cs.DS

Kernelization algorithms are polynomial-time reductions from a problem to
itself that guarantee thei… show more

**2018-08-15**

1808.04995 | cs.DS

Subgraph counting is a fundamental primitive in graph processing, with
applications in social networ… show more