ENFORCING CATEGORY DIVERSITY

• US 20150169573A1
• Filed: 10/04/2011
• Published: 06/18/2015
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yang, Ke, Arora, Neha, Yang, Zuguang
• Granted Patent: US 9,507,801 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for enforcing category diversity of points of interest (POIs). In one aspect, a method includes receiving a request to identify POIs, obtaining data identifying (i) POIs that satisfy the request, (ii) a category associated with each POI, and (iii) a non-scaled score associated with each POI, and ranking, for each category, the POIs based on the non-scaled scores. The method also includes scaling, for each of one or more categories, the non-scaled scores of the ranked POIs associated with the category, ranking the POIs using the scaled scores, for the POIs that are associated with the one or more categories, and the non-scaled scores, for the POIs that are not associated with the one or more categories, and providing data that identifies the POIs, as ranked according to the scaled and the non-scaled scores.

Claims

1. A computer-implemented method comprising:

receiving a request to identify points of interest (POIs) associated with a geographic location identified in the request;

obtaining data identifying (i) candidate points of interest (POIs) associated with the geographic location that satisfy the request, (ii) a respective category associated with each candidate POI, and (iii) a non-scaled score associated with each candidate POI;

scaling, for each of one or more particular categories and based on a respective number of candidate POIs associated with each of the one or more particular categories, the non-scaled scores of the candidate POIs associated with the one or more particular categories;

ranking the candidate POIs using (i) the scaled scores, for the candidate POIs that are associated with the one or more particular categories, and (ii) the non-scaled scores, for the candidate POIs that are not associated with the one or more particular categories; and

providing data that identifies two or more of the candidate POIs, as ranked according to the scaled scores and the non-scaled scores.

2. The method of claim 1, comprising:

selecting, as the one or more categories, one or more categories that are each associated with more than a predetermined number of candidate POIs.

6. The method of claim 1, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

increasing the respective non-scaled scores of one or more of the top n ranked candidate POIs.

7. The method of claim 1, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

leaving unchanged the non-scaled scores of one or more of the top n ranked candidate POIs.

8. The method of claim 1, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

decreasing the non-scaled scores of one or more of the top n ranked candidate POIs.

9. The method of claim 1, comprising dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a non-scaled score associated with a top ranked candidate POI of a different category.

10. The method of claim 1, comprising dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a quantity of the candidate POIs of the particular category identified in the data.

3-5. -5. (canceled)

11. A computer-readable storage device having stored thereon instructions, which, when executed by a computer, cause the computer to perform operations comprising:

receiving a request to identify points of interest (POIs) associated with a geographic location identified in the request;

obtaining data identifying (i) candidate points of interest (POIs) associated with the geographic location that satisfy the request, (ii) a respective category associated with each candidate POI, and (iii) a non-scaled score associated with each candidate POI;

scaling, for each of one or more particular categories and based on a respective number of candidate POIs associated with each of the one or more particular categories, the non-scaled scores of the candidate POIs associated with the one or more particular categories;

ranking the candidate POIs using (i) the scaled scores, for the candidate POIs that are associated with the one or more particular categories, and (ii) the non-scaled scores, for the candidate POIs that are not associated with the one or more particular categories; and

providing data that identifies two or more of the candidate POIs, as ranked according to the scaled scores and the non-scaled scores.

12. The medium of claim 11, wherein the operations comprise:

selecting, as the one or more categories, one or more categories that are each associated with more than a predetermined number of candidate POIs.

16. The medium of claim 11, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

increasing the respective non-scaled scores of one or more of the top n ranked candidate POIs.

17. The medium of claim 11, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

leaving unchanged the non-scaled scores of one or more of the top n ranked candidate POIs.

18. The medium of claim 11, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

decreasing the non-scaled scores of one or more of the top n ranked candidate POIs.

19. The medium of claim 11, wherein the operations comprise dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a non-scaled score associated with a top ranked candidate POI of a different category.

20. The medium of claim 11, wherein the operations comprise dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a quantity of the candidate POIs of the particular category identified in the data.

13-15. -15. (canceled)

21. A system comprising:

one or more computers; and

a computer-readable storage device having stored thereon instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving a request to identify points of interest (POIs) associated with a geographic location identified in the request;

