Technical description of ITA Software's search engine
 

The highly technical article can be found here:

http://www.paulgraham.com/carl.html

As most of you know, their search engine is used by Orbitz, and you can sample it directly at http://www.itasoftware.com/demos/

From the article:

"The real challenge is that a single fixed itinerary (a fixed set of flights from BOS to LAX and a fixed set back) with only two flights in each direction may have more than 10,000 possible combinations of applicable 'fares', each fare with complex restrictions that must be checked against the flights and the other fares. That means that the search space for this simple trip is of the order 5000 x 5000 x 10000, and a naive program would need to do a _lot_ of computation just to validate each of these possibilities."