Dividing A Travel Query Into Sub-Queries

• US 20110153592A1
• Filed: 03/04/2011
• Published: 06/23/2011
• Est. Priority Date: 10/16/2002
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: DeMarcken, Carl G.
• Application Number:
  US13/040,346
• Publication Number:
  US 20110153592A1
• Time in Patent Office: Days
• US Class Current: 707/713
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

Techniques for dividing a travel query into sub-queries for execution by a travel planning system is described. The techniques can divide the travel query according to some optimization such as by taking query processing difficulty into consideration or loading on the travel planning system.

Claims

1. A method comprising:

receiving by a computer system a travel planning query including trip information including time of departure and origin and destination information from a client system;

dividing by the computer system the travel query into sub-queries for execution by a travel planning system the sub-queries divided according to a criterion selected from the group consisting of;

destination airport, outbound departure time, outbound and return departure times, airline, fares booking codes, cabin classes, carriers, and flight combinations;

receiving from plural computer systems answers in response to each of the sub-queries;

merging the received answers to return answers that satisfy the travel planning query.

2. The method of claim 1 wherein the sub-queries are divided according to destination.

3. The method of claim 1 wherein the query is used with the travel planning system to produce an answer that includes flights that satisfy the query and fares that are valid for the flights.

4. The method of claim 1 further comprising:

concurrently executing the sub queries on the plural computers, with executing the sub-queries comprising;

calculating by each of the plural computers the answers with calculating based on the selected criterion, the trip information in the sub-query.

5. The method of claim 1 wherein the computer system is part of a travel planning system, the method further comprising:

annotating by the computer system the travel planning query with a total number of sub-queries;

assigning by the computer system an index to each a sub-query; and

executing the sub-queries on the plural computers that are part of the travel planning system, with executing comprising;

calculating the answers by applying a travel planning application to data to form the answers.

6. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a time range.

7. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a pair of time ranges.

8. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a set of locations.

9. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to both a time range and a set of locations.

10. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a set of flight combinations.

11. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a set of fares or booking codes or cabin classes.

12. The method of claim 1 wherein the sub queries are provided by dividing the travel query according to a set of carriers.

13. The method of claim 1 further comprising:

determining a potential cost associated with execution of each of the sub-queries; and

wherein the sub queries are provided by dividing the travel query in accordance with one of the criteria and the determined potential cost of executing each of the sub-queries.

14. The method of claim 1 wherein the method is executed on a travel planning system comprised of the computer and the plural computers that each execute a travel planning application, the travel planning application calculating answers to the sub-queries and the sub queries are determined independently on each of the planning computers.

15. The method of claim 1 wherein the method is executed on a query distributer computer that sends the sub-queries to a travel planning system comprised of a plurality of planning computers that each execute a travel planning application that calculates the answers.

16. The method of claim 1 wherein the travel planning system is comprised of a plurality of planning computers that each execute a travel planning application that calculates the answers and a query distributor system coupled to a client system that is the source of the travel query and the computer.

17. A method comprising:

dividing by one or more computers a travel query into sub-queries according to a determined optimal division of the query for execution by a travel planning system to return answers that satisfy the travel query;

with the determined optimal division based on cost functions to arrive at a set of sub-queries that would balance work performed by the sub-queries through selecting values of terms in the cost functions.

19. The method of claim 17 wherein the sub queries are optimized by to control a number of computers used to process the sub-queries by assigning an absolute upper bound on the number of sub-queries for a query and assigning a base cost to every sub-query regardless of its size.

20. The method of claim 17 wherein the cost functions include estimates of query processing complexity including determining presence of a Saturday-night stay or advanced purchase requirement.

21. The method of claim 17 wherein the sub-queries are provided with multi-day ranges and multi-location sets.

22. The method of claim 17 wherein the sub-queries do not overlap.

18. A method comprises:

receiving by a computer system a travel planning query;

