Enhanced identification of interesting points-of-interest

• US 8,566,029 B1
• Filed: 11/12/2009
• Issued: 10/22/2013
• Est. Priority Date: 11/12/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lopatenko, Andrei, Kim, Hyung-Jin, Mazumdar, Soham
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US12/617,302
• Time in Patent Office: 1,440 Days
• Field of Search: 701400-541
• US Class Current: 701/426
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• 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/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G08G 1/0962 having an indicator mounted inside the vehicle, e.g. giving voice messages
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for identifying points-of-interest. In one aspect, a method includes identifying points-of-interest (POIs) associated with one or more of multiple, selected geographic areas, and determining, for each of the multiple geographic areas, a score associated with the identified POIs. The actions also include generating a combined score for each identified POI based on the determined scores associated with the respective POI, selecting a subset of the identified POIs based at least on the combined scores, and displaying a link to the POIs in the subset.

Claims

1. A computer-implemented method comprising:

generating, at one or more processors, a first search engine results page which includes links to one or more points-of-interest that satisfy a query;

receiving, at the one or more processors, one or more signals indicating that a link to a point-of-interest was selected by a user;

responsive to receiving the one or more signals;

selecting, at the one or more processors, a plurality of geographic areas, each geographic area being associated with a set of information, each set of information comprising one or more identifiers of points-of-interest and a score associated with each identifier,

determining, at the one or more processors, for each of the selected geographic areas, an increment value,

determining, at the one or more processors, for each of the selected geographic areas, a score associated with the selected point-of-interest,

incrementing, at the one or more processors, for each of the selected geographic areas, the score by the increment value, and

storing, by the one or more processors, for each of the selected geographic areas, the incremented score in the set of information associated with the respective geographic area, the incremented score being stored in association with an identifier of the selected point-of-interest; and

using, at the one or more processors, the incremented scores stored in the sets of information associated with the selected geographic areas to generate a second search engine results page.

2. The computer-implemented method of claim 1, wherein:

one or more of the sets of information are stored in a query database;

the query includes a query term entered by the user,

the first search engine results page includes one or more links to the points-of-interest which satisfy the query, overlaid on a map,

selecting the plurality of geographic areas further comprises determining that the plurality of geographic areas are disposed at or near a center of the map,

the score is associated with a query-result pair including the query term and the particular point-of-interest,

the incremented score for each of the selected geographic areas is stored in association with the query-result pair, in the query database, and

the incremented scores stored in the query database are used to generate the second search engine results page.

3. The method of claim 2, further comprising:

determining a scale of the map,

wherein determining the increment value further comprises selecting a value of zero as the increment value when the scale is determined not to exceed a predetermined threshold.

4. The method of claim 2, further comprising:

providing a search engine query page which includes a pre-query map, and a query field for the user to enter the query terms,

wherein the first search engine results page further includes one or more links to the points-of-interest which satisfy the query, overlaid on a post-query map.

5. The method of claim 1, further comprising:

determining a geographic location of the particular point-of-interest,

wherein;

one or more of the sets of information are stored in a point-of-interest database,

the first search engine results page includes one or more links to the points-of-interest which satisfy the query, presented in a list of search results or overlaid on a map,

selecting the plurality of geographic areas further comprises determining that the plurality of geographic areas are at or near the geographic location of the selected point-of-interest,

the incremented score for each of the selected geographic areas is stored in association with the selected point-of-interest, in the point-of-interest database, and

the incremented scores stored in the point-of-interest database are used to generate the second search engine results page.

6. The method of claim 5, wherein determining the geographic location of the selected point-of-interest further comprising:

determining geographic coordinates of the selected point-of-interest based on accessing a location database which stores information identifying points-of-interest, and geographic coordinates associated with each identified point-of-interest.

7. The method of claim 1, wherein using the incremented scores stored in the sets of information associated with the selected geographic areas to generate a second search engine results page further comprises:

identifying candidate points-of-interest stored for a target geographic area in the sets of information,

determining the score associated with each candidate point-of-interest; and

selecting, as relevant points-of-interest, the candidate points-of-interest whose associated scores satisfy a threshold,

wherein the second search engine results page includes links to the relevant points-of-interest.

