{"id":706,"date":"2008-11-24T16:25:59","date_gmt":"2008-11-24T16:25:59","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/11\/24\/scale-how-large-quantities-of-information-change-everything\/"},"modified":"2008-11-24T16:25:59","modified_gmt":"2008-11-24T16:25:59","slug":"scale-how-large-quantities-of-information-change-everything","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/11\/24\/scale-how-large-quantities-of-information-change-everything\/","title":{"rendered":"Scale: How Large Quantities of Information Change Everything"},"content":{"rendered":"

Technorati Tags: scale<\/a>, computation<\/a>, information<\/a><\/span><\/p>\n

Since people know I work for Google, I get lots of mail from folks with odd questions, or with complaints about some Google policy, or questions about the way that Google does some particular thing. Obviously, I can’t answer questions about Google. And even if I could, I wouldn’t. This isn’t a Google blog; this is my blog, which I write as a hobby in my free time.<\/p>\n

But there are intersections between my work life and my hobby. And one of the ideas that underlies many of the questions that I receive, and which also
\nhits on my work, and my hobby. And that’s the idea of scale<\/em>. Scale is computer-science talk for how things change as they get bigger. In particular, I’m talking about the scale of information; the amount of information that we use on a daily basis has increased dramatically, and the amount of dramatic, fundamental change that has resulted is both amazing, and amazingly unnoticed by most people.<\/p>\n

<\/p>\n

What’s scale?<\/p>\n

Take a bunch of information, and think about how you would analyze it. Suppose you have a list of, say, music tracks. On my computer, I’ve got 4,426 tracks of music. Now, suppose I wanted to go through those tracks, and summarize what’s there. If all you want to look at is simple information – the name of the track, the artist, the length, the genre, etc., it’s trivial. You could do it in seconds on any modern computer. Heck, you could do it in seconds on any modern cellphone<\/em>.<\/p>\n

Now, suppose that instead of 4,000 tracks, it were 4 million. That’s still
\nnot a big deal. I can still do all sorts of interesting analysis of 4 million
\nrecords in minutes. With a modern computer, it’s no big deal.<\/p>\n

But what if I wanted to do something more interesting, like look at the files and try to compute the tempo? Now instead of dealing with four million sets of strings, I’d need to actually look at the full content of the songs, to compute the tempo. OnIn my mumic collection, the average track seems to take up a couple of megabytes; let’s say it’s just one megabyte per song. To analyze a library of 4,000 songs at one megabyte each is doable on a modern PC, but it’s going to take a while. To do it to a library of 4 million<\/em> tracks is simply not feasible. I can buy a disk for my computer large enough to store that many tracks, but there’s no way that I’d ever be able to run an interesting sonic analysis and finish it.<\/p>\n

Services with music databases like LastFM, Pandora, and iTunes maintain
\ninformation on tens of millions of tracks, and many of us play with those
\nevery day without ever thinking about what’s going on. LastFM and Pandora
\nanalyze millions of tracks of music, so that when you tell it what you like, it
\ncan suggest similar things based on the musical structure. Ten years ago, having a computer do that would have been impossible. Today it’s routine.<\/p>\n

That’s scale – the way that things change as you increase the size of the problem.
\nThings get bigger and bigger, and eventually the size of the problem crosses a line so that the increase in size fundamentally changes the problem.<\/p>\n

Again, let me try to put the idea of quantities of data into some kind of terms
\nthat intuitively give you an idea. I bought my first computer in 1982. It was a
\nFranklin Ace 1000 – and Apple II clone. It had a floppy disk drive, which stored
\n140,000 bytes on a 5 1\/4 inch floppy disk. My next computer was a big step up – an
\nAmiga, which stored around 800,000 bytes on a 3 1\/2 inche disk drive. Today, my
\ncellphone<\/em> has a removable flash drive which can store 8,000,000,000 bytes, on
\na little tiny card about 1\/4 inch on a side, and about the thickness of a greeting
\ncard. If I were to convert the storage on my cellphone to floppy disks on my old Apple
\nclone, it would require about 57,000 disks. That would be a stack of floppy disks
\nalmost 500 feet high. <\/p>\n

We’re routinely carrying around quantities of data that we simply don’t have
\nthe ability to intuitively understand. A gigabyte is a billion<\/em> letters. What does that mean<\/em>? We just don’t think about it. The closest we come is
\nto break it down some other way; instead of calling it a billion characters, we’ll call it a hundred songs. But the availability of that quantity of data has dramatically changed the way we work, and the things we can do. I used to
\nhave a little briefcase full of cassettes for my car stereo. I carried this stupid thing around, with 100 little plastic cassettes in it, just to have a decent selection of music to listen to. Now I’ve got 887 tracks on my Android, and I complain<\/em> about how I don’t have enough space for a decent selection! That’s scale – the
\namount of data I can afford to carry with me has changed dramatically, and as a result, my expectations about what’s normal have changed.<\/p>\n

The effects of scale are very counter-intuitive. By making the problem bigger,
\nin some cases, you make it easier<\/em>. There are things that you can do
\neasily<\/em> with data at massive scale that you couldn’t do at all with
\nsmall quantities of data; and there are things that you can easily do with small amounts of data that become impossible when you scale upwards.<\/p>\n

We’ll start with the upside. Scale means that you can do some amazing things
\nthat used to be impossible. For example, scale means that you can record the entire genomes of large numbers of organisms. Last week, my fellow ScienceBlogger Tara Smith at Aetiology<\/a> wrote an article about a recent Ebola outbreak; doctors studying the outbreak wanted to see what strain of Ebola they were dealing with, so they sequenced it, and compared it to the existing library of Ebola genomes, and identified it as a new strain, but related to one of the known strains. Scientists now now routinely<\/em> sequence the genes new infectious diseases, and compare them with a range of known variants. In fact, they do more than that; to quote one website
\ndiscussing this<\/a>:<\/p>\n

\n“Due to the explosive growth of the field of Genomics, several
\ndatabases containing fully sequenced genomes of many viruses have been created and
\nplaced online for easy access. By taking the newly sequenced Ebola genome data,
\nscientists were able to compare its composition to that of other viruses. When the
\ntranslated genome of the Ebola virus and its respective subtypes was compared to that
\nof other viruses, something of particular interest stood out. There was an almost
\nidentical match between the immunosuppressive motifs of the oncogenic retroviruses,
\nmurine leukemia virus (MuLV) and feline leukemia virus (FeLV) and a region of the
\nEbola genome.”\n<\/p><\/blockquote>\n

To translate that into simpler terms: they didn’t just compare the genome of the new Ebola variant to other Ebola viruses; that wouldn’t be particularly difficult, since the Ebola genome is only about 19K of data. But they compared it to the sequenced genomes of every previously sequenced virus<\/em>, and found nearly identical sequences in Ebola and feline leukemia virus!<\/p>\n

That’s the good side of scale. Things that we wouldn’t have imagined just a few years ago are not just possible, but they’re downright routine – because carrying
\naround and manipulating massive quantities of data is now routine. Scientists now casually work with massive quantities of information, and by doing that, they’re finding completely new ways of doing science. Ten years ago, if they could have gotten state of the art equipment, the scientists looking at the Ebola genome could probably have sequenced it. But they would never have dreamt<\/em> of comparing it to feline leukemia virus. But with the scale at which we can now work, it’s harder to exclude<\/em> some probably irrelevant virus than it is to go ahead and compare it, just on the incredible off-chance that there might be something there. <\/p>\n

In some ways, it’s almost like something out of Douglas Adams’ “Hitchhiker’s Guide
\nto the Galaxy” made real: we can now generate answers to questions that we didn’t even
\nask, and by there are answers laying in the data we have available for questions that
\nwe don’t even know. By searching for apparently meaningful patterns in large
\nquantities of data, we can find answers before we even know what the questions are.
\n(Of course, just like in HHGtG, we still need to figure out what the question is.)
\nScale has dramatically changed science: we can routinely look for things and discover
\ncorrelations that we don’t expect, which opens up whole new questions that we never
\nthought of before.<\/p>\n

That’s the happy side of scale: the ability to mine huge quantities of data means
\nthat we can look at things and discover things in a whole new way. But there’s also
\na downside: there are things that would be easy for small-scale data that becomes unmanageable on a large scale.<\/p>\n

In computer science, we’ve traditionally drawn a line between things that are really computable, and things that while theoretically computable, simply take too long on any real computer to be doable. We’ve drawn that line in terms of something called algorithmic complexity. The line has traditionally been that anything whose
\ncomplexity can be bounded by some polynomial computed from the size of its input is computable, while anything whose complexity is bounded by some exponential in the size of its input is not<\/em>. But scale changes that. When you’re working with large
\nscale data, polynomial complexity is not really doable. Even if you’ve got something
\nwhich grows very slowly, like sorting, becomes close to impossible at scale.<\/p>\n

A great example of how even people who deal with massive quantities of data
\nhaven’t really grasped what a deep fundamental change we’re seeing in the scale of
\nthings comes from the database world. A while ago, a database magazine published an
\narticle critiquing Google’s MapReduce for not being sufficiently
\nrelational-database-like. I wrote a
\npost<\/a> responding to it, explaining why that’s wrong. I still get mail about that
\nold post from database folks who think that the stuff that’s typically done by
\nMapReduce should be done by relational databases.<\/p>\n

Databases were designed to deal with what were (at the time) considered massive
\nquantities of data. And as database people keep reminding me, modern databases support clustering – meaning using multiple computers in parallel to make things faster – just like Google, so that they’re more scalable than I give them credit for.<\/p>\n

BUt there’s massive, and then there’s massive<\/em>. Databases are great
\nat handling large quantities of data. But there are collections of data that are simply too large<\/em> for current database technology. And much of the reason
\nfor that isn’t just because databases haven’t been designed to work with network-scale datasets, but because many of the fundamental database algorithms and representations simply don’t work on the massive scale.<\/p>\n

It’s easiest to explain this through an example. This past weekend, a team
\nat Google<\/a> (a team which I have no connection<\/em> to; I know no one involved in
\nthe task) announced the results of trying to sort one petabyte<\/em> of data,
\nstored in 10 trillion<\/em> 100-byte records. Doing this required 4,000<\/em>
\ncomputers and 48,000<\/em> hard drives working together for just over six hours.<\/p>\n

When database people talk about clustering, they’re usually talking about up to a
\ndozen or so machines. (I just did a quick search of IBM’s DB information on the web,
\nand couldn’t find any reference to using more than 12 CPUs.)<\/p>\n

There’s a big difference between dealing with 12 CPUs and gigabytes of data, and
\n4,000 CPUs and a petabyte of data stored on 48,000 disk drives! Modern large scale
\nsystems are increasingly more like the petabyte scale of large map-reduce than the
\ngigabyte scale of databases. According to the post about the petabyte sort results,
\nGoogle routinely processes 20 petabytes<\/em> of data every single day. I’m sure
\nthat other large internet companies are seeing similar quantities of data. Both Yahoo and Microsoft are certainly maintaining search indices that have to be in that
\nrough size range; ISPs need to log traffic information for millions of users;
\ncellphone companies must be recieving billions of data packets per hour providing them
\nwith location information about cellphones; and so on. And it’s not just
\ninternet companies: maintaining genomic data on thousands of human beings (which is
\nsomething medical researchers want to do); or maintaining infection disease tracking
\ninformation for large populations; or even managing auctions and bids on eBay all involve storing<\/p>\n

That’s scale, and that’s downright scary<\/em>. Just sorting<\/em> one
\n20th of the data processed by Google every day takes a team of brilliant engineers
\nto figure out how to do it<\/em>, and the result requires tens of thousands of computers and hundreds of thousands of disks!<\/p>\n

Imagine how many computers it must take to encrypt<\/em> all of that information! Companies like Google, Yahoo, Amazon, and Ebay are recieving millions
\nto billions of requests per day, and they’re not storing the information about those requests in text files that any bozo can read. Just think about what it means to
\nencrypt 20 petabytes of data per day.<\/p>\n

There’s another important downside to scale. When we look at large quantities of information, what we’re really doing is searching for patterns. And being the kind of creatures that we are, and given the nature of the laws of probability, we are<\/em> going to find patterns. Distinguishing between a real legitimate
\npattern, and something random that just happens to look like a pattern can be somewhere between difficult and impossible. Using things like Bayesian methods
\nto screen out the false positives can help, but scale means that scientists need to learn new methods – both the new ways of doing things that they couldn’t do before, and the new ways of recognizing when they’ve screwed up.<\/p>\n

There’s the nature of scale. Tasks that were once simple have become hard
\nor even impossible, because they can’t be done at scale. Tasks that were once
\nimpossible have become easy because scale makes them possible. Scale
\nchanges everything.<\/p>\n","protected":false},"excerpt":{"rendered":"

Technorati Tags: scale, computation, information Since people know I work for Google, I get lots of mail from folks with odd questions, or with complaints about some Google policy, or questions about the way that Google does some particular thing. Obviously, I can’t answer questions about Google. And even if I could, I wouldn’t. This […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[79],"tags":[],"class_list":["post-706","post","type-post","status-publish","format-standard","hentry","category-computation"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bo","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/706","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=706"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/706\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=706"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=706"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=706"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}