ML p(r)ior | Some Pairs Problems

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2019-01-07 1901.01630 | cs.DC This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting … show more Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2018-09-18 1809.06950 | math.CO Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix o… show more Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

2018-12-07
1812.03155 | cs.DS

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

Highlights - Most important sentences from the article

2018-08-15
1808.04995 | cs.DS

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

Highlights - Most important sentences from the article