Enforcing category diversity

• US 10,289,648 B2
• Filed: 11/14/2016
• Issued: 05/14/2019
• Est. Priority Date: 10/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Arora, Neha, Yang, Ke, Yang, Zuguang
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US15/350,377
• Publication Number:
  US 20170061025A1
• Time in Patent Office: 911 Days
• Field of Search: 707723
• 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 the category diversity or sub-category diversity of POIs that are identified in response to a local search. According to one implementation, a method includes receiving a request to identify points of interest (POIs), obtaining data identifying (i) candidate points of interest (POIs) that satisfy the request, (ii) a respective category associated with each candidate POI, and (iii) a non-scaled score associated with each candidate POI, and ranking, for each of one or more of the categories, the candidate POIs associated with the category, based on the respective non-scaled scores. The method also includes scaling, for each of the one or more categories, the non-scaled scores of the ranked candidate POIs associated with the category, ranking the candidate POIs using the scaled scores, for the candidate POIs that are associated with the one or more categories, and the non-scaled scores, for the candidate POIs that are not associated with the one or more 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.

Claims

1. A computer-implemented method comprising:

receiving a search query from a computing device;

identifying multiple entities responsive to the search query, each of the multiple entities being associated with a respective relevance score, where the multiple entities are associated with multiple different categories;

determining that a top N ranked entities according to relevance scores includes more than a predetermined number of entities associated with a particular category of the multiple different categories, wherein N is a positive integer that is less than or equal to a count of the multiple entities;

in response to determining that a top N ranked entities according to relevance scores includes more than the predetermined number of entities associated with the particular category, scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of a top most ranked entity associated with the particular category according to both a scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of another entity associated with the particular category;

after scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of the top most ranked entity associated with the particular category according to both the scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of the another entity associated with the particular category, ranking the multiple entities associated with the multiple different categories based on the relevance scores including the respective relevance score that is scaled; and

providing, to the computing device, data that identifies two or more of the multiple entities, as ranked according to the relevance scores, for display on the computing device as search results that are responsive to the search query.

2. The method of claim 1, comprising:

selecting, as the particular category, a category that is associated with more than a predetermined candidate number of entities.

3. The method of claim 2, wherein scaling the respective relevance score associated with one or more of the multiple entities comprises:

for the particular category;

selecting top n ranked entities associated with the particular category based on the relevance scores, wherein n is a positive integer that is less than or equal to a count of entities associated with the particular category; and

increasing the respective relevance score of one or more of the top n ranked entities.

4. The method of claim 2, comprising:

dynamically determining the scaling factor to use to scale one or more of the respective relevance scores associated with one or more of the multiple entities of the particular category based on a particular relevance score associated with a top ranked entity of a different category.

5. The method of claim 2, comprising:

dynamically determining the scaling factor to use to scale one or more of the respective relevance scores associated with one or more of the multiple entities of the particular category based on a quantity of the multiple entities of the particular category identified.

6. The method of claim 2, wherein in response to determining that a top N ranked entities according to relevance scores for the particular category includes more than the predetermined number of entities associated with the particular category, scaling the respective relevance score associated with one or more of the multiple entities comprises:

in response to determining that the top N ranked entities according to relevance scores for the particular category includes more than the predetermined number of entities associated with the particular category, reducing the relevance score of at least one of the entities associated with the particular category responsive to the search query relative to the relevance score of at least one of the entities associated with another particular category and identified responsive to the search query.

7. The method of claim 1, wherein in response to determining that a top N ranked entities according to relevance scores includes more than the predetermined number of entities associated with the particular category, scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of a top most ranked entity associated with the particular category according to the relevance scores relative to the relevance score of another entity associated with the particular category comprises:

in response to determining that the top N ranked entities according to relevance scores includes two or more entities associated with the particular category, increasing the relevance score of the top most ranked entity associated with the particular category according to the relevance scores and decreasing the relevance score of the another entity associated with the particular category.

8. The method of claim 2, comprising:

determining that the top N ranked entities according to relevance scores includes a single entity associated with a second particular category; and

