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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-05-17

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

Highlights - Most important sentences from the article

2019-02-23

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

Highlights - Most important sentences from the article

2018-07-16

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

Highlights - Most important sentences from the article

2019-01-07

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

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
PDF

Highlights - Most important sentences from the article

2018-06-16

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

Highlights - Most important sentences from the article

2015-04-27

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

Highlights - Most important sentences from the article

2018-09-18

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

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
PDF

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
PDF

Highlights - Most important sentences from the article

2017-02-21

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

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
PDF

Highlights - Most important sentences from the article

2018-07-18

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

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
PDF

Highlights - Most important sentences from the article

2018-08-15

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

Highlights - Most important sentences from the article