executing by the computer system a process to determine an optimal division of the travel query for execution by a travel planning system, the computer system dividing the travel query into sub-queries according to the determined optimal division of the query for execution of the sub-queries by the travel planning system to return answers that satisfy the travel query, with the process to determine the optimal division using cost functions to arrive at a set of sub-queries that would balance work performed by the sub-queries through selecting values of terms in the cost functions.

23. A system comprising:

a query distributor computer configured to;

receive a travel planning query including trip information including time of departure and origin and destination information from a client system;

divide the travel query into sub-queries for execution by a travel planning system the sub-queries divided according to a criterion selected from the group consisting of;

destination airport, outbound departure time, outbound and return departure times, airline, fares booking codes, cabin classes, carriers, and flight combinations;

receive answers in response to each of the sub-queries;

merge the received answers to return answers that satisfy the travel planning query.

24. The system of claim 23 wherein dividing of the travel planning query further takes query difficulty into account, by determining whether the travel planning query comprises presence of a Saturday-night stay or advanced purchase requirement, the system is further configured to:

vary the number of sub-queries by the determined query difficulty.

25. The system of claim 23 further comprising plural computers configured to:

concurrently execute the sub queries on the plural computers, with the computers configured to;

calculate by each of the plural computers the answers based on the selected criterion, the trip information in the sub-query.

26. The system of claim 23 wherein the system is part of a travel planning system, the system further configured to:

annotate the travel planning query with a total number of sub-queries;

assign an index to each a sub-query; and

execute the sub-queries on the plural computers that are part of the travel planning system, with plural computers configured to;

calculate the answers by applying a travel planning application to data to form the answers.

27. The system of claim 24 wherein taking query difficulty into account comprises taking system load into account.

28. The system of claim 24 wherein taking query difficulty into account comprises varying the number of sub-queries by system load.

29. The system of claim 23 further configured to:

monitor loading of the computing resources;

adjust parameters used in dividing the query into sub-queries to maximize the resources used without exceeding the available resources.

30. A computer program product tangibly embodied on a computer readable storage medium, the computer program product comprises instructions for causing a computer to:

receive a travel planning query including trip information including time of departure and origin and destination information from a client system;

divide the travel query into sub-queries for execution by a travel planning system the sub-queries divided according to a criterion selected from the group consisting of;

destination airport, outbound departure time, outbound and return departure times, airline, fares booking codes, cabin classes, carriers, and flight combinations;

receive answers in response to each of the sub-queries;

merge the received answers to return answers that satisfy the travel planning query.

32. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a time range.

31. The computer program product of claim 32 wherein the travel query includes an input specification of origins and destinations and time range for different parts of a trip.

33. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a pair of time ranges.

34. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a set of locations.

35. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to both a time range and a set of locations.

36. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a set of flight combinations.

37. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a set of fares or booking codes cabin classes.

38. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a set of carriers.

39. The computer program product of claim 32 wherein instructions to divide the query divide the query into the sub queries according to a cost of executing the sub-queries.

40. The computer program product of claim 32 wherein instructions to divide the query divide the query according to a determined optimal division of the query for execution by a travel planning system to return answers that satisfy the travel query.

42. The computer program product of claim 32 wherein instructions to divide comprises instructions to:

determining presence of a Saturday-night stay or advanced purchase requirement to ascertain query difficulty; and

vary the number of sub-queries by query difficulty.

43. The computer program product of claim 32 wherein instructions to divide include instructions that execute cost functions to balance system load during execution of the sub-queries

41. A computer program product residing on a computer readable medium comprises instructions for causing a computer to:

receive a travel planning query including trip information including time of departure and origin and destination information from a client system;

divide the travel query into sub-queries for execution by a travel planning system the sub-queries divided according to a criterion selected from the group consisting of;

destination airport, outbound departure time, outbound and return departure times, airline, fares booking codes, cabin classes, carriers, and flight combinations and based on query difficulty, by determining whether the travel planning query comprises presence of a Saturday-night stay or advanced purchase requirement;

receive answers in response to each of the sub-queries;

merge the received answers to return answers that satisfy the travel planning query.