Predicting categorized completions of a partial search term

• US 9,690,858 B1
• Filed: 02/14/2014
• Issued: 06/27/2017
• Est. Priority Date: 02/14/2014
• Status: Active Grant

• Current Assignee: Priceline.com LLC (Booking Holdings, Inc., fka Priceline Group Inc.)
• Original Assignee: Priceline.com LLC (Booking Holdings, Inc., fka Priceline Group Inc.)
• Inventors: Taylor, Jonathan, Diliberto, Michael, Caine, John, Gonzalez, Michael P., Chen, Jim Jianqiang, Poddar, Amit
• Primary Examiner(s): Gortayo, Dangelino
• Application Number:
  US14/181,498
• Time in Patent Office: 1,229 Days
• Field of Search: 707767, 707708, 707721, 707723, 707759, 707765, 707768, 707771
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

In an embodiment, a method comprises receiving, from a client computer, a first request comprising a partial search term for an item, wherein the partial search term comprises one or more characters; selecting a first plurality of predicted completions of the partial search term based, at least in part, on the partial search term, wherein each predicted completion in the first plurality of predicted completions is associated with a category of a set of categories; determining an order of each category in the set of categories; ordering the first plurality of predicted completions based, at least in part, on a position, in the order, of each category that is associated with each predicted completion in the first plurality of predicted completions; sending the first plurality of predicted completions to the client computer.

Claims

1. A method comprising:

receiving, from a client computer, a first request comprising a partial search term for an item, wherein the partial search term comprises one or more characters;

selecting a first plurality of predicted completions of the partial search term based, at least in part, on the partial search term, wherein each predicted completion in the first plurality of predicted completions is associated with a category of a set of categories;

wherein the first plurality of predicted completions comprises;

a first set of categorized completions associated with a first category among the set of categories, and a second set of categorized completions associated with a second category among the set of categories;

determining a highest first selection ratio for the first set of categorized completions associated with the first category wherein the highest first selection ratio is greater than a first threshold value based, at least in part, on a selection ratio for the partial search term and the first set of categorized completions;

determining a highest second selection ratio for the second set of categorized completions associated with the second category wherein the highest second selection ratio is greater than a second threshold value based, at least in part, on a selection ratio for the partial search term and the second set of categorized completions;

ranking the highest first selection ratio and the highest second selection ratio;

determining an order of each category in the set of categories based, in part, on ranking the highest first selection ratio and the highest second selection ratio;

ordering the first plurality of predicted completions based, at least in part, on a position, in the order, of each category that is associated with each predicted completion in the first plurality of predicted completions;

sending, to the client computer, the first plurality of predicted completions and data identifying the first set of categorized completions from the first plurality of predicted completions and the second set of categorized completions from the first plurality of predicted completions;

wherein the method is performed by one or more computers.

2. The method of claim 1 comprising:

collecting a first set of feedback data indicating one or more predicted completions were sent to one or more client computers in response to receiving the partial search term;

collecting a second set of feedback data indicating how many times each predicted selection of the one or more predicted completions that were sent to the one or more client computers in response to receiving the partial search term were selected;

calculating, periodically, a selection ratio for the partial search term and each predicted completion in a set of predicted completions based, at least in part, on the first set of feedback data and the second set of feedback data.

3. The method of claim 1 comprising:

determining a selection ratio for the partial search term and each predicted completion in a set of predicted completions based, at least in part, on a first count of instances in which the predicted completion is included in the first plurality of predicted completions that have been sent in response to previous requests comprising the partial search term, and a second count of instances in which the predicted completion is selected after receiving the first plurality of predicted completions;

selecting one or more predicted completions from the set of predicted completions based, at least in part, on the selection ratio of each predicted completion in the one or more predicted completions;

including, in the first plurality of predicted completions, the one or more predicted completions that are selected.

4. The method of claim 3 comprising:

ordering the particular predicted completion to be first in the first plurality of predicted completions and ordering each remaining predicted completion in the first plurality of predicted completions based, at least in part, on the order.

5. The method of claim 3 comprising for each predicted completion from the one or more predicted completions, determining the selection ratio is greater than or equal to a particular threshold value, and in response, adding the predicted completion to the first plurality of predicted completions.

6. The method of claim 3 comprising:

determining a highest first selection ratio for the first plurality of predicted completions that are associated with a first category of the set of categories;

determining a highest second selection ratio for the first plurality of predicted completions that are associated with a second category of the set of categories;