obtaining data identifying (i) candidate points of interest (POIs) associated with the geographic location that satisfy the request, (ii) a respective category associated with each candidate POI, and (iii) a non-scaled score associated with each candidate POI;

scaling, for each of one or more particular categories and based on a respective number of candidate POIs associated with each of the one or more particular categories, the non-scaled scores of the candidate POIs associated with the one or more particular categories;

ranking the candidate POIs using (i) the scaled scores, for the candidate POIs that are associated with the one or more particular categories, and (ii) the non-scaled scores, for the candidate POIs that are not associated with the one or more particular categories; and

providing data that identifies two or more of the candidate POIs, as ranked according to the scaled scores and the non-scaled scores.

22. The system of claim 21, wherein the operations comprise:

selecting, as the one or more categories, one or more categories that are each associated with more than a predetermined number of candidate POIs.

26. The system of claim 21, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

increasing the respective non-scaled scores of one or more of the top n ranked candidate POIs.

27. The system of claim 21, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

leaving unchanged the non-scaled scores of one or more of the top n ranked candidate POIs.

28. The system of claim 21, wherein scaling the non-scaled scores of the candidate POIs associated with the one or more particular categories comprises:

for a category of the one or more particular categories;

selecting top n ranked candidates POIs associated with the category based on the non-scaled scores, wherein n is a positive integer that is less than or equal to a count of candidate POIs associated with the category; and

decreasing the non-scaled scores of one or more of the top n ranked candidate POIs.

29. The system of claim 21, wherein the operations comprise dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a non-scaled score associated with a top ranked candidate POI of a different category.

30. The system of claim 21, wherein the operations comprise dynamically determining a scaling factor to use to scale one or more non-scaled scores of the ranked, candidate POIs of a particular category based on a quantity of the candidate POIs of the particular category identified in the data.

23-25. -25. (canceled)

31. A computer-implemented method comprising:

receiving a search query;

identifying multiple businesses in response to the search query, and a respective relevance score associated with each business;

determining that a top N businesses according to the relevance scores include more than a predetermined number of businesses of a particular category, wherein N is a positive integer that is less than or equal to a count of the multiple businesses;

based on determining that the top N businesses according to the relevance scores include more than the predetermined number of businesses of the particular category, demoting the respective relevance score of a particular business of the particular category; and

after demoting the respective relevance score, re-ranking the multiple businesses by the relevance scores; and

providing a top M ranked businesses for display based on re-ranking the multiple businesses by the relevance scores, wherein M is a positive integer that is less than or equal to the count of the multiple businesses.

32. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises selecting the particular business based on a rank of the particular business in the particular category.

33. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises determining a scaling factor for demoting the respective relevance score based on a rank of the particular business in the particular category.

34. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises dynamically determining a scaling factor for demoting the respective relevance score of the particular business based on a number of businesses of the particular category that are included in the top N businesses.

35. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises:

demoting the respective relevance score of the particular business of the particular category with a first scaling factor; and

demoting a respective relevance score of a different business of the particular category with a second scaling factor,

wherein the particular business is ranked lower than the different business in the particular category, and

wherein the first scaling factor is higher than the second scaling factor.

36. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises promoting a respective relevance score of a different business of the particular category, wherein the particular business is ranked lower than the different business in the particular category.

37. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises promoting a respective relevance score of a different business of a different category, wherein the particular business of the particular category is ranked higher than the different business of the different category in the top N businesses.

38. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises:

demoting the respective relevance score of the particular business of the particular category with a first scaling factor; and

demoting a respective relevance score of a different business of a different category with a second scaling factor,

wherein a ranking of the particular business in the particular category is equal to a ranking of the different business in the different category, and

wherein the first scaling factor is different from the second scaling factor.

39. The method of claim 38, wherein a number of businesses of the different category does not exceed the predetermined number, and wherein the first scaling factor is higher than the second scaling factor.

40. The method of claim 31, wherein demoting the respective relevance score of the particular business of the particular category comprises demoting the respective relevance score of the particular business of the particular category such that (i) before demoting the respective relevance score of the particular business, a different business of a different category is not included in the top M ranked businesses for display, and (ii) after demoting the respective relevance score of the particular business, the different business of the different category is included in the top M ranked businesses for display.