Broadly agree with this and the parent - but there's an interesting alternative way to look at travel metasearch.

If you think of obtaining prices as being akin to 'indexing', then what metasearch engines are doing is building up a search index for flights. And not all price sources necessarily charge for data (do Google pay to index Hacker News?)

Flight prices become stale as do indexed web pages - and as long as the user doesn't pay a transaction price for any search activity, then you can re-check pages based on user activity - in the case of travel, re-check the price once the user nears the booking phase of the funnel.

As noted though, sparseness of travel queries is certainly tricky! The 80/20 rule applies to some extent, and popular routes will be the ones which have the best price cache.

Another disclosure: I work for Skyscanner (our core is a flexible travel search engine)

I imagine that the kind of traveller looking at this map wouldn't care so much about the direct A-to-B-ness of flights, given that they don't even care that much about where they're going in the first place. They just want to go somewhere interesting, for cheap.

Therefore, rather than only considering the single lowest-cost edge on the graph (that is, an A-to-B flight to an interesting place), you could consider lowest-cost paths, using a pathfinding algorithm (secondarily weighted by the popularity of intermediate cities/vertices as temporary destinations.) Thus, instead of going to city X, it would recommend going to Y, staying a month and taking in the local culture, and then finishing the trip to X with a short, local flight in the off-season (or any other method of travel—it could integrate with Google Maps to see if it would be cheaper to drive between each pair of intermediate nodes than fly.)

I fought this challenge a few years ago and made some some (albeit, little) progress. Besides not being fully versed in programming, I ran into many other problems from processing time, threading, concurrency, but as a number of you mentioned, the biggest challenge is cost. The throughput with or without intent to purchase wouldn't come close to covering the cost of queries. There are ways to offset this- using on/off site marketing, limiting query combinations, and partnerships, but the problem is big- and grows bigger with each subtle change in the query. Cacheing results can help, but the real value of the tool diminishes with each cached result.

I went back and forth with Bill O (at Kayak) while leveraging their API, and know the cost/query was fairly high a few years ago. I suspect it has decreased, but probably not to the point where the processing power needed for massive permutations and cost/query makes this any more feasible.

I set up a proof of concept in 2006/2007 that still works (most of the time). I ended up using Flash/Flex front-end to overcome the number of browser HTTP connections (and keep some of the processing on the client). I'm not sure this actually helped the server or not b/c I never did any testing. I also limited to "where can you go" (multiple city pairs) and "when should I go" (single city pair with multiple dates), but not a combination of both.

Feel free to take a look. It will shut down after the max number of queries/day is reached.

http://takoph.com/poc/takoph.html

We actually started building such a product for India where the problem complexity is much smaller (only about 20 prominent airports, majority travel by train where prices are static, only availability varies with time).

Availability of data APIs turned out to be a big hurdle for a bootstrapped startup. The market is still up for grabs. Here is another attempt by an Indian startup:

http://www.90di.com/travel/#form_based_search_home_page