Method, system, and computer program product for interfacing with information sources

• US 7,668,740 B1
• Filed: 09/22/2000
• Issued: 02/23/2010
• Est. Priority Date: 09/22/2000
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Galperin, Gregory R., Baggett, David M.
• Primary Examiner(s): Hayes; John W
• Assistant Examiner(s): CAMPBELL, SHANNON S
• Application Number:
  US09/667,235
• Time in Patent Office: 3,441 Days
• Field of Search: 705/1, 705/5, 705/6, 705/7, 705/10, 705/26, 705/27, 711/118, 711/122, 711/130, 711/137, 711/216, 707/3, 707/5, 707/1, 345/557
• US Class Current: 705/5
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

A method, system and computer program product for interfacing between information requesters and information sources. In an embodiment, information is obtained from one or more information sources in response to client requests. In an embodiment, information received from information sources is cached for future use, such as for future client requests. In a caching embodiment, information can also be received by monitoring traffic between an information source and a third party, and/or by proactively querying the information sources. Proactive queries can be generated to populate a cache and/or to update presently cached information. In a caching embodiment, the invention includes methods for determining whether to respond to a request for information out-of-cache and/or with real-time information from an information source. In an embodiment, the invention interfaces with airline availability information sources. The invention also includes, without limitation, methods for interfacing with information sources through proxies, methods for ordering and prioritizing queries, methods for processing queries in a distributed architecture, and time-out features.

Claims

1. A method, comprising:

ordering records of airline flights based on a combination of factors including age of cached flight availability information associated with at least a portion of the records and time-to-departure;

querying one or more airline information sources for flight availability information corresponding to the records in accordance with the ordering; and

caching flight availability information received from the one or more airline information sources;

wherein the ordering, the querying, and the caching are performed within a suitably programmed computer system.

2. The method of claim 1, wherein the ordering includes assigning higher priority to records for which flight availability information is not cached.

3. The method of claim 1, wherein the querying includes omitting records from the querying for which cached flight availability information is newer than a threshold age.

4. The method of claim 1, further including re-ordering the records in response to a change in the time-to-departure corresponding to a record.

5. The method of claim 1, wherein:

the ordering includes assigning higher priority to records for which flight availability information is not cached;

the querying includes omitting records from the querying for which cached flight availability information is newer than a threshold age; and

the method further includes re-ordering the records in response to a change in the time-to-departure corresponding to a record.

6. The method of claim 1, wherein the factors include a market.

7. The method of claim 1, wherein the factors include one or more of an origination location and a destination location.

8. The method of claim 1, wherein the factors include one or more a holiday and an event.

9. The method of claim 1, wherein the factors include a flight frequency.

10. The method of claim 1, wherein the factors include a frequency of change of availability.

11. The method of claim 1, wherein the factors include a transportation equipment type.

12. The method of claim 1, wherein the factors include a cached flight availability count associated with a record.

13. The method of claim 1, wherein the ordering includes:

encoding the combination of factors into a mathematical function that assigns a numerical priority value to each of the records.

14. The method of claim 1, wherein the ordering includes:

associating the records with one of a plurality of buckets based on a first set of one or more of the factors;

associating each of the buckets with a corresponding update interval; and

ordering records within the buckets based on a second set of one or more of the factors;

wherein the querying includes querying the one or more airline information sources for flight availability information corresponding to the records in accordance with the bucket update intervals and the ordering of the records within the buckets.

15. The method of claim 14, wherein the first set of one or more factors includes time-to-departure.

16. The method of claim 15, further including re-assigning a record from a first bucket to a second bucket in response to a change in the time-to-departure corresponding to the record.

17. The method of claim 14, wherein the second set of one or more factors includes age of cached flight availability information.

18. The method of claim 17, wherein the ordering of the records within the buckets includes assigning higher priority to records for which flight availability information is not cached.

19. The method of claim 17, wherein the querying includes generating queries for records within a bucket for which cached flight availability information is older than a threshold age, in accordance with the ordering of the records within the bucket.

20. The method of claim 14, wherein the first set of one or more factors includes time-to-departure and the second set of one or more factors includes age of cached flight availability information, the method further including:

re-assigning a record from a first bucket to a second bucket in response to a change in the time-to-departure corresponding to the record;

wherein the ordering of the records within the buckets includes assigning higher priority to records for which flight availability information is not presently cached; and

wherein the querying includes generating queries for records within a bucket for which cached flight availability information is older than a threshold age and for which flight availability information is not presently cached.

21. The method of claim 14, further including:

associating the buckets with one of a plurality of bucket groups;

wherein the querying includes alternately querying with respect to a first number of records from a first bucket group and with respect to a second number of records from a second bucket group.

22. The method of claim 21, further including:

associating a first set of the buckets with a first market and a second set of the buckets with a second market.

23. The method of claim 1, wherein the ordering includes:

associating buckets with corresponding time-to-departure ranges;

associating the records with the buckets based at least on time-to-departures;

ordering the buckets according at least to the corresponding time-to-departure ranges;

ordering records within the buckets based at least on age of cached flight availability information; and

re-bucketing the records to accommodate changes to the time-to-departures;

