4 ms·

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

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.

t1m 13y ago
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 :-)
- dekhn 13y ago
  There's another important dimension: the fan-out factor when a person with many followers tweets.
- cdavid 13y ago
  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.
NathanRice 13y ago
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.
- pnathan 13y ago
  Here's an interesting probabilistic way to sample up to the median: http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-day-frugal-streaming/ http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-...
im3w1l 13y ago
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 http://en.wikipedia.org/wiki/Quickselect

t1m 13y ago

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 :-)

dekhn 13y ago
There's another important dimension: the fan-out factor when a person with many followers tweets.
cdavid 13y ago
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.

NathanRice 13y ago

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.

pnathan 13y ago
Here's an interesting probabilistic way to sample up to the median: http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-day-frugal-streaming/ http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-...

im3w1l 13y ago

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 http://en.wikipedia.org/wiki/Quickselect