English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Distributed processing frameworks, such as MapReduce, Hadoop, and Spark arepopular systems for processing large amounts of data. The design of efficientalgorithms in these frameworks is a challenging problem, as the systems bothrequire parallelism---since datasets are so large that multiple machines arenecessary---and limit the degree of parallelism---since the number of machinesgrows sublinearly in the size of the data. Although MapReduce is over a dozenyears old~\cite{dean2008mapreduce}, many fundamental problems, such as MatrixMultiplication, 3-SUM, and All Pairs Shortest Paths,  lack efficient MapReduce algorithms. We study these problems in the MapReducesetting. Our main contribution is to exhibit smooth trade-offs between thememory available on each machine, and the total number of machines necessaryfor each problem. Overall, we take the memory available to each machine as aparameter, and aim to minimize the number of rounds and number of machines.  In this paper, we build on the well-known MapReduce theoretical frameworkinitiated by Karloff, Suri, and Vassilvitskii ~\cite{karloff2010model} and givealgorithms for many of these problems. The key to efficient algorithms in thissetting lies in defining a sublinear number of large (polynomially sized)subproblems, that can then be solved in parallel. We give strategies forMapReduce-friendly partitioning, that result in new algorithms for all of theabove problems. Specifically, we give constant round algorithms for theOrthogonal Vector (OV) and 3-SUM problems, and $O(\log n)$-round algorithms forMatrix Multiplication, All Pairs Shortest Paths (APSP), and Fast FourierTransform (FFT), among others. In all of these we exhibit trade-offs betweenthe number of machines and memory per machine.

MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond