Point of interest category ranking

• US 9,194,716 B1
• Filed: 06/18/2010
• Issued: 11/24/2015
• Est. Priority Date: 06/18/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cutter, Al
• Primary Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US12/819,041
• Time in Patent Office: 1,985 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods, systems, and apparatus, including computer programs encoded on one or more computer storage devices, for ranking categories of points of interest. In one aspect, a method includes receiving at a current time a location of a user'"'"'s electronic device and retrieving data identifying multiple points of interest. Each point of interest is within a predetermined distance to the location and is associated with a category. Each of the points of interest is scored based on proximity of the point of interest to the location. Each of the categories is ranked based on the scores of the points of interest included in the categories and on the probability of receiving a query from a user relating to the subject matter of the category at the current time in the location. Data identifying points of interest is provided to the electronic device based on the ranking and the scoring.

Claims

1. A computer-implemented method comprising:

receiving at a current time a current location of a user'"'"'s electronic device;

retrieving data identifying a plurality of points of interest, each point of interest within a predetermined distance to the current location and associated with a category of a plurality of categories differentiated by subject matter;

scoring each of the points of interest based at least in part on a proximity of the point of interest to the current location by calculating a plurality of scores, each respective score corresponding to a respective point of interest;

obtaining, for each of the points of interest, a category of points of interest including the respective point of interest;

determining, for each category of points of interest, a density of points of interest that (i) correspond to that category and (ii) are within the predetermined distance to the current location;

boosting the scores of points of interest associated with categories having lower densities relative to points of interest associated with categories having higher densities;

obtaining, for each category of points of interest, a probability of receiving a user query relating to the category at a time corresponding to the current time and in a location near the current location, wherein the probability of receiving the user query relating to the subject matter is determined based on a query database in which previously received queries are logged, and wherein the query database has a plurality of different queries having different terms, the different terms relating to the respective category of points of interest; and

providing data identifying a plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities.

2. The method of claim 1, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device comprises providing the one or more points of interest as suggested search queries.

3. The method of claim 1, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device comprises:

retrieving a portion of a map that includes the current location and the plurality of points of interest; and

providing the portion of the map to the electronic device for presentation to the user on a display of the electronic device, the map overlaid with a plurality of graphical elements representing the plurality of points of interest wherein the one or more graphical elements are overlaid on the map in proximity to locations corresponding to the points of interest represented by the graphical elements.

4. The method of claim 1, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of restaurants in response to the current time being a meal time based on the probability of receiving a user query relating to the category of restaurants being higher during the meal time than during other times.

5. The method of claim 4, wherein different sub-categories of restaurants are increased in ranking differently based on differing probabilities of receiving a user query relating to the respective sub-categories of restaurants at the current time.

6. The method of claim 1, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of coffee shops in response to the current time being morning based on the probability of receiving a user query relating to the category of coffee shops being higher during the morning than during other times.

7. The method of claim 1, comprising determining that the different terms relate to the respective category of points of interest based on user selection of search results that are responsive to queries including the different terms and relate to the respective category of points of interest.

8. A non-transitory computer-readable medium having instructions stored thereon, which, when executed by a processor, cause the processor to perform operations comprising:

receiving at a current time a current location of a user'"'"'s electronic device;

retrieving data identifying a plurality of points of interest, each point of interest within a predetermined distance to the current location and associated with a category of a plurality of categories differentiated by subject matter;

scoring each of the points of interest based at least in part on a proximity of the point of interest to the current location by calculating a plurality of scores, each respective score corresponding to a respective point of interest;

obtaining, for each of the points of interest, a category of points of interest including the respective point of interest;

determining, for each category of points of interest, a density of points of interest that (i) correspond to that category and (ii) are within the predetermined distance to the current location;

boosting the scores of points of interest associated with categories having lower densities relative to points of interest associated with categories having higher densities;

