Thursday, December 06, 2012

Google and the right database for the job

I finally got a chance to read "Processing a Trillion Cells per Mouse Click", a paper out of Google presented at the recent VLDB 2012 conference.

It describes the rather cool PowerDrill column-oriented database at Google that is optimized for speed, x10-100 times faster than other column-oriented databases, and several orders of magnitude faster than MapReduce/Hadoop. But, of course, there are tradeoffs to get those speed gains, and the tradeoff PowerDrill makes is that it keeps a lot in memory, so it can only contain a fraction of the data of the other systems.

What is so interesting about this, and what other companies need to learn from this, is the way Google builds so many databases to analyze its massive log data. The goal is to let people find stuff in the logs as fast as possible. That means you need many tools, the right tool for the job.

Hadoop and similar systems allow you to scan massive amounts of log data but, c'mon, all of us know that the vast majority of Hadoop jobs ignore almost all of the data. Every one of these jobs starts by selecting out a couple of the columns, the same columns almost everyone else wants, and dropping everything else. Fire up your job, waste hours of time waiting for almost all the data from a full table scan to be thrown out, and finally you get the result.

Dremel and other column-oriented databases help a lot with this. If almost all log processing jobs only want a couple columns, a column-oriented database is designed to pull out just a few columns quickly, and it's going to be a lot faster.

PowerDrill goes a step further. If almost all log processing jobs only want the most recent logs and only a few of the columns, just create a database with only the most recent logs and a few of the columns. Add in a lot of carefully designed compression, sharding across a medium-sized cluster, and the ability to skip over much of the data when it isn't needed (instead of doing full table scans all the time), and you got yourself the ability to answer most questions people ask of the logs in seconds, not hours.

And that's the point. Build a system that can answer 90% of the questions people ask of the logs in seconds. Build another than can answer 90% of the remaining, harder questions people ask of the logs in minutes. Then have a system that primarily archives all the logs, but also can answer, given enough time and power, much more complicated questions people very rarely ask.

Those Google guys have many databases for asking questions of their logs. Maybe you should too.

Some excerpts from the PowerDrill paper:
The column-store developed as part of PowerDrill is tailored to support a few selected datasets and tuned for speed ... Our column-store relies on having as much data in memory as possible ... PowerDrill can run interactive single queries over more rows than Dremel, however the total amount of data it can serve is much smaller.

Consider a typical use case such as triggering 20 SQL queries with a single click in the UI. In our production system on average these queries process 782 billion cells in 30-40 seconds (under 2 seconds per query) .... Each month it is used by more than 800 users sending out about 4 million SQL queries ... scanning [the equivalent of] 525 trillion cells .... One of our top users ... [in] 6 hours ... [executed about] 12 thousand queries .... Our production system is running on well over 1000 machines, the distributed servers altogether using over 4T of main memory.

[PowerDrill] pushes the "interactivity limit" out significantly ... The majority of queries are fairly discriminative, similar, and uniform ... The store has only a few but often explored tables (as opposed to many tables that are not used very often) ... [For many common queries] our techniques push the limit of interactivity out by one or two orders of magnitude.

Saturday, December 01, 2012

Quick links

More of what caught my attention recently:
  • Android now has 72.4% of the mobile market, up from 52.5% a year ago ([1])

  • Google's new Nexus 4 smartphone is in high demand and for good reason: "The idea that a Nexus quad-core smartphone is hitting the market ... [at] $300 is simply stunning. Even more so is that it's available without any contract or carrier locks, which means you can use it virtually anywhere in the world. .. The price of freedom has never been more reasonable." ([1] [2] [3])

  • Google and Amazon aim to destroy Apple's high margin business model, selling hardware at cost and making money off content instead ([1])

  • "Amazon is a black hole threatening to devour corporate America" ([1])

  • "The ground is shifting beneath ... tech titans because of a major force: the rise of mobile devices" ([1])

  • Mobile/tablets are being used for about 16% of online sales, but sales from referrals out of Twitter and Facebook are near 0% ([1])

  • Google expects that 50% of traffic to will come from mobile in 2013. I wonder what that implies for Google, since it almost certainly does not mean 50% of revenue comes from mobile in 2013. ([1])

  • Google's latest Chromebook laptop and Nexus 7 tablet are both in high demand, and Google is "massively ramping production". Meanwhile, Microsoft is cutting production of its Surface hybrid tablet because of low demand. ([1] [2] [3])

  • Tablets mostly are used in the evening and for games and entertainment ([1] [2] [3])

  • Surprising data (at least to me) on browser market share, I thought IE was falling rapidly, but no. Data says IE is steady, Chrome growth is stalled, and Firefox is no longer falling, actually climbing slightly. ([1])

  • "Giving users the choice to view (or not view) may actually increase this advertising effectiveness" ([1])

  • Experimental data is poised to kill off a big chunk of the last three decades of work in theoretical physics ([1])

  • Good overview of current state of autonomous flying robots. Lots of breakthroughs recently. ([1])

  • "It's actually more natural for humans to think logarithmically than linearly" ([1])

  • If you don't need the actual location right away, it's three orders of magnitude cheaper (in energy use) to collect raw GPS data and process it later (in the cloud) than it is to process it immediately on the mobile device ([1])

  • Startups would love to get their hands on Google Fiber (especially the upload speeds) but can't. Cities should be thinking about encouraging Google Fiber (or similar) as a way to encourage startups. ([1])

  • Key question is: "Do patents, in fact, provide a net incentive for innovation in the software industry?" ([1])

  • Crazy data about the incredibly low cost of renting botnets, paying for someone to take out websites with DDoS attacks, sending spam, and buying various types of trojans ([1])

  • "We can't be afraid to let them actually take charge and ship" ([1])

  • "Only a handful of startups that are big successes. What happens along the way that causes such failure? It's like there's a tunnel full of monsters that kill them along the way. I'm going to tell you what these monsters are so you know to avoid them." ([1])

  • "By far the most common mistake startups make is to solve problems no one has" ([1])

  • Dilbert summarizes the advice from most business books ([1])

  • "People with lots of authority tend to behave like neurological patients with a damaged orbito-frontal lobe, a brain area that's crucial for empathy and decision-making" ([1])

  • "Studies of the human brain demonstrate that .... some people seem to think about their future selves in the same way that they think about complete strangers" ([1])

  • On why PC sales are flat: "Norvig's Law: Any technology that surpasses 50% penetration will never double again (in any number of months)." ([1])

  • "To the surprise of pundits, numbers continue to be best system for determining which of two things is larger" ([1])

