Efficient indexing and caching infrastructure for metasearch

• US 9,298,837 B2
• Filed: 11/08/2012
• Issued: 03/29/2016
• Est. Priority Date: 11/10/2011
• Status: Active Grant

• Current Assignee: Lola 77, Inc.
• Original Assignee: Room 77, Inc. (Lexyl Travel Technologies LLC)
• Inventors: Oztekin, Bilgehan Uygar, Webster, Ian, Chen, Jie, Cho, Sungsoon, Edelman, Nicholas, Yang, Calvin Cheng
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US13/672,622
• Publication Number:
  US 20130124237A1
• Time in Patent Office: 1,237 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

Techniques are provided for a metasearch infrastructure. The metasearch infrastructure supports one or more of the following: hotel matching, backend support of user queries, frontend support for user queries, a cache layer that groups or organizes cached data in storage based on hotel location, scoring and ranking on the client side, experiments and rankers, duplicate booking prevention, blacklisting hotels, and indexing that utilizes a document-independent data structure to store index values.

Claims

1. A computer-implemented method comprising:

receiving a first query from a client over a network;

identifying one or more first terms associated with the first query;

based on a first term of the one or more first terms, identifying first location data that comprises an address of an entry in a first data structure or an offset into the first data structure;

using the first location data to identify one or more first entries in the first data structure, wherein a first entry of the one or more first entries includes a first index value;

using the first index value to identify a first set of one or more values in a second data structure that is different than the first data structure;

wherein the first data structure comprises a plurality of entries, each of which contains an index value into the second data structure;

using the first set of one or more values in the second data structure to identify a first location within a first document;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein identifying the first location data based on the first term of the one or more first terms comprises:

based on the first term, identifying one or more first hotel identifiers that are associated with the first term;

based on a first hotel identifier of the one or more first hotel identifiers, identifying the first location data that is associated with the first hotel identifier.

3. The method of claim 2, wherein identifying the first location data that is associated with the first hotel identifier based on the first term of the one or more first terms comprises:

based on the first term, identifying one or more first sections that are associated with the first term;

based on a first section of the one or more first hotel identifiers, identifying the first location data that is associated with the first section.

4. The method of claim 1, further comprising:

receiving a second query that is different than the first query;

identifying one or more second terms associated with the second query;

based on a second term of the one or more second terms, identifying second location data;

using the second location data to identify one or more second entries in the first data structure, wherein a second entry of the one or more second entries includes the first index value;

using the first index value to identify the first set of one or more values in the second data structure;

using the first set of one or more values in the second data structure to identify a location within a second document that is different than the first document.

5. The method of claim 1, further comprising, after identifying the first location within the first document:

generating, based on the first location, a snippet of text from the first document as a response to the first query;

sending, to the client over the network, the snippet of text.

6. The method of claim 1, further comprising, after identifying the first location within the first document:

generating, based on text within the first document, score data that is associated with the first document;

sending, to the client, ranking data that is associated with the first document and that is based on the score data.

7. The method of claim 1, further comprising, in response to receiving the first query:

identifying a plurality of hotel identifiers;

generating, based on a first mapping and a first subset of the plurality of hotel identifiers, a second plurality of hotel identifiers;

generating a first request that identifies the second plurality of hotel identifiers;

sending the first request to a first source;

generating, based on the first mapping and a second subset of the plurality of hotel identifiers, a third plurality of hotel identifiers;

generating, based on a second mapping and the third plurality of hotel identifiers, a plurality of location identifiers;

generating a second request that identifies the plurality of location identifiers;

sending the second request to a second source that is different than the first source.

8. The method of claim 1, further comprising:

generating a booking identifier and sending the booking identifier to the client;

receiving, from the client, a request to make a reservation at a particular hotel, wherein the request includes the booking identifier;

in response to receiving the request;

storing data that indicates a status of a booking request associated with the booking identifier, and

sending, to a source that is different than the client, the booking identifier and the request to make the reservation at the particular hotel.

9. The method of claim 1, further comprising:

organizing, in storage, information about a plurality of hotels based on location of each hotel of the plurality of hotels such that information about hotels that are geographically located near each other is physically stored together in the storage.

10. The method of claim 1, further comprising:

storing a first set of hotel data that identifies a first plurality of hotels and includes, for each hotel in the first plurality of hotels, a first plurality of attributes of said each hotel;

receiving, over a second network from a particular source, a second set of hotel data that identifies a second plurality of hotels and includes, for each hotel in the second plurality of hotels, a second plurality of attributes of said each hotel;

for a particular hotel in the second plurality of hotels;