determining the highest first selection ratio is higher than the highest second selection ratio;

ordering the first category to be higher in the order than the second category.

7. The method of claim 1, wherein the first request specifies an item type of a plurality of item types, and the method comprising determining the order based on the item type.

8. The method of claim 1 comprising:

maintaining an alias mapping that maps one or more partial search terms to one or more aliases;

selecting an alias from the alias mapping based on the partial search term;

selecting the first plurality of predicted completions based, at least in part, on the alias.

9. The method of claim 1 comprising:

maintaining a first alias mapping that maps one or more partial search terms to one or more first aliases;

maintaining a second alias mapping that maps the one or more partial search terms to one or more second aliases;

receiving the first request, wherein the first request specifies a first item type;

selecting the first alias mapping based on the first item type;

selecting a first alias from the first alias mapping based on the partial search term;

selecting the first plurality of predicted completions based, at least in part, on the first alias;

receiving a second request comprising the partial search term, wherein the second request specifies a second item type;

selecting the second alias mapping based on the second item type;

selecting a second alias from the second alias mapping based on the partial search term, wherein the first alias is different than the second alias;

selecting a second plurality of predicted completions based, at least in part, on the second alias.

10. The method of claim 1 comprising:

determining a first selection ratio for the partial search term, a first item type, and each predicted completion in a set of predicted completions based, at least in part, on a first count of instances in which the predicted completion is included in the first plurality of predicted completions sent in response to previous requests comprising the partial search term and the first item type, and a second count of instances in which the predicted completion is selected by a user after receiving the first plurality of predicted completions;

receiving the first request, wherein the first request specifies the first item type;

selecting one or more first predicted completions from the set of predicted completions to include in the first plurality of predicted completions based, at least in part, on the first selection ratio of each predicted completion in the one or more first predicted completions;

determining a second selection ratio for the partial search term, a second item type, and each predicted completion in the set of predicted completions based, at least in part, on a third count of instances in which the predicted completion is included in a second plurality of predicted completions sent in response to previous requests comprising the partial search term and the second item type, and a fourth count of instances in which the predicted completion is selected by a user after receiving the second plurality of predicted completions;

receiving a second request, wherein the second request specifies the second item type;

selecting one or more second predicted completions from the set of predicted completions to include in the second plurality of predicted completions based, at least in part, on the second selection ratio of each predicted completion in the one or more second predicted completions.

11. The method of claim 1 comprising:

receiving, on the client computer, the first plurality of predicted completions;

causing displaying of at least a subset of the first plurality of predicted completions on a display.

12. The method of claim 1 comprising causing to present, on a display, a user interface with the first plurality of predicted completions, wherein the user interface identifies which predicted completions of the first plurality of predicted completions are in the first set of categorized completions and which predicted completions of the first plurality of predicted completions are in the second set of categorized completions.

13. A system comprising:

a processor;

a memory;

a database;

a prediction module configured to;

receive, from a client computer, a first request comprising a partial search term for an item, wherein the partial search term comprises one or more characters;

select, from the database, a first plurality of predicted completions of the partial search term based, at least in part, on the partial search term, wherein each predicted completion in the first plurality of predicted completions is associated with a category of a set of categories;

wherein the first plurality of predicted completions comprises;

a first set of categorized completions associated with a first category among the set of categories, and a second set of categorized completions associated with a second category among the set of categories;

determine a highest first selection ratio for the first set of categorized completions associated with the first category wherein the highest first selection ratio is greater than a first threshold value based, at least in part, on a selection ratio for the partial search term and the first set of categorized completions;

determine a highest second selection ratio for the second set of categorized completions associated with the second category wherein the highest second selection ratio is greater than a second threshold value based, at least in part, on a selection ratio for the partial search term and the second set of categorized completions;

rank the highest first selection ratio and the highest second selection ratio;

determine an order of each category in the set of categories based, in part, on ranking the highest first selection ratio and the highest second selection ratio;

order the first plurality of predicted completions based, at least in part, on a position, in the order, of each category that is associated with each predicted completion in the first plurality of predicted completions;

send, to the client computer, the first plurality of predicted completions and data identify the first set of categorized completions from the first plurality of predicted completions and the second set of categorized completions from the first plurality of predicted completions.

14. The system of claim 13, wherein the prediction module is configured to:

store, in the database, a first set of feedback data indicating one or more predicted completions were sent to one or more client computers in response to receiving the partial search term;

