4 ms·

It’s rather powerful: as long as the origin airport is one of those shown on the map, and the destination airport is reachable via a domestic flight on one of t

It’s rather powerful: as long as the origin airport is one of those shown on the map, and the destination airport is reachable via a domestic flight on one of the major airlines (AA, AS, B6, CO, DL, F9, UA, US), the search results come back instantaneously. Multiple origins and destinations (up to five of each) are supported as well: http://www.google.com/flights/#search;f=LAX,SFO,SEA,LAS,DEN;t=ORD,BOS,MIA,ATL,CLT;d=2011-10-10;r=2011-10-14;mp=1300;md=690 http://www.google.com/flights/#search;f=LAX,SFO,SEA,LAS,DEN;... And the results still come back immediately! Including the three-month chart of prices. This leads me to believe that Google/ITA has precomputed all of these results, and is simply serving these results out of a cache of some sort. That would explain why they are only offering a limited set of origin airports at this time: it probably takes an incredible amount of computing power and storage space to pre-calculate all of the possible results. Colour me impressed.

stingraycharles 15y ago
Interesting. That makes me wonder: would that really be the optimal approach? Google is able to return search results for previously unsearched queries nearly instantaneously too, so I'm wondering whether it's really a cache that's serving those queries. Would some sort of graph-based index be possible in this situation?
- kiwidrew 15y ago
  Yes, using a shortest path tree [1], it is possible to efficiently (for some definition of "efficient") calculate the best path from a single origin node to all destination nodes in the graph. Dijkstra's algorithm is the standard implementation, but is not very amenable to parallel processing. Perhaps unsurprisingly, Google has a framework called Pregel [2] which does parallel graph processing. Their research paper outlines how it can be used to calculate a single-source shortest path tree (in section 5.2) in reasonable time. [1] http://en.wikipedia.org/wiki/Shortest_path_tree http://en.wikipedia.org/wiki/Shortest_path_tree [2] http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf
- noduerme 15y ago
  Lol. If I were Google, I'd probably have bought all the tickets in advance ;) Thing that gets me is, do they really send their employees SFO to LA on United?! Southwest's like a third the price... And why isn't SW listed, anyway? Did Herb take issue with something here?
  - jbail 15y ago
    Probably for the same reason you don't see Southwest flights on any travel website. Southwest doesn't allow their flights to be booked outside of their website.
  - lee337 15y ago
    This information is a decade old, but my wife told me that Southwest were the only American airline to make a profit. That could have something to do with it... EDIT: This recent news article states "Of the five biggest U.S. airline companies, analysts expected only Southwest to report a first-quarter profit": http://travel.usatoday.com/flights/story/2011/04/Southwest-manages-to-make-a-Q1-profit---/46353984/1 http://travel.usatoday.com/flights/story/2011/04/Southwest-m...
    - drags 15y ago
      Some of Southwest's profit comes from fuel price speculation, which could backfire on them much more quickly and easily than their core business: http://en.wikipedia.org/wiki/Southwest_Airlines#Risk_management http://en.wikipedia.org/wiki/Southwest_Airlines#Risk_managem...
      - joahua 15y ago
        From what I understand fuel contract hedging is a pretty standard part of airline business. Obviously hedging has potential to go the other way but it's unlikely to erode profit unless competitors are able to significantly compete on price and steal customers...
- gyardley 15y ago
  Here's the classic presentation people usually refer to when talking about flight pricing complexity. http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf http://www.demarcken.org/carl/papers/ITA-software-travel-com... I'd love to know how Google's doing it - it's a really hard problem.
  - kiwidrew 15y ago
    Well, if one narrows down the options a bit, it becomes far more tractable. Considering that Google's flight search only works for domestic return trips of 15 days or less (it didn't seem to give me results for anything longer than that?) and doesn't allow stopovers or open jaws, it's entirely possible that the complexity is much reduced.
  - objclxt 15y ago
    What's interesting is that you linked to an ITA Software presentation, and Google own ITA Software. So it's almost certain that some of the people who put that document together worked on this pre-computed solution.
  - lars 15y ago
    If I remember correctly, it's mentioned in Artificial Intelligence, A Modern Approach that this problem is not only hard but in fact formally undecidable in the general case.