wherein the querying includes selecting a bucket according to the ordering of the buckets and querying the one or more airline information sources for flight availability information corresponding to records within the selected bucket, omitting querying with respect to records for which flight availability information is presently cached and newer than a threshold age.

24. The method of claim 1, further including:

filtering a record from the querying for which a corresponding fare is unavailable.

25. The method of claim 1, further including:

filtering a record from the querying for which requesters are not expected to request flight availability information.

26. The method of claim 1, wherein the caching includes:

hashing information from the flight records; and

storing the flight availability information at hash indexes corresponding to the hashed flight records information.

27. A method, comprising:

ordering records of airline flights based at least in part on a cached number of available seats associated with one or more of the records;

querying one or more airline information sources for flight availability information corresponding to the records in accordance with the ordering; and

caching flight availability information received from the one or more airline information sources;

wherein the ordering, the querying, and the caching are performed within a suitably programmed computer system.

28. A method, comprising:

receiving first and second requests for flight availability information from corresponding first and second requesters;

separating each of the first and second requests into a plurality of sub-queries;

prioritizing the first requestor sub-queries with respect to one another;

prioritizing the second requestor sub-queries with respect to one another;

ordering the first requestor sub-queries with respect to the second requestor sub-queries according to corresponding times of receipt, including resolving priority disputes between simultaneously received first and second requests so that higher priority sub-queries of the first and second requests are processed before lower priority sub-queries of the first and second requests; and

processing the sub-queries according to the associated priorities;

wherein the receiving, the separating, the prioritizing of the first and second requestor sub-queries, and the ordering, are performed within a suitably programmed computer system.

29. The method of claim 28, further including:

placing the requestor sub-queries in a query priority queue;

generating proactive queries for flight availability information independent of the requestor requests; and

adding the proactive queries to the query priority queue at lower priorities than the requestor sub-queries.

30. A method, comprising:

converting scheduled airline flight times to approximate flight times;

hashing records of the airline flights, including the approximate flight times;

storing the scheduled flight times at corresponding hash indexes;

receiving a request for flight availability information, including a requested flight time;

converting the requested flight time to an approximate requested flight time;

hashing at least the approximate requested flight time to generate a request hash index; and

returning information from the request hash index including the corresponding scheduled flight time;

wherein the convertings, the hashings, the storing, and the returning, are performed within a suitably programmed computer system.

31. The method of claim 30, wherein:

the storing includes storing the scheduled flight times and associated flight availability information at the corresponding hash indexes; and

the returning of the information from the request hash index includes returning the scheduled flight time and the corresponding flight availability information.

32. The method of claim 30, wherein the converting the scheduled airline flight times to approximate flight times includes rounding down the scheduled times.

33. The method of claim 30, wherein the converting the scheduled airline flight times to approximate flight times includes rounding up the scheduled times.

34. The method of claim 30, wherein:

the converting the scheduled airline flight times to approximate flight times includes rounding down the scheduled times and rounding up the scheduled times;

the hashing of records of the airline flights includes hashing each of the rounded up flight times and hashing the rounded down flight times; and

the storing includes storing the scheduled flight times and associated flight availability information at hash indexes corresponding to the rounded up flight times and at hash indexes corresponding to the rounded down flight times.

35. The method of claim 30, wherein the converting the scheduled airline flight times includes converting scheduled departure times to approximate departure times.

36. The method of claim 30, wherein the converting the scheduled airline flight times includes converting scheduled arrival times to approximate arrival times.

37. A method, comprising:

storing records of airline flights; and

caching flight availability information received from one or more airline information sources, including sharing a cached availability count record between a plurality of the airline flight records;

wherein the storing and the caching are performed within a suitably programmed computer system.

38. The method of claim 37, further including:

associating a plurality of the airline flight records as a married flight record; and

sharing a cached availability count record between the married flight record and another flight record.

39. A method, comprising:

caching flight availability information;

receiving a request for flight availability information;

querying an airline information source for flight availability information in response to the request; and

searching the cached flight availability information for the requested flight availability information after waiting a pre-determined time for a response from the airline information source;

wherein the caching, the receiving, the querying, and the searching are performed within a suitably programmed computer system.

40. A method, comprising:

monitoring flight availability information traffic between an airline information source and one or more clients of the airline information source;

caching at least a portion of the monitored flight availability information traffic;

determining a likelihood that flight availability information will be received within a period of time by the monitoring;

generating proactive queries for flight availability information not likely to be received within the period of time; and

caching information returned in response to the proactive queries;

wherein the monitoring, the cachings, the determining, and the generating are performed within a suitably programmed computer system.

41. A method, comprising:

identifying one or more factors associated with flight availability information;

learning a relationship between historical values for the one or more factors and historical values for flight availability information;

generating a function according to the learned relationship;

receiving a request for flight availability information;

providing values for the one or more factors corresponding to the request to the function; and

returning predicted flight availability information from the function;

wherein the identifying, the learning, the generating, the receiving, the providing, and the returning are performed within a suitably programmed computer system.

42. The method according to claim 41, further including:

determining to respond to the request with at least one,

real-time flight availability information,

cached flight availability information, and

predicted flight availability information.