store, in the database, a second set of feedback data indicating how many times each predicted selection of the one or more predicted completions that were sent to the one or more client computers in response to receiving the partial search term were selected;

calculate, periodically, a selection ratio for the partial search term and each predicted completion in a set of predicted completions based, at least in part, on the first set of feedback data and the second set of feedback data.

15. The system of claim 13, wherein the prediction module is configured to:

determine a selection ratio for the partial search term and each predicted completion in a set of predicted completions based, at least in part, on a first count of instances in which the predicted completion is included in the first plurality of predicted completions that have been sent in response to previous requests comprising the partial search term, and a second count of instances in which the predicted completion is selected after receiving the first plurality of predicted completions;

select one or more predicted completions from the set of predicted completions based, at least in part, on the selection ratio of each predicted completion in the one or more predicted completions;

include, in the first plurality of predicted completions, the one or more predicted completions that are selected.

16. The system of claim 15, wherein the prediction module is configured to:

order the particular predicted completion to be first in the first plurality of predicted completions and order each remaining predicted completion in the first plurality of predicted completions based, at least in part, on the order.

17. The system of claim 15, wherein the prediction module is configured to, for each predicted completion from the one or more predicted completions, determine the selection ratio is greater than or equal to a particular threshold value, and in response, add the predicted completion to the first plurality of predicted completions.

18. The system of claim 15, wherein the prediction module is configured to:

determine a highest first selection ratio for the first plurality of predicted completions that are associated with a first category of the set of categories;

determine a highest second selection ratio for the first plurality of predicted completions that are associated with a second category of the set of categories;

determine the highest first selection ratio is higher than the highest second selection ratio;

order the first category to be higher in the order than the second category.

19. The system of claim 13, wherein the first request specifies an item type of a plurality of item types, and the prediction module is configured to determine the order based on the item type.

20. The system of claim 13, wherein:

the database is configured to maintain an alias mapping that maps one or more partial search terms to one or more aliases;

the prediction module is configured to;

select an alias from the alias mapping based on the partial search term;

select the first plurality of predicted completions based, at least in part, on the alias.

21. The system of claim 13, wherein:

the database is configured to;

maintain a first alias mapping that maps one or more partial search terms to one or more first aliases;

maintain a second alias mapping that maps the one or more partial search terms to one or more second aliases;

the prediction module is configured to;

receive the first request, wherein the first request specifies a first item type;

select the first alias mapping based on the first item type;

select a first alias from the first alias mapping based on the partial search term;

select the first plurality of predicted completions based, at least in part, on the first alias;

receive a second request comprising the partial search term, wherein the second request specifies a second item type;

select the second alias mapping based on the second item type;

select a second alias from the second alias mapping based on the partial search term, wherein the first alias is different than the second alias;

select a second plurality of predicted completions based, at least in part, on the second alias.

22. The system of claim 13, wherein the prediction module is configured to:

determine a first selection ratio for the partial search term, a first item type, and each predicted completion in a set of predicted completions based, at least in part, on a first count of instances in which the predicted completion is included in the first plurality of predicted completions sent in response to previous requests comprising the partial search term and the first item type, and a second count of instances in which the predicted completion is selected by a user after receiving the first plurality of predicted completions;

receive the first request, wherein the first request specifies the first item type;

select one or more first predicted completions from the set of predicted completions to include in the first plurality of predicted completions based, at least in part, on the first selection ratio of each predicted completion in the one or more first predicted completions;

determine a second selection ratio for the partial search term, a second item type, and each predicted completion in the set of predicted completions based, at least in part, on a third count of instances in which the predicted completion is included in a second plurality of predicted completions sent in response to previous requests comprising the partial search term and the second item type, and a fourth count of instances in which the predicted completion is selected by a user after receiving the second plurality of predicted completions;

receive a second request, wherein the second request specifies the second item type;

select one or more second predicted completions from the set of predicted completions to include in the second plurality of predicted completions based, at least in part, on the second selection ratio of each predicted completion in the one or more second predicted completions.

23. The system of claim 13, wherein the prediction module is configured to:

receive, on the client computer, the first plurality of predicted completions;

cause display of at least a subset of the first plurality of predicted completions on a display.

24. The system of claim 13, wherein the prediction module is configured to cause to present, on a display, a user interface with the first plurality of predicted completions, wherein the user interface identifies which predicted completions of the first plurality of predicted completions are in the first set of categorized completions and which predicted completions of the first plurality of predicted completions are in the second set of categorized completions.