chintan 15y ago
Seems they are only pre-computing for next month or so.. http://www.google.com/flights/#search;f=EWR,JFK,LGA;t=ORD;d=2011-10-01;r=2011-11-01 http://www.google.com/flights/#search;f=EWR,JFK,LGA;t=ORD;d=... gives: Your search – New York to Chicago – did not match any results. versus http://www.kayak.com/#flights/NYC-ORD/2011-10-01/2011-11-01 http://www.kayak.com/#flights/NYC-ORD/2011-10-01/2011-11-01 1347 of 1347 roundtrips shown
- alec 15y ago
  Trip length duration is currently limited to 14 days.
  - smackfu 15y ago
    It's odd that the limits are just in the data it seems, not in actual limit checks. So when you hit a limit, it's indistinguishable from there being no available flights... which seems very bad for UX.
grayrest 15y ago
Here's one that didn't work for a trip I'll be making later this month: http://www.google.com/flights/#search;f=LGA;t=MYR;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=LGA;t=MYR;d=2011-09-... No flights. However: http://www.google.com/flights/#search;f=LGA;t=ATL;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=LGA;t=ATL;d=2011-09-... http://www.google.com/flights/#search;f=ATL;t=MYR;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=ATL;t=MYR;d=2011-09-...
Fenn 15y ago
I would think the limiting factor is availability. You can pre-compute valid fares between cities super-fast with sufficient computing power, but you're still (somewhat) limited by the rate at which you can update availability, which _still_ has to be polled from airline systems (to some degree) and can't give you answers in <400ms :) One of the bits ITA/QPX got really right was smart availability caching (http://hasbrouck.org/blog/archives/001880.html http://hasbrouck.org/blog/archives/001880.html) - I would think they can do the fare search/assembly in realtime with their infrastructure, but they're relying on cached availability, hence the limit to "popular US cities" at the moment, to keep caches fresh enough within the practical throughput limits.
- Fenn 15y ago
  Expanding on this, one of the things ITA/QPX comes with is a dirty big availability cache that's constantly being primed (and paid for) by their customers (ie: Kayak, Orbitz, et al), who are now ironically not getting any traffic from Google :) And they have this: http://itasoftware.com/pdf/BrochurePDF_DACS.pdf http://itasoftware.com/pdf/BrochurePDF_DACS.pdf
jser 15y ago
Published airline fares change only a couple of times a day (10:30am, noon and 8pm), and only once a day on the weekends. Airlines (like American) are trying to push travel sites to use more dynamic pricing. The data is cached and outdated (including availability). It doesn't take a tremendous amount of computing power -- remember that most airlines are still running ancient mainframe reservation systems. The multiple destinations functionality was from ITA -- it's been around for years. Check out flyertalk.com for discussions -- you can input multiple layovers to have it compute cheap fares that maximize miles/segments. They keep a basic backend open at: matrix1.itasoftware.com

stingraycharles 15y ago

Interesting. That makes me wonder: would that really be the optimal approach? Google is able to return search results for previously unsearched queries nearly instantaneously too, so I'm wondering whether it's really a cache that's serving those queries. Would some sort of graph-based index be possible in this situation?

kiwidrew 15y ago
Yes, using a shortest path tree [1], it is possible to efficiently (for some definition of "efficient") calculate the best path from a single origin node to all destination nodes in the graph. Dijkstra's algorithm is the standard implementation, but is not very amenable to parallel processing. Perhaps unsurprisingly, Google has a framework called Pregel [2] which does parallel graph processing. Their research paper outlines how it can be used to calculate a single-source shortest path tree (in section 5.2) in reasonable time. [1] http://en.wikipedia.org/wiki/Shortest_path_tree http://en.wikipedia.org/wiki/Shortest_path_tree [2] http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf
noduerme 15y ago
Lol. If I were Google, I'd probably have bought all the tickets in advance ;) Thing that gets me is, do they really send their employees SFO to LA on United?! Southwest's like a third the price... And why isn't SW listed, anyway? Did Herb take issue with something here?
- jbail 15y ago
  Probably for the same reason you don't see Southwest flights on any travel website. Southwest doesn't allow their flights to be booked outside of their website.
- lee337 15y ago
  This information is a decade old, but my wife told me that Southwest were the only American airline to make a profit. That could have something to do with it... EDIT: This recent news article states "Of the five biggest U.S. airline companies, analysts expected only Southwest to report a first-quarter profit": http://travel.usatoday.com/flights/story/2011/04/Southwest-manages-to-make-a-Q1-profit---/46353984/1 http://travel.usatoday.com/flights/story/2011/04/Southwest-m...
  - drags 15y ago
    Some of Southwest's profit comes from fuel price speculation, which could backfire on them much more quickly and easily than their core business: http://en.wikipedia.org/wiki/Southwest_Airlines#Risk_management http://en.wikipedia.org/wiki/Southwest_Airlines#Risk_managem...
    - joahua 15y ago
      From what I understand fuel contract hedging is a pretty standard part of airline business. Obviously hedging has potential to go the other way but it's unlikely to erode profit unless competitors are able to significantly compete on price and steal customers...
gyardley 15y ago
Here's the classic presentation people usually refer to when talking about flight pricing complexity. http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf http://www.demarcken.org/carl/papers/ITA-software-travel-com... I'd love to know how Google's doing it - it's a really hard problem.
- kiwidrew 15y ago
  Well, if one narrows down the options a bit, it becomes far more tractable. Considering that Google's flight search only works for domestic return trips of 15 days or less (it didn't seem to give me results for anything longer than that?) and doesn't allow stopovers or open jaws, it's entirely possible that the complexity is much reduced.
