Query caching for travel planning systems

• US 7,840,587 B2
• Filed: 06/06/2003
• Issued: 11/23/2010
• Est. Priority Date: 06/06/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Boyan, Justin A., Demarcken, Carl G.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Syed; Farhan M
• Application Number:
  US10/456,980
• Publication Number:
  US 20040249798A1
• Time in Patent Office: 2,727 Days
• Field of Search: 707/2, 705/5, 705/6
• US Class Current: 707/768
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 50/14 Travel agencies

Abstract

A query cache for travel planning includes a cache database that stores query results and a cache test mechanism that receives a travel planning query and uses the query to find a result in the cache database and if a result is found returns the result, the result including a set of answers each answer in the set having a flight and a fare useable with the flight.

Claims

1. A method for testing freshness of query results in a travel planning query cache comprising:

retrieving from a cache database a result comprising a set of answers, each answer including a flight and a fare usable with the flight, in response to a travel planning query;

testing the retrieved result to determine whether at least one answer in the result is stale or insufficiently fresh to be returned as an answer to the query, with testing using the travel planning query, the retrieved cached result and age of the retrieved cached result to determine whether answers in the retrieved cache result are stale or insufficiently fresh to return the result to a user; and

if at least one of the answers in the retrieved cache result is stale,

sending the travel planning query to a travel planning system; and

storing a result from execution of the travel planning query in the cache database, with the result comprising a set of answers, each answer including a flight and a fare usable with the flight.

2. The method of claim 1 wherein testing staleness uses statistical tests based on previously tabulated probabilities of staleness.

3. The method of claim 1 wherein testing staleness separately tests whether cached answers are valid and whether better answers are likely to exist.

5. The method of claim 1 wherein testing validity of cached answers comprises:

testing staleness by proportion or number of invalid answers.

6. The method of claim 5 wherein only a subset of the cached answers are tested for validity to determine whether the cached result is stale.

7. The method of claim 6 wherein testing validity of cached answers comprises:

testing whether flights, fares or availability in key markets have changed.

8. The method of claim 1 wherein testing validity of cached answers comprises:

testing whether flights, fares or availability in key markets have changed.

9. The method of claim 1 wherein testing validity of cached answers comprises:

testing whether answer components remain valid by examining current contents of travel database.

10. The method of claim 1 wherein testing validity of cached answers comprises:

testing validity of cached answers by re-querying using the travel planning query.

11. The method of claim 1 wherein testing validity of cached answers comprises:

testing validity of cached answers by re-querying using flight pricing queries.

12. The method of claim 1 wherein, testing staleness of the at least one cached answers comprises:

performing a shallow query and comparing resulting answers with the cached results.

4. The method of 1 further comprising:

testing of validity of cached result by testing validity of cached answers that comprise the cached result.

13. A computer program product residing on a computer readable medium for testing freshness of query results in a travel planning query cache comprises instructions for causing a computer to:

retrieve from a cache database a result comprising a set of answers, each answer including a flight and a fare usable with the flight, in response to a travel planning query;

test the retrieved result to determine whether at least one answer in the result is stale or insufficiently fresh to be returned as an answer to the travel planning query, with the instructions to test using the travel planning query, the retrieved cached result and age of the retrieved cached result to determine whether answers in the retrieved cache result are stale or insufficiently fresh to return the result to a user; and

if at least one of the answers is stale or insufficiently fresh,

send the travel planning query to a travel planning system; and

store a result from execution of the travel planning query in the cache database, the result comprising a set of answers, each answer including a flight and a fare usable with the flight.

14. The computer program product of claim 13 wherein instructions to test the result for staleness uses statistical tests based on previously tabulated probabilities of staleness.

15. The computer program product of claim 13 wherein instructions to test the result for staleness separately tests whether cached answers are valid and whether better answers are likely to exist.

16. The computer program product of claim 13 further comprising instructions to:

test validity of cached result by testing validity of cached answers that comprise the cached result.

17. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

test staleness by proportion or number of invalid answers.

18. The computer program product of claim 17 wherein only a subset of the cached answers are tested for validity to determine whether the cached result is stale.

19. The computer program product of claim 18 wherein instructions to test validity of cached answers comprises instructions to:

test whether flights, fares or availability in key markets have changed.

20. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

test whether flights, fares or availability in key markets have changed.

21. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

test whether answer components remain valid by examining current contents of travel database.

22. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

test validity of cached answers by re-querying.

23. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

test validity of cached answers by re-querying using flight pricing queries.

24. The computer program product of claim 13 wherein instructions to test validity of cached answers comprises instructions to:

perform a shallow query and comparing resulting answers with the cached results.

25. A travel planning system comprises:

a cache database, storing results comprising a set of answers to travel planning queries, each answer including a flight and a fare usable with the flight; and

a computing system executing;

a management process that retrieves cached results from the cache database in response to a travel planning query,

tests the retrieved cached result to determine whether at least one answer in the result is stale or insufficiently fresh to be returned as an answer to the query, with the management process testing validity of cached answers by determining staleness according to a proportion or number of invalid answers in the retrieved result exceeding a pre-determined threshold; and

if at least some of the answers are stale or insufficiently fresh, and the threshold is exceeded,

send the travel planning query to a travel planning system; and

store a result from execution of the travel planning query in the cache database, the result comprising a set of answers, each answer including a flight and a fare usable with the flight.

26. The travel planning query cache of claim 25 wherein the management process tests the result for staleness using the query, cached result and age of the cached result to determine whether the result is stale or sufficiently fresh to be returned to a user.

27. The travel planning query cache of claim 25 wherein the management process tests the result for staleness using statistical tests based on previously tabulated probabilities of staleness.

28. The travel planning query cache of claim 25 wherein the management process tests the results for staleness separately, and tests whether cached answers are valid and whether better answers are likely to exist.

29. The travel planning query cache of claim 25 wherein the management process further tests validity of cached result by testing validity of cached answers that comprise the cached result.

30. The travel planning query cache of claim 25 wherein the management process only tests a subset of the cached answers for validity to determine whether the cached result is stale.

31. The travel planning query cache of claim 30 wherein the management process tests validity of cached answers by testing whether flights, fares or availability in key markets have changed.

32. The travel planning query cache of claim 25 wherein the management process tests validity of cached answers by testing whether flights, fares or availability in key markets have changed.

33. The travel planning query cache of claim 25 wherein the management process tests validity of cached answers by testing whether answer components remain valid by examining current contents of travel database.

34. The travel planning query cache of claim 25 wherein the management process tests validity of cached answers by testing validity of cached answers by re-querying.

35. The travel planning query cache of claim 25 wherein the management process tests validity of cached answers by testing validity of cached answers by re-querying using flight pricing queries.

36. The travel planning query cache of claim 25 wherein the management process tests validity of cached answers by performing a shallow query and comparing resulting answers with the cached results.