Saturday, November 24, 2012

Code Maven and programming for teens

I recently launched Code Maven from Crunchzilla. It helps teens learn a little about what they can do if they learn more about programming.

A lot of teens are curious about programming these days, but don't end up doing any. And, it's true, if you are a teen who wants to learn programming, you either have to use tutorials, books, and classes made for adults (which have a heavy focus on syntax and are slow to let you do anything) or high level tools that let you build games but teach a specialized programming language you can't use anywhere else. Maybe something else might be useful to help more teens get started and get interested.

Code Maven lets teens learn a little about how to program, starting with basic concepts such as loops then rapidly getting into fractals, animation, physics, and games. In every lesson, all the code is there -- in some cases, a complete physics engine with gravity, frame rate, friction, and other code you can modify -- and it is all live Javascript, so the impact of any change is immediate. It's a fun way to explore what programming can do.

Code Maven is a curious blend of a game and a tutorial. Like a tutorial, it's step-by-step, and there's not-too-big, not-too-small challenges at each step. Like a game, it's fun, addictive, and experimentation can yield exciting (and often very cool) results. I hope you and your friends like it. Please try Code Maven, tell your friends about it, and, if you have suggestions or feedback, please e-mail me at

Code Maven builds on Code Monster. Code Monster is for kids ages 9-14 (but many even younger have enjoyed it too, especially with a little help). Code Maven is for teens ages 13-18 (and curious adults too, especially adults who have never programmed before). Because Code Maven is built for older kids, it assumes a longer attention span, and so is a bit harder, has more explanation, and has some additional fun projects. Pick which one you like based on the age of your kids and your interest. You can try them both at!

Friday, October 19, 2012

Quick links

What caught my attention recently:
  • The latest Google and Microsoft earnings show damage from a tech disruption, a shift to mobile that is impacting both badly but for different reasons. Google needs to crack mobile ads. Microsoft needs to get share in mobile computing. ([1] [2] [3] [4])

  • Now "there are almost as many mobile phone subscriptions in the world as people" ([1] [2] [3])

  • Google is getting aggressive, releasing a $99 tablet and a $250 laptop ([1] [2] [3] [4])

  • Amazon prices their tablet at cost ([1] [2])

  • And decent tablets in the $50 range are already widely available in China ([1])

  • But Microsoft prices its new tablet above the cost of an iPad. ([1] [2])

  • Meg "Whitman liberally mixed metaphors to describe her awakening to just how screwed HP was" ([1])

  • "Prepare for Windows 8 induced user rage" ([1])

  • "The argument that C.E.O.'s will leave if they aren't compensated well, perhaps even lavishly, is bogus" ([1])

  • "FTC puts a bounty on the heads of robo-telemarketers" ([1])

  • On Amazon EC2, testing performance of the instances and rejecting ones with weak performance can make a huge difference ([1] [2])

  • Good article in The Atlantic about the considerable lengths Google is willing to go to increase the quality of Google Maps ([1])

  • "We read Apple's secret Genius Training Manual from cover to cover. It's a penetrating look inside Apple: psychological mastery, banned words, roleplaying—you've never seen anything like it." ([1])

  • Big data is "a process that uses data to refine our thinking. But it doesn't work without some thinking first." ([1])

  • Surprisingly detailed talks on Netflix and LinkedIn's recommender systems ([1] [2] [3])

  • Great talk on A/B testing, especially how to do A/B testing at large companies ([1] [2])

  • Amazing speaker list at a workshop on big data for personalized education, slides from many of the talks are available ([1] [2])

  • Sometimes research just confirms what we already know (or should know), in this case, that simpler websites with familiar themes in the design do better ([1] [2])

  • "Savvy Internet users know that all the great stuff they get from the Internet us for 'free' -- the searches, the social networks, the games, even the news -- isn't really free. It's an exchange, where companies are able to take user data, sell it to advertisers, and make money." ([1] [2])

  • In the US, "80% of teens ... have a game console" ([1] [2])

  • Meanwhile, in Estonia, "a new education program that will have 100 percent of publicly educated students learning to write code" ([1])

  • Xkcd on dinosaurs ([1])

  • Good TED talk on publication bias, which is caused by not publishing negative results ([1])

  • Got willpower depletion? One study claims, if you believe willpower depletion exists, it does, otherwise it doesn't. ([1])

  • "Ever heard of the marshmallow test? The outcome may have more to do with conditioning from a child's environment" ([1])

  • "Is playtesting essential to making a good game? Yes ... [But] playtesting is like an engraved invitation that reads: 'You are cordially invited to tell me why I suck. Bring a friend - Refreshments served.' The whole point of playtesting is to make clear to you that some of the decisions you made ... are completely wrong." ([1])

Friday, September 28, 2012