obtaining, for each category of points of interest, a probability of receiving a user query relating to the category at a time corresponding to the current time and in a location near the current location, wherein the probability of receiving the user query relating to the subject matter is determined based on a query database in which previously received queries are logged, and wherein the query database has a plurality of different queries having different terms, the different terms relating to the respective category of points of interest; and

providing data identifying a plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities.

9. The computer-readable medium of claim 8, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device comprises providing the one or more points of interest as suggested search queries.

10. The computer-readable medium of claim 8, wherein providing data identifying one or more of the points of interest to the user'"'"'s electronic device comprises:

retrieving a portion of a map that includes the current location and the plurality of points of interest; and

providing the portion of the map to the electronic device for presentation to the user on a display of the electronic device, the map overlaid with a plurality of graphical elements representing the plurality of points of interest wherein the one or more graphical elements are overlaid on the map in proximity to locations corresponding to the points of interest represented by the graphical elements.

11. The computer-readable medium of claim 8, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of restaurants in response to the current time being a meal time based on the probability of receiving a user query relating to the category of restaurants being higher during the meal time than during other times.

12. The computer-readable medium of claim 8, wherein different sub-categories of restaurants are increased in ranking differently based on differing probabilities of receiving a user query relating to the respective sub-categories of restaurants at the current time.

13. The computer-readable medium of claim 8, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of coffee shops in response to the current time being morning based on the probability of receiving a user query relating to the category of coffee shops being higher during the morning than during other times.

14. The computer-readable medium of claim 8, comprising determining that the different terms relate to the respective category of points of interest based on user selection of search results that are responsive to queries including the different terms and relate to the respective category of points of interest.

15. A system comprising:

one or more computers;

one or more data storage devices coupled to the one or more computers and storing instructions, which, when executed by the processor cause the one or more computers cause the one or more computers to perform operations comprising;

receiving at a current time a current location of a user'"'"'s electronic device;

retrieving data identifying a plurality of points of interest, each point of interest within a predetermined distance to the current location and associated with a category of a plurality of categories differentiated by subject matter;

scoring each of the points of interest based at least in part on a proximity of the point of interest to the current location by calculating a plurality of scores, each respective score corresponding to a respective point of interest;

obtaining, for each of the points of interest, a category of points of interest including the respective point of interest;

determining, for each category of points of interest, a density of points of interest that (i) correspond to that category and (ii) are within the predetermined distance to the current location;

boosting the scores of points of interest associated with categories having lower densities relative to points of interest associated with categories having higher densities;

obtaining, for each category of points of interest, a probability of receiving a user query relating to the category at a time corresponding to the current time and in a location near the current location, wherein the probability of receiving the user query relating to the subject matter is determined based on a query database in which previously received queries are logged, and wherein the query database has a plurality of different queries having different terms, the different terms relating to the respective category of points of interest; and

providing data identifying a plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities.

16. The system of claim 15, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device comprises providing the one or more points of interest as suggested search queries.

17. The system of claim 15, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device comprises:

retrieving a portion of a map that includes the current location and the plurality of points of interest; and

providing the portion of the map to the electronic device for presentation to the user on a display of the electronic device, the map overlaid with a plurality of graphical elements representing the plurality of points of interest wherein the one or more graphical elements are overlaid on the map in proximity to locations corresponding to the points of interest represented by the graphical elements.

18. The system of claim 15, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of restaurants in response to the current time being a meal time based on the probability of receiving a user query relating to the category of restaurants being higher during the meal time than during other times.

19. The system of claim 15, wherein different sub-categories of restaurants are increased in ranking differently based on differing probabilities of receiving a user query relating to the respective sub-categories of restaurants at the current time.

20. The system of claim 15, wherein providing data identifying the plurality of points of interest to the user'"'"'s electronic device based on the scoring and the probabilities comprises:

increasing a ranking of points of interest in the category of coffee shops in response to the current time being morning based on the probability of receiving a user query relating to the category of coffee shops being higher during the morning than during other times.

21. The system of claim 15, comprising determining that the different terms relate to the respective category of points of interest based on user selection of search results that are responsive to queries including the different terms and relate to the respective category of points of interest.