Wednesday, July 21, 2010

Finally, A New Posting---Systems

It's been a long time since I last did a blog posting. Partially, this is because I've been working with a different company for the last year and it was hard to post anything interesting that didn't impinge on their proprietary interests. That's still true to some degree, but a lot of what I've seen with respect to system design there is still relevant. Of course, the other motivation is that the company I'm working for is ITA Software, which Google recently announced they were acquiring. So, if all goes well, sometime in the not too distant future this I'll be a Google employee.

So, let me start with ITA's products, some of their differences, and how not to learn form success. ITA's original product is a shopping and pricing product that is used on many web sites to find the flight combination for an itinerary with the best price. This is a lot harder problem then I expected, largely because airlines are really clever at controlling their prices to get the most money out of travelers on each flight. And as if that wasn't hard enough there are all those extra fees that need to be included (and taxed) in order to get the actual price of the tickets. And for international flights that cross multiple borders, each with their own currencies, tax structures and conversion rates. Just figuring out the price to charge for a coke on a flight is daunting.

But the ITA people are really smart, they work really hard, and they figured out how to do all of that, how to it all very fast, accurately, and reliably. This problem, while very complex to get right and efficient, is at its core very simple. It is a special filtered search in a very, very large graph which is never actually generated. One way to think about the problem is that is like looking for the way out of a large maze. At each corner you have 2 or 3 possible choices and the complete graph of all possible choices could be enormously large. You can't generate the whole graph and local optimums won't get you out of the maze. Sounds like an Artificial Intelligence problem doesn't it? Would you be surprised that our CEO comes the AI lab at MIT?

Next time, I'll talk a bit about the project I'm working on, and how it differs.