Code Monster and teaching programming to kids

I recently launched Code Monster from Crunchzilla. It helps parents teach a little programming to their kids.

A lot of parents want their kids to learn a little about programming. But, if you are a parent, there seem to be only two choices out there, either have your kids slog through all the syntax and pain of tutorials and textbooks made for adults, or have them learn a visual programming language made for kids that can't be used for anything else.

Code Monster teaches Javascript, which is a useful and valuable programming language to know. When learning using Code Monster, the code is live, so changes kids make have impact immediately. They learn a bit about how to program, starting with early concepts like parameters, variables, and loops, moving through functions, eventually introducing some of the wonders of fractals, animation, and physics. Code Monster encourages experimentation. It makes programming fun.

Code Monster is an unusual blend of a tutorial and a game. It is not a tutorial or a lesson plan, but it does walk kids through many experiments with a real, useful programming language. It is not a game, but many of the children who have playtested it have found it fun, addictive, and exciting.

If you're a geek like me, there are some techie aspects of Code Monster you may find interesting. For example, Code Monster uses live code so kids see the immediate impact from code changes, no hitting a run or compile button. Code Monster provides useful help messages if the player stops working on the code but has an error. There are several nice but subtle features -- like preventing most accidental infinite loops -- that are harder to do than you might think (if you think you know how to do that in Javascript, try it, I bet your solution doesn't work). It only needs an internet connection when you first go to Code Monster (allowing working on lessons offline) and keeps your progress without saving anything remotely (privacy is important). The lessons eventually introduce quite sophisticated topics -- like fractals, L-grammars, animation, and physics -- that are very fun for kids but not normally taught to beginning programmers. But all of that tech stuff only matters because it makes Code Monster do the right thing; the important thing is that Code Monster fun and enjoyable to use.

Code Monster came out of my interest in online education, especially math and computer science education. I am convinced that, when this generation of children grows up, algorithmic thinking, large scale data analysis, and programming will be a major force multiplier for people working in many fields. People who have these tools will have the power to find breakthroughs in medicine, biology, economics, and many other areas; these tools will let them do things no others have done. I hope Code Monster can be a small piece of many more girls and boys becoming interested in computational thinking.

Please try Code Monster. It's free and it's fun. If you have kids (especially ages 9-14) , please have them try it. If you know people who have kids (or adults who are young at heart and might want to dabble in programming), please tell them about it (and share on Facebook, Google+, and Twitter too). I'd love to get the word out about it, and it's all for a good cause, it's teaching kids to program. Finally, if you have any suggestions or find it useful for your kids, please post a comment here or e-mail me at, I'd enjoy knowing how you like it and how I can make it better.

Thursday, September 13, 2012

Will tablets replace PCs?

I just bet Professor Daniel Lemire $100 that they won't.

At least, any time soon. The specific terms of the bet are, "In some quarter of 2015, the unit sales of tablets will be at least twice the unit sales of traditional PCs, in the USA." Loser donates $100 USD to the charity of the winner's choice.

How did I get to this point? About a year and a half ago, I wrote a blog post for CACM, "Who needs a tablet?"

The purposely inflammatory title overstates the main point, which is that rather than replace PCs, people are mostly buying tablets in addition to their PC ([1] [2]).

Even so, predictions in the article have already proven wrong. Tablet sales did not "stall around the same level where netbook sales stalled". Netbook sales peaked and stalled around 40M units/year worldwide ([1] [2]). Tablet sales passed 60M units/year worldwide in 2011 and are projected to be twice that this year.

So, tablets show no sign of stalling where netbooks did, but they are still being bought in addition to, not in replacement of, PCs. While many are taking some of the time they would have spent on their PC and spending it on their mobile or tablet instead, they still own and spend time on a laptop or PC.

This bet doesn't quite say what I want to say. What I want to say is that PCs aren't going away any time soon. They definitely are not going away by the end of 2015. Eventually, yes, but the change is not going to happen in less than three years.

What the bet actually says is more about how fast people in the US will buy new tablets in 2015 compared to replacing PCs. Projections I've seen put PC unit sales in the US around 16M units/quarter and mostly flat through 2015, tablet unit sales currently at 7M/quarter in the US and growing rapidly (projections vary from 10-16M/quarter by 2016). Seems unlikely that the projections would be that far off, so I took the bet.

But the more interesting questions are:
  1. What will it take to get people to stop using PCs?
  2. Will the tablet market continue to be dominated by expensive devices (like the $600 iPad) or convert almost entirely to low priced tablets (currently $200 with the Nexus 7 and Kindle Fire, but probably soon around $100)?
  3. Will anything coming in the next five years, including tablets, get people to stop buying and using PCs entirely? Or will people continue to buy and use multiple computing devices?
I've said what I think (breakthroughs in input/output, almost all $100 tablets, no). What do you think?

Tuesday, August 28, 2012

Quick links

