Query caching for travel planning systems

• US 20040249798A1
• Filed: 06/06/2003
• Published: 12/09/2004
• 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.
• Granted Patent: US 7,840,587 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 a result for a query from a cache database;

if a cached result is found,

testing the retrieved result to determine whether at least one answer in the result is stale or sufficiently fresh to be returned as an answer to the query, and if at least some of the answers are stale or if no result is found,

indicating a cache miss.

2. The method of claim 1 wherein testing the result for staleness uses 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.

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

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

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

testing staleness by proportion or number of invalid answers.

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

8. The method of claim 7 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 flights, fares or availability in key markets have changed.

10. 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.

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

testing validity of cached answers by re-querying.

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

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

13. 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.

5. The method of 1 further comprising:

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

14. 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 a result for a query from a cache database;

if a cached result is found,

test the retrieved result to determine whether at least one answer in the result is stale or sufficiently fresh to be returned as an answer to the query, and if at least some of the answers are stale or if no result is found,

indicate a cache miss.

15. The computer program product of claim 14 wherein instructions to test the result for staleness uses the query, cached result and age of the cached result to determine whether the result is stale or sufficiently fresh to be returned to the user.

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

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

18. The computer program product of claim 14 further comprising instructions to:

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

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

test staleness by proportion or number of invalid answers.

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

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

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

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

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

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

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

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

test validity of cached answers by re-querying.

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

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

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

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

27. A travel planning query cache comprises:

a cache database; and

a management process that retrieves cached results from the cache database in response to a user query and if a retrieved cached result is found that satisfies the query,

tests the retrieved cached result to determine whether at least one answer in the result is stale or sufficiently fresh to be returned as an answer to the query, and if at least some of the answers are stale or if no result is found,

indicates a cache miss.

28. The travel planning query cache of claim 27 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.

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

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

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

32. The travel planning query cache of claim 27 wherein the management process tests validity of cached answers by testing staleness by proportion or number of invalid answers.

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

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

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

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

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

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

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