Hadoop for super O(N) or O(N log N) algorithms?

Question

Is there any documented case of Hadoop working for any algorithm that's more than approximately linear? Or does huge data sets pretty much mean that anything above linear is unacceptable?

I'm trying to find algorithms that run on Hadoop that to more complicated things than just sorting/agregrating.

Thanks!

Answer 1

Have you had a look at the Apache Mahout Project? They're implementing machine learning algorithms using Hadoop (most of the algorithms do anyway).

The algorithms they're working on are listed on their wiki here.

Answer 2

Here is an overview of ~50 papers describing algorithms with mapreduce (hadoop): http://atbrox.com/2010/02/12/mapreduce-hadoop-algorithms-in-academic-papers-updated/ Some of the algorithms categorized under statistics there have running time O(N^2)