Some of what has caught my attention lately:
  • Pump and dump, both at the Facebook and Groupon IPOs. ([1] [2])

  • "The thrilling demise of Groupon's crummy business model" ([1] [2])

  • Dave McClure says, "Returns for venture capital 'absolutely suck' ... even worse ... most VCs are 'insufferable, arrogant, fucking assholes'." ([1])

  • And good advice here, also from Dave McClure: "Don't do a startup, you idiot!" ([1])

  • Remember all the startups in desktop search a few years ago? They all disappeared when Microsoft fixed desktop search in Windows. Likewise, cloud storage is increasingly becoming part of the operating system (in MacOS, Windows, and Ubuntu), and that likely will kill off startups like Dropbox. ([1] [2])

  • This is the end of the customizable home page hype, also a popular startup idea a few years ago ([1])

  • "Once valued at more than $160 million, [Digg] is selling for the deeply discounted price of about $500,000" ([1])

  • I wonder why we don't see engineers leave en masse for another company. Lack of organization? Fear of being sued?([1])

  • After saying "Windows 8 is terrible for desktops", a reviewer goes on to predict, "Windows 7, with its 630 million licenses sold, will remain an incredibly popular OS for the next 10 years -- just like Windows XP." ([1] [2] [3])

  • WinXP amazingly still has 26% market share but, in a bizarre twist on top of that, Microsoft decided not to support IE9 on WinXP; WinXP users have to use Chrome or Firefox if they want a modern browser. ([1] [2])

  • Brutal (and long) Vanity Fair article on Microsoft. To summarize, stack ranking and Ballmer's repeated errors killed confidence, morale, and the company's performance in the last decade. This quote captures the dysfunction: "People responsible for features will openly sabotage other people’s efforts. One of the most valuable things I learned was to give the appearance of being courteous while withholding just enough information from colleagues to ensure they didn't get ahead of me on the rankings." ([1] [2] [3] [4] [5])

  • Microsoft has a decent phone out now, but it's priced so high, no one sees the point of getting it. You can't have a product consumers see as inferior to an Apple product but charge Apple-level prices, people will just get the Apple product. ([1] [2])

  • Others had the same idea as the iPhone, just no one but Apple was willing to piss off the carriers and partners and launch it ([1])

  • A change that may have widespread impact, current smartphones are getting powerful enough that people are waiting longer before replacing them; they're happy with what they already have. A similar thing happened a while ago with PCs, with dramatic impact on that industry, could be just starting for smartphones. ([1])

  • Of course you can sacrifice customer service in the short-term to boost short-term profitability. Customers take a while to learn that the service is not what it once was; you're essentially drawing down from past investment in your brand. After a few years, your brand becomes soiled, retention rates fall, customer acquisition costs rise, and profitability plummets. This has happened many times in the past, and is happening again right now. ([1] [2] [3])

  • A hybrid recommender, using both content and behavior data, wins A/B tests on articles. Why does that sound familiar (cough, Findory, cough)? ([1] [2])

  • Cute idea, default local search results not to where you are, but where you are likely going, based on your current trajectory ([1])

  • Nice example of how better hardware in your database can be faster and cheaper than expanding your caching layer ([1])

  • What we introverts have to go through to act like extroverts ([1])

  • If you have ever worked with software engineers and thought, "Why are they so grumpy?", this article provides insight, understanding, and solutions. ([1])

  • Long article from Steve Yegge, but with some thought-provoking points about liberal (risk embracing) and conservative (risk avoiding) programmers. ([1])

  • A start on personalized education, recommendations for courses ([1])

  • An interesting difference between Coursera and Udacity is that Udacity is sticking mostly to computer science. I think Udacity is right to do so, but also curious how well Coursera manages to do in fields outside of CS. ([1])

  • Love DragonBox, a game that is primarily a fun puzzle game, but also teaches algebra. The math is subtle; the puzzles involve matching and moving things on two sides of the screen that, as it turns out, represent two sides of the equation and all your moves are the same as moving things between two sides of an equation. Great for kids, really fun and addictive to play, love this, more like this please. ([1] [2])

  • Nice example of A/B testing in the physical world ([1])

  • Google App Engine launched at the top of the stack (write code and don't know where or how it is running) and Amazon EC2 at the bottom (just providing virtual machines). It's been interesting to watch both of them move toward each other, Amazon launching more and more features on top of EC2 (like CloudFront and Elastic MapReduce) and Google launching lower level services (like this new move to allow you to run your own virtual machine in Google's cloud). ([1] [2] [3] [4] [5] [6] [7])

  • Why read research papers? "These papers often foreshadow where the rest of the world is going." ([1])

  • I like this search quality metric, WTF! @ k. Colorfully useful. ([1])

  • Google Research and their hybrid research model blends research and engineering (to maximize impact and avoid the problematic tech transfer from research) and keeps projects short (but still do long-term research by iterating). ([1])

  • Cow Clicker is a very amusing (and bizarrely successful) deconstructive satire of Zynga games, reduced to just clicking, waiting, and buying your way out of waiting, hilarious. Also worth seeing is Nekogames' Parameters, which breaks down Diablo-like games to their core elements. ([1] [2] [3])

  • NNet guru Geoffrey Hinton says, "The brain is confronted by a buzzing, blooming confusion. It needs to fit many different models and use wisdom of the crowds." He then goes on to show the surprising benefits of massive NNets that drop out hidden units randomly. ([1] [2])

  • "We oversimplify because, simply, there is no other way of getting by in the world" ([1])

  • "It's not that our memory is a glitchy wetware version of computer flash memory; it’s that the computer metaphor just doesn't apply ... We store only bits and pieces of what happened—a smattering of impressions we weave together into feels like a seamless narrative. When we retrieve a memory, we also rewrite it, so that the time next we go to remember it, we don't retrieve the original memory but the last one we recollected." ([1])

  • Amazing technology, a camera fast enough to catch light moving, can see around corners using clever algorithms, well worth watching this short talk ([1])

  • Another amazing technology, very clever algorithms allowing an autonomous plate to fly at high speed in a constrained space. Go robots! Well worth watching this too, also short. ([1])

  • Yet another impressive video, worth watching. Simple idea that breaks an assumption, solves a long standing problem with robot grippers, very effective, clever. ([1])

Tuesday, August 07, 2012

The computer scientist CEO

Marissa Mayer as CEO of Yahoo may be a test of a new style of executive leadership, the optimizing CEO.

She is not the first computer scientist to lead a major company, but she is the first computer scientist (MSCS or higher) hired in as CEO to a Fortune 500 company. Many computer scientists view everything as an optimization problem. People, work, politics, life, everything is a search (often of a dynamic space) to find a maximum near the global maximum.

Marissa Mayer is an important test of a new style of CEO. She is not a Neutron Jack or Carly Fiorina, the strong military general style of bold decisions, loyalty-first, follow me, right or wrong. She is not going to be a charismatic cheerleading, press-focused CEO, the type that views their job solely as managing the message and marketing and selling the company and themselves. She is not going to be the mad visionary of Steve Jobs, yelling at everyone while single-handedly designing breakthrough products. She is a computer scientist and appears to be leading like one. I suspect she views the company, people at the company, the products, even her own role, all as an optimization process, a search to find the most productive and most useful outcomes.

The most common degree of CEOs hired into Fortune 500 companies is an MBA. Marissa appears to be the first computer scientist. This may be a test of a new style of leadership. Will Marissa Mayer be the start of companies hiring optimizing CEOs?

Thursday, July 05, 2012

Puzzling outcomes in A/B testing

A fun upcoming KDD 2012 paper out of Microsoft, "Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained" (PDF), has a lot of great insights into A/B testing and real issues you hit with A/B testing. It's a light and easy read, definitely worthwhile.

Selected excerpts:
We present ... puzzling outcomes of controlled experiments that we analyzed deeply to understand and explain ... [requiring] months to properly analyze and get to the often surprising root cause ... It [was] not uncommon to see experiments that impact annual revenue by millions of dollars ... Reversing a single incorrect decision based on the results of an experiment can fund a whole team of analysts.

When Bing had a bug in an experiment, which resulted in very poor results being shown to users, two key organizational metrics improved significantly: distinct queries per user went up over 10%, and revenue per user went up over 30%! .... Degrading algorithmic results shown on a search engine result page gives users an obviously worse search experience but causes users to click more on ads, whose relative relevance increases, which increases short-term revenue ... [This shows] it's critical to understand that long-term goals do not always align with short-term metrics.

A piece of code was added, such that when a user clicked on a search result, additional JavaScript was executed ... This slowed down the user experience slightly, yet the experiment showed that users were clicking more! Why would that be? .... The "success" of getting users to click more was not real, but rather an instrumentation difference. Chrome, Firefox, and Safari are aggressive about terminating requests on navigation away from the current page and a non-negligible percentage of clickbeacons never make it to the server. This is especially true for the Safari browser, where losses are sometimes over 50%.

Primacy effect occurs when you change the navigation on a web site, and experienced users may be less efficient until they get used to the new navigation, thus giving an inherent advantage to the Control. Conversely, when a new design or feature is introduced, some users will investigate the new feature, click everywhere, and thus introduce a "novelty" bias that dies quickly if the feature is not truly useful.

For some metrics like Sessions/user, the confidence interval width does not change much over time. When looking for effects on such metrics, we must run the experiments with more users per day in the Treatment and Control.

The statistical theory of controlled experiments is well understood, but the devil is in the details and the difference between theory and practice is greater in practice than in theory ... It's easy to generate p-values and beautiful 3D graphs of trends over time. But the real challenge is in understanding when the results are invalid, not at the sixth decimal place, but before the decimal point, or even at the plus/minus for the percent effect ... Generating numbers is easy; generating numbers you should trust is hard!
Love the example of short-term metrics improving when they accidentally hurt search result quality (which caused people to click on ads rather than search results). That reminds me of a problem we had at Amazon where pop-up ads won A/B tests. Sadly, pop-up ads stayed up for months, until, eventually, we could show that they were hurting long-term customer happiness (and revenue) even if they showed higher revenue in the very short-term, and finally we were able to take pop-up ads down.

The whole paper is a great read. The authors have a lot of experience with A/B testing in practice and all the problems you encounter with A/B testing in practice. Definitely good to learn from their experience.

Tuesday, June 12, 2012

Quick links

What has caught my attention lately:
  • The coming bandwidth explosion, by 2015, a zetabyte per year, "the equivalent of all movies ever made crossing IP networks every four minutes" ([1])

  • Googlers (including gurus Jeff Dean and Andrew Ng) train "perhaps one of the largest known networks to date" on 1000 machines for three days, shows it is possible to learn to detect faces without ever labeling any of the data as a face, which has crazy cool implications for how the brain works ([1])

  • John Dvorak says, "Windows 8 looks to me to be an unmitigated disaster".  Long-time Microsoft reporter Todd Bishop writes, "Microsoft [uses] 'fast and fluid' to describe Windows 8, but two other words keep popping to my mind: New Coke." A former Palm executive says, "To me, it feels like Microsoft is in a quiet panic. When Apple says the era of the PC has ended, I think Microsoft may believe it even more than Apple does." ([1] [2] [3])

  • "Make everyone a manager" aka "why there are no bosses" ([1] [2] [3] [4] [5])

  • Usability study shows people ignore social annotations when searching (e.g. one of your friends clicked or liked a web page that is in your search results) and, in the rare cases when searchers pay attention to them, people don't find them useful. Pretty serious implications for Facebook's partnership with Bing and Google's increasingly annoying habit of slopping Google+ all over Google web search. ([1]

  • Prefetching entire web pages has issues, but a lot of the benefit can be gained just with DNS prefetching and TCP preconnecting.   "If we guess right, the DNS and TCP handshake may complete before we even hit enter."  Lots of clever ideas in Google Chrome, including this one. ([1])

  • Chatbot for Facebook and Twitter that basically does Let Me Google That For You, very funny, but also surprisingly effective ([1])

  • Retention, morale, productivity, and recruiting have long been wastelands of opinion over data, but here is a very welcome initiative to change that spearheaded by Google. By the way, I love that Google doesn't have Human Resources, they have "People Ops". ([1])

  • The time has come to optimize code for energy consumed. Don't miss the table showing how many joules it takes to render the home pages of some popular websites. ([1])

  • At least for ambiguous queries like [pizza], Google no longer emphasizes search results, not a bad idea, but quite a change for them ([1])

  • Google is now crawling and executing most Javascript on the Web. This has been talked about for years, but first I've heard of it being done routinely at massive scale. ([1])

  • For shopping search results, it matters what products you show next to each other.  In particular, people often buy in the middle of the price range, so the mix of prices on the products you show can change what product people buy. ([1])

  • Is Google's mission now organize the world's information and make it universally accessible and useful (but only if you pay to be included)? ([1])

  • Clever idea here, using playlists (or wishlists or any kind of publicly available list) for recommendations. ([1])

  • A WWW 2012 paper that both quotes Xkcd and contains the sentence "this is quite a sweet ass-abstract for a scientific paper, dude!" in the introduction. Fun paper as well, but I think it's notable for that alone. ([1])

  • Remarkable ability to automatically stabilize the camera in YouTube videos. Make sure to look at the two videos. ([1])

  • Can't wait for us to have full wall displays controlled by voice and gesture, these are another step closer ([1] [2])

  • Udacity and Coursera are getting more explicit about their business model, which appears to be sourcing programmers nicely pre-screened for coding ability to companies. ([1] [2])

  • On flipped classrooms: "A control class that received a lecture from a Nobel Prize-winning physicist and an experimental section where students worked with graduate assistants to solve physics problems. Test scores for the experimental group (non-lecture) was nearly double that of the control section (41% to 74%)." ([1])

  • Love that robot swarms are practical and starting to be used. Want to see this for space and undersea probes too. ([1])

  • A big step toward computers that accept error as normal, yielding large gains in efficiency and performance ([1])

  • Talk about geniuses at Facebook ignores the big problem that no one -- not Google, Yahoo, Microsoft, Facebook, or any of the newspapers -- knows how to solve this problem of making advertising relevant, effective, and lucrative without immediate purchase intent, despite years of work by thousands of brilliant people ([1] [2])

  • "The buy, driven entirely by Zuckerberg, was made because Facebook’s CEO was petrified of Instagram becoming a Twitter-owned property. Zuckerberg, we’re told, lives in perpetual anxiety, preoccupied by the fear of Facebook losing its place ... That fear served as the catalyst behind his decision to buy Instagram." ([1] [2])

  • Fascinating (but long) talk by Googler Steve Seitz on "the next generation of Google Maps". Also a great survey of work (older work and work currently at Google) using crowdsourced photos to build 3D walkthroughs of cities and interiors for photo tourism. Relevant for Apple launching their own maps, but also amazing and fun, can't wait to see more of this launched. ([1])

  • The decline of TV has been greatly exaggerated ([1])

  • Ubiquitous Wi-Fi might be back, this time with cell phone-like handoff between hotspots, could be a real game changer ([1])

  • One of the better articles on this: "5 Things You Should Know Before Working at a Start-Up" ([1])

  • "The average VC fund returns less money to investors than they invested in the first place." ([1] [2])

  • Truly random (and fast) number generators by looking at quantum vacuum, possibly soon small and cheap enough to be put on a motherboard. Sounds trivial, I know, but insufficiently random numbers cause security and performance problems, so this really is a pretty useful idea. ([1])

  • "Geek" has really changed meaning in the last decade, now almost admired. ([1])

Thursday, May 17, 2012

The game Stick Portal

I want to share more of the ideas I've been exploring. First, let me start with this, an early version of a game I'm calling Stick Portal. Click on the image to play:
It's entirely written in Coffescript using HTML5 canvas. Just need a browser to play, works pretty well on mobile devices (add it to your home screen and it'll even go full screen and behave like a free app).

The idea is to create a simplified puzzle game with a level editor where kids could share levels they created. The current version has ten levels that are the tutorials to teach players how to play the game. I've just started on the level editor that will, eventually, allow people to create their own levels easily and share them with others.

The motivation for this came from seeing what Valve did with Portal 2. Portal 2 had a level editor called Hammer that was amazing but incredibly hard to use. Kids were using Hammer to create puzzles for each other that they could play in Portal 2 -- which is great exposure to CAD-like modeling tools and a nice spatial reasoning workout -- but it was really painful. Valve just launched a much easier-to-use editor for Portal 2 that is truly fantastic, highly recommend it.

Stick Portal is free to play, open source (MIT license), and the code is available on GitHub. The source might be useful to people working on similar games as it contains examples of ways to use the Box2Djs physics engine, handling touch and multi-touch (and accelerometer) on mobile devices, how to make your web page look like an app, plenty of examples of working with HTML5 Canvas, crazy things like a way to automatically resize the canvas when the browser window changes or a device rotates, and a lot of other goodies. Won't claim it's the most beautiful code ever, but it is well commented and was fun to write. I hope it is useful.

I plan to keep working on this and extend it to include an editor, but I've been sitting on this long enough so, in the spirit of launch early and often, I'm putting it out now. Please let me know what you think in the comments, and I'd love it if you'd drop me a note if your kids like the game or if the examples in the source turn out to be useful to you.

Update: A couple people have told me they have gotten stuck not being able to guess the controls in the tutorial. It's AWSD or arrow keys for movement and mouse button and mouse movement for the portal gun. On mobile, it's hold down your finger to run toward your finger and hold down above you to jump, tap to aim and fire the portal gun, and second finger (multi-touch) to move the portal gun without firing (like to maneuver a held box).

I also should have said more explicitly that one very cool thing is that the game doesn't use Flash, it's just HTML5. So, it works on all modern browsers without a plug-in, which is neat-o. Also interesting is that it is a fairly complicated HTML5 game running smoothly in the browser on PCs and mobile, almost looking like a native app, but not a native app.

Finally, let me add that I did this game mostly to learn about making games fun. That's a surprisingly hard thing to do. If you're interested in that topic too, nothing like trying to do it yourself, but I'd also recommend the books "A Theory of Fun Game Design" and "The Art of Game Design: A Book of Lenses". And, if you find Stick Portal fun or don't find it fun, please let me know!

Thursday, April 12, 2012

More quick links

More of what has caught my attention recently:
  • $1B for Instagram was silly and caused by fear ([1] [2] [3] [4]), but it is impressive the scale Instagram built with just three engineers ([5] [6])

  • Felix Salmon at Reuters writes that Twitter is under revenue pressure and will start doing things that make the site much less pleasant to use. I'd say Facebook is under similar pressure. Both likely will do increasingly aggressive attempts to sell their users to advertisers and may face a backlash. ([1] [2] [3])

  • Google has millions of machines ([1] [2] [3]), so many that "a performance improvement of even 1% can results in millions of dollars saved", which explains why they spend so much time on the details, like how threads run on cores and estimating disk space needed ([4] [5])

  • Great recent talk by Googler Jeff Dean on problems due to hitting occasional latency in large scale distributed systems, some surprising and useful advice here. ([1] [2])

  • While 89% of ad clicks are incremental (visit wouldn't have happened without the ad), only 50% of ad clicks on the top ad are incremental. Is that due to ads on navigational queries? And does Google effectively force companies to buy those ads (so competitors don't get them) even though the ads are not very effective? ([1])

  • "In this two-part blog post, we will open the doors of one of the most valued Netflix assets: our recommendation system." ([1])

  • "Yahoo's Chief Product Officer Blake Irving resigns" over disagreements on strategy, in particular he was "concerned about the massive engineering and research talent exodus of late, especially in Yahoo's vaunted Labs arm." ([1] [2])

  • The field of astronomy appears to be going through a major shift to large scale analysis of truly massive data sets ([1] [2])

  • Amazing to me that Walmart has taken this long to ramp up online against Amazon. Amazon even has been called the "Walmart of the Web"; you going to take that, Walmart? ([1])

  • A clever analysis deduces that Amazon has 450k machines in AWS. ([1] [2])

  • A video out of Microsoft Research shows how different interacting with a tablet would feel if touch response times could be made faster. Very compelling. ([1])

  • Other work out of Microsoft Research demos a Kinect-like gesture interface built using what is essentially echolocation via a laptop's built-in microphone and speaker, no other hardware required. (video [1] and CHI 2012 paper [2])

Sunday, March 18, 2012

Quick links

What has caught my attention lately:
  • Videos showing Windows 8 is horribly painful for most people, looks likely to be another Windows Vista-like flop. Really worth watching the videos or trying it yourself (videos [1] [2], try it [1] [2])

  • "38% of the ads are never in view to a user" and another 12% "of the ads are in view for less than 0.5 seconds" ([1])

  • "Many more ads" are coming on Facebook, "a lot more advertising ... [on] Facebook's traditionally clean interface." Could this mean Facebook is having revenue trouble already? ([1] [2] [3])

  • Not only is the iPhone over half of Apple's revenue, it is more than 70% of their profits. Apple really is a mobile phone manufacturer with a few other businesses attached. ([1])

  • Coming soon, a "voice-activated assistant that remembers everything you say ... systems that are more conversational, that have the ability to ask more sophisticated followup questions and adapt to the individual ... [with] short-term and long-term memory." ([1])

  • "Microsoft tries to find pockets of unrealized revenue and then figures out what to make. Apple is just the opposite: It thinks of great products, then sells them." ([1])

  • "The best way to get the most out of engineers is to surround them with other great engineers." ([1])

  • "It’s positively de-motivating to work for a company where your job is just to shut up and take orders. In tech startup land, we all understand instinctively that we have to hire super smart people, but we forget that we then have to organize the workforce so that those people can use their brains." ([1])

  • Programmers want to learn new skills and technology while working in a team of people they respect, and over 90% of programmers said they are willing to take a lower paying job to get that. ([1])

  • Netflix's streaming catalog continues to deteriorate, is now down to only 853 good movies, of which only 155 were released within the last five years ([1] [2] [3])

  • "This class is about setting you on the path to developing good taste as a programmer" (free, from Udacity, taught by Googler and AI guru Peter Norvig, starts Apr 16) ([1])

  • Could this be the business model for Udacity? Offer free classes online, then send companies candidates pre-screened for machine learning programming ability? ([1] [2])

  • If my blog is any indication, the only RSS feeder still being used is Google Reader. Are all others dead now? ([1])

  • Huge and wide open opportunity in personalized advertising for online news. Amazes me Yahoo and Amazon haven't gone after this, and that Google hasn't done a better job going after it. ([1])

  • Paper with fascinating statistics on Groupon and other daily deal sites. Most dramatic, it costs restaurants half a star in their Yelp rating if they offer Groupon deals. ([1])

Friday, March 09, 2012

Ad targeting at Yahoo

A remarkably detailed paper, "Web-Scale User Modeling for Targeting" (PDF), will be presented at WWW 2012 that gives many insights into how Yahoo does personalized advertising.

In summary, the researchers describe a system used in production at Yahoo that does daily builds of large user profiles. Each profile contains tens of thousands of features that summarize the interests of each user from the web pages they have viewed, searches they made, and ads they have viewed, clicked on, and converted (bought something) on. They explain how important it is to use conversions, not just ad clicks, to train the system. They measure the importance of using recent history (what you did in the last couple days), of using fine-grained data (detailed categories and even some specific pages and queries), of using large profiles, and of including data about ad views (which is a huge and low quality data source since there are multiple ad views per page view), and find all those significantly help performance.

Some excerpts from the paper:
We present the experiences from building a web-scale user modeling platform for optimizing display advertising targeting at Yahoo .... Our work ... [looks] into understanding the effect of different user activities on prediction, [gives] insights about the temporal aspect of user behavior (recency vs. long-term trends), and [explores] different variants (user representation and target label) through large offline and online experiments .... We deployed our platform to production and achieved a [large] boost in online metrics, such as eCPA, compared to the old system.

Our objective is to refine the targeting constraints using the past behavior of the users ... [so] we can improve the number of conversions per ad impression without greatly increasing the number of impressions.

User profiles are aggregated logs from different systems/products (e.g. user logs of Yahoo News, Yahoo Finance, etc.) .... We consider several different events ... [including] pages visited .. the category of the page ... searches issued, clicks on search links, clicks on search advertising links ... [and] the category of the search query ... [and] views and clicks on ads ... [and] the ad category ... from an existing hierarchical ad categorizer.

Our results show [a] large performance loss incurred in favoring long-term history over short-term history. This is obvious as the recent history clearly communicates with a high probability the current interest of the user ... Although recent history is more important than older history, we still need to include older history to get the most complete idea about the user.

Results show ... many of our raw features are completely non-discriminative. However, a small percentage of these features are actually important ... [For example, just] ... dropping all raw ad views ... [or if] we drop all raw features and only keep categorical features ... [causes] dropping [of] the weighted AUC measure by 3.69% and 4.26%, respectively ... In production ... we apply a coarse feature selection through mutual information, then we apply a rigorous feature selection through l1 regularization.
Very interesting. A couple things I am left wondering:

First, they found recent history is very effective, yet only update the profiles daily. Wouldn't their results on the value of recent behavior (which others found too) suggest that there would be benefit from hourly or, even better, real-time updates of the profiles (perhaps with a second memory-based, unreliable, and partial coverage system supplementing the data in the more complete and more accurate older profiles)? That would allow the system to adapt immediately when someone, for example, starts looking at information for a vacation to Hawaii and show relevant offers immediately instead of only being able to do it the next day when it is usually too late. Unfortunately, I suspect we're not going to see really big gains in relevance and usefulness of ads without real-time updates to profiles of fine-grained interests; results that show that data only 24 hours old is better than data a week old may only be a tease of the gains to be seen with data only seconds old.

Second, they find that features based on individual search queries and pages viewed ("raw features") usually have no value, but occasionally have enough value that it is important to include some. Wouldn't that suggest that the categorization scheme for pages viewed, searches made, and ads need to be more fine-grained (e.g. not just the category "pants", but the category "men's boot cut jeans")? Or, better, perhaps more fine-grained while also correctly cross correlated (interest in "men's boot cut jeans" not only shows in the data a weak interest in all pants, but also maybe has been shown to indicate a fairly strong interest in "men's flannel shirts")?

If you are interested in this paper, you might also want to look at another recent paper out of Yahoo Research, "Learning to Target: What Works for Behavioral Advertising" (ACM), which is referenced multiple times by this paper and describes the features used in the user profile in a bit more detail, as well as the results of some other experiments.

Please see also my 2007 post, "What to advertise when there is no commercial intent?"

Friday, January 27, 2012

More quick links

More of what has caught my attention lately:
  • Laptops with Kinect sensors are coming. Worth paying attention to, gesturing in air to issue commands, a very different UX could be built on top of this ([1] [2])

  • "Each streaming subscriber is worth only $2.40 in profit each quarter to Netflix, compared to $17.32 for each DVD subscriber. The old business was very lucrative. The new business kind of sucks." ([1])

  • "You're not going to get content owners to license ... for less than what they get from the cable companies ... [if you will] use that cheap content to destroy the cable companies' business model." ([1])

  • "Federal officials approached Google with evidence of its employees' wrongdoing ... Google agreed to pay $500 million to ... ward off criminal charges against the company." ([1])

  • Google is spending nearly $1B every quarter buying new servers and data centers. That buys a lot of machines. ([1] [2])

  • Education startups are suddenly very, very hot. ([1] [2] [3] [4])

  • "Tiny directional antennas at the top of each rack ... send and receive data. A central controller monitors traffic patterns, finds network bottlenecks, configures the antennas and turns on the wireless links when more bandwidth is required ... The design sped up traffic by at least 45 percent." ([1])

  • "Wimpy cores are fine, but if you go down to the wimpiest range, your gains really have to be enormous if you want to consider all the aggravation -- and the hit to their productivity -- that your software engineers face." ([1])

  • A Facebook engineer explains why is actually the right thing for Facebook to produce buggy code ([1])

  • "How sex, bombs, and burgers shaped our world" ([1])

  • "There is a monolithic view that this generation of technology I.P.O.'s is completely broken." ([1])

  • Just three engineers built and run Instagram, which has 14 million users, 150 million photos, several terabytes of data, and hundreds of machines. ([1] [2])

  • Startup founders "say that if they'd known when they were starting their company about the obstacles they'd have to overcome, they might never have started it." ([1])

  • Two 17-year-olds used a weather balloon to send a little Lego astronaut and a video camera 15 miles into the stratosphere. Very fun. ([1])