8. The method of claim 1, wherein:

the signal further indicates a duration between an initial click on the link by the user, and a subsequent click by the user; and

determining the increment value comprises selecting, as the increment value, a value which is proportional to the duration.

9. The method of claim 1, wherein:

the signal further indicates a click-through-rate of the link, and

determining the increment value comprises selecting, as the increment value, a value which is proportional to the click-through-rate.

10. The method of claim 1, wherein determining the increment value further comprises:

selecting a first increment value for a first selected geographic area, and

selecting a second, lesser increment value for the selected geographic areas which surround the first geographic area based on a fall-off function.

11. The method of claim 10, wherein determining the second increment value further comprises applying a Gaussian function to the first increment value.

12. The method of claim 10, wherein determining the second increment value further comprises applying a parabolic function to the first increment value.

13. The method of claim 1, further comprising:

determining that information identifying the selected point-of-interest is stored in the sets of information for more than a predetermined quantity of the geographic areas;

determining, for each of the geographic areas in which the information identifying the selected point-of-interest is stored, a decrement value;

decrementing, for each of the geographic areas in which the information identifying the selected point-of-interest is stored, the score by the decrement value; and

storing, for each of the geographic areas in which the information identifying the selected point-of-interest is stored, the decremented score in association with the information.

14. The method of claim 1, further comprising:

identifying a selected category associated with the link;

incrementing, for the selected point-of-interest, a category score of the selected category by a predetermined value, in a category database which stores information identifying the points-of-interest, candidate categories associated with the selected point-of-interest, and category scores associated with the candidate categories; and

storing, for the selected point-of-interest, the incremented category score in association with the selected category.

15. The method of claim 14, further comprising:

selecting, for the selected point-of-interest, a predominant category having a highest category score; and

storing, for each of the selected geographic areas, the predominant category in association with the information identifying the selected point-of-interest.

16. The method of claim 1, further comprising defining multiple, contiguous geographic areas within a geographic region, the multiple geographic areas each exhibiting a uniform size and shape.

17. The method of claim 1, wherein receiving the one or more signals further comprises:

receiving first and second signals indicating that the link to the selected point-of-interest was selected by the user at a first time and a second time, respectively; and

filtering the second signal.

18. The method of claim 1, further comprising normalizing the increment value into a range between 0 to 1, inclusive.

19. A system comprising:

one or more computers; and

a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

generating a first search engine results page which includes links to one or more points-of-interest that satisfy a query;

receiving one or more signals indicating that a link to a point-of-interest was selected by a user;

responsive to receiving the one or more signals;

selecting a plurality of geographic areas, each geographic area being associated with a set of information, each set of information comprising one or more identifiers of points-of-interest and a score associated with each identifier,

determining, for each of the selected geographic areas, an increment value,

determining, for each of the selected geographic areas, a score associated with the selected point-of-interest,

incrementing, for each of the selected geographic areas, the score by the increment value, and

storing, for each of the selected geographic areas, the incremented score in the set of information associated with the respective geographic area, the incremented score being stored in association with an identifier of the selected point-of-interest; and

using the incremented scores stored in the sets of information associated with the selected geographic areas to generate a second search engine results page.

20. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

generating, at the one or more processors, a first search engine results page which includes links to one or more points-of-interest that satisfy a query;

receiving, at the one or more processors, one or more signals indicating that a link to a point-of-interest was selected by a user;

responsive to receiving the one or more signals;

selecting, at the one or more processors, a plurality of geographic areas, each geographic area being associated with a set of information, each set of information comprising one or more identifiers of points-of-interest and a score associated with each identifier,

determining, at the one or more processors, for each of the selected geographic areas, an increment value,

determining, at the one or more processors, for each of the selected geographic areas, a score associated with the selected point-of-interest,

incrementing, at the one or more processors, for each of the selected geographic areas, the score by the increment value, and

storing, by the one or more processors, for each of the selected geographic areas, the incremented score in the set of information associated with the respective geographic area, the incremented score being stored in association with an identifier of the selected point-of-interest; and

using, at the one or more processors, the incremented scores stored in the sets of information associated with the selected geographic areas to generate a second search engine results page.