in response to determining that the top N ranked entities according to relevance scores includes a single entity associated with the second particular category, bypassing scaling the respective relevance score associated with the single entity associated with the second particular category.

9. The method of claim 2, wherein the computing device is configured to display at most a predetermined number of search results at a time, wherein increasing the relevance score of a top most ranked entity associated with the particular category according to the relevance scores relative to the relevance score of another entity associated with the particular category increases a likelihood that the top most ranked entity associated with the particular category and a top most ranked entity associated with a different particular category are displayed at a time on the computing device.

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

receiving a search query from a computing device;

identifying multiple entities responsive to the search query, each of the multiple entities being associated with a respective relevance score, where the multiple entities are associated with multiple different categories;

determining that a top N ranked entities according to relevance scores includes more than a predetermined number of entities associated with a particular category of the multiple different categories, wherein N is a positive integer that is less than or equal to a count of the multiple entities;

in response to determining that a top N ranked entities according to relevance scores includes more than the predetermined number of entities associated with the particular category, scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of a top most ranked entity associated with the particular category according to both a scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of another entity associated with the particular category;

after scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of the top most ranked entity associated with the particular category according to both the scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of the another entity associated with the particular category, ranking the multiple entities associated with the multiple different categories based on the relevance scores including the respective relevance score that is scaled; and

providing, to the computing device, data that identifies two or more of the multiple entities, as ranked according to the relevance scores, for display on the computing device as search results that are responsive to the search query.

11. The computer-readable storage device of claim 10, wherein the operations comprise:

selecting, as the particular category, a category that is associated with more than a predetermined candidate number of entities.

12. The computer-readable storage device of claim 10, wherein scaling the respective relevance score associated with one or more of the multiple entities comprises:

for the particular category;

selecting top n ranked entities associated with the particular category based on the relevance scores, wherein n is a positive integer that is less than or equal to a count of entities associated with the particular category; and

increasing the respective relevance score of one or more of the top n ranked entities.

13. The computer-readable storage device of claim 10, wherein the operations comprise:

dynamically determining the scaling factor to use to scale one or more of the respective relevance scores associated with one or more of the multiple entities of the particular category based on a particular relevance score associated with a top ranked entity of a different category.

14. The computer-readable storage device of claim 10, wherein the operations comprise:

dynamically determining the scaling factor to use to scale one or more of the respective relevance scores associated with one or more of the multiple entities of the particular category based on a quantity of the multiple entities of the particular category identified.

15. 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 search query from a computing device;

identifying multiple entities responsive to the search query, each of the multiple entities being associated with a respective relevance score, where the multiple entities are associated with multiple different categories;

determining that a top N ranked entities according to relevance scores includes more than a predetermined number of entities associated with a particular category of the multiple different categories, wherein N is a positive integer that is less than or equal to a count of the multiple entities;

in response to determining that a top N ranked entities according to relevance scores includes more than the predetermined number of entities associated with the particular category, scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of a top most ranked entity associated with the particular category according to both a scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of another entity associated with the particular category;

after scaling the respective relevance score associated with one or more of the multiple entities by increasing the relevance score of the top most ranked entity associated with the particular category according to both the scaling factor that varies for entities within the particular category and the relevance scores relative to the relevance score of the another entity associated with the particular category, ranking the multiple entities associated with the multiple different categories based on the relevance scores including the respective relevance score that is scaled; and

providing, to the computing device, data that identifies two or more of the multiple entities, as ranked according to the relevance scores, for display on the computing device as search results that are responsive to the search query.

16. The system of claim 15, the operations comprising:

selecting, as the particular category, a category that is associated with more than a predetermined candidate number of entities.

17. The system of claim 15, wherein scaling the respective relevance score associated with one or more of the multiple entities comprises:

for the particular category;

selecting top n ranked entities associated with the particular category based on the relevance scores, wherein n is a positive integer that is less than or equal to a count of entities associated with the particular category; and

increasing the respective relevance score of one or more of the top n ranked entities.