performing a first comparison between (a) one or more attributes of the particular hotel and (b) one or more attributes of each hotel in a subset of the first plurality of hotels to identify a candidate set of hotels;

after identifying the candidate set of hotels, performing a second comparison between (c) one or more attributes of the particular hotel and (d) one or more attributes of each hotel in the candidate set of hotels to generate a score for each hotel in the candidate set of hotels; and

based on each generated score, storing data that indicates that the particular hotel matches a certain hotel in the candidate set of hotels.

11. One or more non-transitory storage media carrying instructions which, when executed by one or more processors, cause:

receiving a first query from a client over a network;

identifying one or more first terms associated with the first query;

based on a first term of the one or more first terms, identifying first location data that comprises an address of an entry in a first data structure or an offset into the first data structure;

using the first location data to identify one or more first entries in the first data structure, wherein a first entry of the one or more first entries includes a first index value;

using the first index value to identify a first set of one or more values in a second data structure that is different than the first data structure;

wherein the first data structure comprises a plurality of entries, each of which contains an index value into the second data structure;

using the first set of one or more values in the second data structure to identify a first location within a first document.

12. The one or more non-transitory storage media of claim 11, wherein identifying the first location data based on the first term of the one or more first terms comprises:

based on the first term, identifying one or more first hotel identifiers that are associated with the first term;

based on a first hotel identifier of the one or more first hotel identifiers, identifying the first location data that is associated with the first hotel identifier.

13. The one or more non-transitory storage media of claim 12, wherein identifying the first location data that is associated with the first hotel identifier based on the first term of the one or more first terms comprises:

based on the first term, identifying one or more first sections that are associated with the first term;

based on a first section of the one or more first hotel identifiers, identifying the first location data that is associated with the first section.

14. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause:

receiving a second query that is different than the first query;

identifying one or more second terms associated with the second query;

based on a second term of the one or more second terms, identifying second location data;

using the second location data to identify one or more second entries in the first data structure, wherein a second entry of the one or more second entries includes the first index value;

using the first index value to identify the first set of one or more values in the second data structure;

using the first set of one or more values in the second data structure to identify a location within a second document that is different than the first document.

15. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause, after identifying the first location within the first document:

generating, based on the first location, a snippet of text from the first document as a response to the first query;

sending, to the client over the network, the snippet of text.

16. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause, after identifying the first location within the first document:

generating, based on text within the first document, score data that is associated with the first document;

sending, to the client, ranking data that is associated with the first document and that is based on the score data.

17. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause, in response to receiving the first query:

identifying a plurality of hotel identifiers;

generating, based on a first mapping and a first subset of the plurality of hotel identifiers, a second plurality of hotel identifiers;

generating a first request that identifies the second plurality of hotel identifiers;

sending the first request to a first source;

generating, based on the first mapping and a second subset of the plurality of hotel identifiers, a third plurality of hotel identifiers;

generating, based on a second mapping and the third plurality of hotel identifiers, a plurality of location identifiers;

generating a second request that identifies the plurality of location identifiers;

sending the second request to a second source that is different than the first source.

18. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause:

generating a booking identifier and sending the booking identifier to the client;

receiving, from the client, a request to make a reservation at a particular hotel, wherein the request includes the booking identifier;

in response to receiving the request;

storing data that indicates a status of a booking request associated with the booking identifier, and

sending, to a source that is different than the client, the booking identifier and the request to make the reservation at the particular hotel.

19. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause:

organizing, in storage, information about a plurality of hotels based on location of each hotel of the plurality of hotels such that information about hotels that are geographically located near each other is physically stored together in the storage.

20. The one or more non-transitory storage media of claim 11, wherein the instructions, when executed by the one or more processors, cause:

storing a first set of hotel data that identifies a first plurality of hotels and includes, for each hotel in the first plurality of hotels, a first plurality of attributes of said each hotel;

receiving, over a second network from a particular source, a second set of hotel data that identifies a second plurality of hotels and includes, for each hotel in the second plurality of hotels, a second plurality of attributes of said each hotel;

for a particular hotel in the second plurality of hotels;

performing a first comparison between (a) one or more attributes of the particular hotel and (b) one or more attributes of each hotel in a subset of the first plurality of hotels to identify a candidate set of hotels;

after identifying the candidate set of hotels, performing a second comparison between (c) one or more attributes of the particular hotel and (d) one or more attributes of each hotel in the candidate set of hotels to generate a score for each hotel in the candidate set of hotels; and

based on each generated score, storing data that indicates that the particular hotel matches a certain hotel in the candidate set of hotels.