Comment by mrcactu5 | Hacker News Reader

Comment by mrcactu5 | Hacker News Reader

Parent Full thread

I remember starting to grasp what "big data" meant when I had a phone interview with Twitter.

@ Imagine you have some numbers spread over some computers -- too many to fit in one computer find the median.

▪ Uhh, sort them?

@ Can you find the median on a single computer without sorting them.

▪ :-(

@ We'll call you back tomorrow.

I was promptly rejected, but it set the tone for my later studies.

The criterion for Big Data seems to be that it fits on thousands of computers, perhaps several TB or a PB. Then I had to think of some examples:

* A million YouTube Videos

* All the tweets in the US in the past 15 minutes

* All US tax records

I still think the map-reduce philosophy is really cool. And I know at that scale there are special counting algorithms (like Bloom Filters) that may lead to some improvements at the GB or MB scales.

For reference, finding the median is an O(n) problem on a single computer, and sorting is an O(n log n) solution.

An O(n) algorithm is Quick select. It is basically like quick sort but you only recurse on the side of the pivot that contains the median.

http://en.wikipedia.org/wiki/Quickselect

Twitter often gets singled out for it's big dataness, though the latest numbers I've seen are only about 400 million tweets per day. Even allowing 1K/tweet this is a rather manageable 400GB uncompressed.

15 minutes of US tweets would fit on your phone :-)

I am pretty sure a tweet is more than 1kb: the message itself is 140 characters, not 140 bytes, and you have lots of metadata around a tweet. I would expect easily one order of magnitude more / weet.

There's another important dimension: the fan-out factor when a person with many followers tweets.

That second question is kind of dirty. Pretty much all algorithms to find the median will perform a partial sort. Without any sorting at all, the only thing I can think of is some kind of statistical approximation based on sampling.

Here's an interesting probabilistic way to sample up to the median: http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-...

Reply on news.ycombinator.com