9
$\begingroup$

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial.

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ There is no way to measure asymptotics. Are you interested in benchmarks or formal analysis? The latter is tough in parallel settings, and depends on your exact machine model. Chances are, if you assume a model that you can handle during analysis, the results won't tell you much in practice. $\endgroup$
    – Raphael ♦
    May 7, 2015 at 7:26
  • 2
    $\begingroup$ That said, this question may be relevant. $\endgroup$
    – Raphael ♦
    May 7, 2015 at 7:28
  • 1
    $\begingroup$ Have you seen Mining of Massive Datasets? Sections 2.5 and 2.6 talk about minimizing communication (I/O) costs and not compute time which is usually the real bottle neck in Hadoop $\endgroup$
    – Eric Farng
    May 7, 2015 at 13:14
  • $\begingroup$ In the papers I've read you don't really analyse the time complexity. You count the number of rounds and the amount of data you need to process in each round (the communication complexity). Shuffling the data through the network is typically the bottleneck in map-reduce. $\endgroup$
    – adrianN
    Dec 28, 2016 at 9:15

2 Answers 2

Reset to default
1
$\begingroup$

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

Improve this answer
$\endgroup$
-2
$\begingroup$

See you are right but you know its quite hard to say a specific time complexity of map reducing. It depends upon the query. But in that case it should be o(nlogn/k)+c+c' because of k nodes. These all shorts of queries including a mapping phase of a map reducing texhnique follows a Btree concept.So from that place for inner computations we may say that its time complexity > o(nlogn)+c+c'.

Correct my suggestions please.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Welcome to the site! When you say "correct my suggestions, please", that suggests you're not very confident in your answer, which makes it sound more like a guess than an actual answer. Obviously, any answer could be wrong but we do hope that the person who wrote the answer believes it to be correct! $\endgroup$
    – David Richerby
    Oct 29, 2016 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.