“Big Data” has been hyped a lot, and due to this now is burning down to get some reality checking. It’s been already overdue, but it is now happening.

I have seen a lot of people be very excited about NoSQL databases; and these databases do have their use cases. However, you just cannot put everything into NoSQL mode and expect it to just work. That is why we have recently seen NewSQL databases, query languages for NoSQL databases etc. - and in fact, they all move towards relational database management again.

Sound new database systems seem to be mostly made up of three aspects: in-memory optimization instead of optimizing for on-disk operation (memory just has become a lot cheaper the last 10 years), the execution of queries on the servers that store the actual data (you may want to call this “stored procedures” if you like SQL, or “map-reduce” if you like buzzwords), and optimized memory layouts (many of the benefits of “colum store” databases come from having a single, often primitive, datatype for the full column to scan, instead of alternating datatypes in records.

However, here is one point you need to consider:
is your data actually this “big”? Big as in: Google scale.

I see people use big data and Hadoop a lot when they just shouldn’t. I see a lot of people run Hadoop in a VM on their laptop. Ouch.

The big data technologies are not a one-size-fits-all solution. They are the supersize-me solution, and supersize just does not fit every task.

When you look at the cases where Hadoop is really successful, it is mostly in keeping the original raw data, and enabling people to re-scan the full data again when e.g. their requirements changed. This is where Hadoop is really good at: managing 100 TB of data, and allowing you to quickly filter out the few GB that you really need for your current task.

For the actual analysis - or when you don’t have 100 TB, and a large cluster anyway - then just don’t try to hadoopify everything.

Here is a raw number from a current experiment. I have a student work on indexing image data; he is implementing some state of the art techniques. For these, a large number of image features are extracted, and then clustering is used to find “typical” features to improve image search.

The benchmarking image set is 56 GB (I have others with 2 TB to use next). The subset the student is currently processing is 13 GB. Extracting 2.3 million 128 dimensional feature vectors reduces this to about 1.4 GB. As you can see, the numbers drop quickly.

State of the art seems to be to load the data into Hadoop, and run clustering (actually, this is more of a vector quantization than clustering) into 1000 groups. Mahout is the obvious candidate to run this on Hadoop.

However, as I’ve put a lot of effort into the data mining software ELKI, I considered also to try processing it in ELKI.

By cutting the data into 10 MB blocks, Mahout/Hadoop can run the clustering in 52x parallel mappers. k-Means is an iterative algorithm, so it needs multiple processes. I have fixed the number of iterations to 10, which should produce a good enough approximation for my use cases.

K-means is embarrassingly parallel, so one would expect the cluster to really shine at this task. Well, here are some numbers:

  • Mahout k-Means took 51 minutes on average per iteration (The raw numbers are 38:24, 62:29, 46:21, 56:20, 52:15, 45:11, 57:12, 44:58, 52:01, 50:26, so you can see there is a surpisingly high amount of variance there).
  • ELKI k-Means on a single CPU core took 4 minutes 25 seconds per iteration, and 45 minutes total, including parsing the input data from an ascii file. Maybe I will try a parallel implementation next.

So what is happening? Why is ELKI beating Mahout by a factor of 10x?

It’s (as always) a mixture of a number of things:

  • ELKI is quite well optimized. The Java Hotspot VM does a good job at optimizing this code, and I have seen it to be on par with R’s k-means, which is written in C. I’m not sure if Mahout has received a similar amount of optimization yet. (In fact, 15% of the Mahout runtime was garbage collection runtime - indicating that it creates too many objects.)
  • ELKI can use the data in a uniform way, similar to a column store database. It’s literally crunching the raw double[] arrays. Mahout on the other hand - as far as I can tell - is getting the data from a sequence file, which then is deserialized into a complex object. In addition to the actual data, it might be expecting sparse and dense vectors mixed etc.
  • Size: this data set fits well into memory. Once this no longer holds, ELKI will no longer be an option. Then MapReduce/Hadoop/Mahout wins. In particular, such an implementation will by design not keep the whole data set in memory, but need to de-serialize it from disk again on each iteration. This is overhead, but saves memory.
  • Design: MapReduce is designed for huge clusters, where you must expect nodes to crash during your computation. Well, chances are that my computer will survive 45 minutes, so I do not need this for this data size. However, when you really have large data, and need multiple hours on 1000 nodes to process it, then this becomes important to survive losing a node. The cost is that all interim results are written to the distributed filesystem. This extra I/O comes, again, at a cost.

Let me emphasize this: I’m not saying, Hadoop/Mahout is bad. I’m saying: this data set is not big enough to make Mahout beneficial.

Conclusions: As long as your data fits into your main memory and takes just a few hours to compute, don’t go for Hadoop.
It will likely be faster on a single node by avoiding the overhead associated with (current) distributed implementations.

Sometimes, it may also be a solution to use the cluster only for preparing the data, then get it to a powerful workstation, and analyze it there. We did do this with the images: for extracting the image features, we used a distributed implementation (not on Hadoop, but on a dozen PCs).

I’m not saying it will stay that way. I have plans for starting “Project HELKI”, aka “ELKI on Hadoop”. Because I do sometimes hit the barrier of what I can compute on my 8 core CPU in an “reasonable” amount of time. And of course, Mahout will improve over time, and hopefully lose some of its “Java boxing” weight.

But before trying to run everything on a cluster, always try to run it on a single node first. You can still figure out how to scale up later, once you really know what you need.

And last but not least, consider whether scaling up really makes sense. K-means results don’t really get better with a larger data set. They are averages, and adding more data will likely only change the last few digits. Now if you have an implementation that doesn’t pay attention to numerical issues, you might end up with more numerical error than you gained from that extra data.

In fact, k-means can effectively be accelerated by processing a sample first, and only refining this on the full data set then. And: sampling is the most important “big data” approach. In particular when using statistical methods, consider whether more data can really be expected to improve your quality.

Better algorithms: K-means is a very crude heuristic. It optimizes the sum of squared deviations, which may be not too meaningful for your problem. It is not very noise tolerant, either. And there are thousands of variants. For example bisecting k-means, which no longer is embarrassingly parallel (i.e. it is not as easy to implement on MapReduce), but took just 7 minutes doing 20 iterations for each split. The algorithm can be summarized as starting with k=2, then always splitting the largest cluster in two until you have the desired k. For many use cases, this result will be just as good as the full k-means result.

Don’t get me wrong. There are true big data problems. Web scale search, for example. Or product and friend recommendations at Facebook scale. But chances are that you don’t have this amount of data. Google probably doesn’t employ k-means at that scale either. (actually, Google runs k-means on 5 mio keypoints for vector quantization; which, judging my experience here, can still be done one a single host; in particular with hierarchical approaches such as bisecting k-means)

Don’t choose the wrong tool for the wrong problem!