- objclxt 15y ago
  What's interesting is that you linked to an ITA Software presentation, and Google own ITA Software. So it's almost certain that some of the people who put that document together worked on this pre-computed solution.
- lars 15y ago
  If I remember correctly, it's mentioned in Artificial Intelligence, A Modern Approach that this problem is not only hard but in fact formally undecidable in the general case.

chintan 15y ago

Seems they are only pre-computing for next month or so.. http://www.google.com/flights/#search;f=EWR,JFK,LGA;t=ORD;d=2011-10-01;r=2011-11-01 http://www.google.com/flights/#search;f=EWR,JFK,LGA;t=ORD;d=... gives: Your search – New York to Chicago – did not match any results. versus http://www.kayak.com/#flights/NYC-ORD/2011-10-01/2011-11-01 http://www.kayak.com/#flights/NYC-ORD/2011-10-01/2011-11-01 1347 of 1347 roundtrips shown

alec 15y ago
Trip length duration is currently limited to 14 days.
- smackfu 15y ago
  It's odd that the limits are just in the data it seems, not in actual limit checks. So when you hit a limit, it's indistinguishable from there being no available flights... which seems very bad for UX.

grayrest 15y ago

Here's one that didn't work for a trip I'll be making later this month: http://www.google.com/flights/#search;f=LGA;t=MYR;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=LGA;t=MYR;d=2011-09-... No flights. However: http://www.google.com/flights/#search;f=LGA;t=ATL;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=LGA;t=ATL;d=2011-09-... http://www.google.com/flights/#search;f=ATL;t=MYR;d=2011-09-29;r=2011-10-03;a=SKYTEAM http://www.google.com/flights/#search;f=ATL;t=MYR;d=2011-09-...

Fenn 15y ago

I would think the limiting factor is availability. You can pre-compute valid fares between cities super-fast with sufficient computing power, but you're still (somewhat) limited by the rate at which you can update availability, which _still_ has to be polled from airline systems (to some degree) and can't give you answers in <400ms :) One of the bits ITA/QPX got really right was smart availability caching (http://hasbrouck.org/blog/archives/001880.html http://hasbrouck.org/blog/archives/001880.html) - I would think they can do the fare search/assembly in realtime with their infrastructure, but they're relying on cached availability, hence the limit to "popular US cities" at the moment, to keep caches fresh enough within the practical throughput limits.

Fenn 15y ago
Expanding on this, one of the things ITA/QPX comes with is a dirty big availability cache that's constantly being primed (and paid for) by their customers (ie: Kayak, Orbitz, et al), who are now ironically not getting any traffic from Google :) And they have this: http://itasoftware.com/pdf/BrochurePDF_DACS.pdf http://itasoftware.com/pdf/BrochurePDF_DACS.pdf

jser 15y ago

Published airline fares change only a couple of times a day (10:30am, noon and 8pm), and only once a day on the weekends. Airlines (like American) are trying to push travel sites to use more dynamic pricing. The data is cached and outdated (including availability). It doesn't take a tremendous amount of computing power -- remember that most airlines are still running ancient mainframe reservation systems. The multiple destinations functionality was from ITA -- it's been around for years. Check out flyertalk.com for discussions -- you can input multiple layovers to have it compute cheap fares that maximize miles/segments. They keep a basic backend open at: matrix1.itasoftware.com