Systems and methods for ranking points of interest

• US 9,703,804 B2
• Filed: 02/06/2015
• Issued: 07/11/2017
• Est. Priority Date: 10/12/2011
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (System1 LLC)
• Inventors: Risser, Adam, Quinion, Brian, Hill, Simon, Laffray, Emilie
• Primary Examiner(s): Mackes, Kris
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US14/615,576
• Publication Number:
  US 20160034494A1
• Time in Patent Office: 886 Days
• Field of Search: 707748
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• 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: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: G07C 13/00 Voting apparatus
• CPC Class Codes: G09B 29/007 using computer methods
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

Systems and methods are provided for ranking points of interest (POIs). According to one implementation, a computer-implemented method may be provided that includes receiving geographic information from a user device, and selecting a plurality of points of interest within the geographic region. The method may also include generating an initial ranking of the selected points of interest based on voting information received from the user device, viral input from a user'"'"'s social network, and/or additional input based on searches for maps and travel directions for traversing a route. In addition, the method may include calculating a modified ranking of the selected points of interest.

Claims

1. A computer-implemented method, the method performed by at least one processor and comprising:

determining clusters of points of interest (POIs) within a geographic region;

calculating popularity values for the clusters based on popularity data associated with the POIs included in the clusters;

selecting, among the clusters, a cluster of POIs having a popularity value, of the popularity values, exceeding a threshold popularity value;

determining a preliminary geographic boundary for the selected cluster based on a density percentage of the POIs from the selected cluster of POIs;

comparing an area within the preliminary geographic boundary with a threshold amount of area, and setting the preliminary geographic boundary as a final geographic boundary when the area within the preliminary geographic boundary does not exceed the threshold amount of area; and

storing data specifying an area of the final geographic boundary and a name of the selected cluster for display on a user device.

2. The method of claim 1, wherein determining the clusters of the POIs within the geographic region includes identifying the POIs within a threshold distance of each other.

3. The method of claim 2, wherein the threshold distance is determined based on a mode of transportation, the mode of transportation including walking or driving.

4. The method of claim 1, wherein the popularity values for the clusters represent at least an average of popularity values corresponding to POIs included in each cluster of the clusters, a mean of popularity values corresponding to the POIs included in each cluster, or a weighted average of popularity values corresponding to the POIs included in each cluster.

5. The method of claim 4, wherein the popularity values are calculated based on at least a number of social media likes associated with the POIs included in each cluster or a number of online reviews associated with the POIs included in each cluster.

6. The method of claim 1, wherein determining the preliminary geographic boundary for the selected cluster includes:

calculating a density percentage of POIs for the selected cluster;

comparing the density percentage with a POI density percentage threshold; and

assigning geographic units of the geographic area to the selected cluster when the density percentage exceeds the POI density percentage threshold.

7. The method of claim 1, wherein the threshold amount of area includes an amount of area within the geographic region.

8. The method of claim 1, further comprising:

generating a name for the final geographic boundary and the selected cluster based on a POI located closest to a centroid of the final geographic boundary.

9. The method of claim 1, further comprising:

setting a geographic boundary, formed by popular streets in the preliminary geographic boundary, as the final geographic boundary for the selected cluster, when the area within the preliminary geographic boundary exceeds the threshold amount of area, wherein the popular streets forming the final geographic boundary are determined by;

computing a popularity score for each street in the preliminary geographic boundary by multiplying a number of POIs located on each street with popularity values corresponding to the POIs;

computing an average popularity score by averaging the computed popularity scores; and

identifying streets with popularity scores greater than the average popularity score.

10. The method of claim 1, further comprising:

selecting, among the clusters, a second cluster of POIs having a popularity value, of the popularity values, exceeding the threshold popularity value;

determining a preliminary geographic boundary for the second selected cluster;

determining whether the preliminary geographic boundary for the selected cluster is located proximate to the preliminary geographic boundary for the second selected cluster; and

merging the preliminary geographic boundary for the selected cluster and the preliminary geographic boundary for the second selected cluster when it is determined that the preliminary geographic boundary for the selected cluster is located proximate to the preliminary geographic boundary for the second selected cluster.

11. The method of claim 1, wherein determining the preliminary geographic boundary for the selected cluster includes:

defining an initial threshold percentage; and

modifying the initial threshold percentage during execution of a flood-fill algorithm.

12. An apparatus, comprising:

a storage device; and

at least one processor coupled to the storage device, wherein the storage device stores a program for controlling the at least one processor, and wherein the at least one processor, being operative with the program, is configured to;

determine clusters of points of interest (POIs) within a geographic region;

calculate popularity values for the clusters based on popularity data associated with POIs included in the clusters;

select, among the clusters, a cluster of POIs having a popularity value, of the popularity values, exceeding a threshold popularity value;

determine a preliminary geographic boundary for the selected cluster based on a density percentage of the POIs from the selected cluster of POIs;

compare an area within the preliminary geographic boundary with a threshold amount of area, and setting the preliminary geographic boundary as a final geographic boundary when the area within the preliminary geographic boundary does not exceed the threshold amount of area; and

storing data specifying an area of the final geographic boundary and a name of the selected cluster for display on a user device.

13. The apparatus of claim 12, wherein the at least one processor is configured to determine the clusters of the POIs within the geographic region by identifying the POIs within a threshold distance of each other.

14. The apparatus of claim 13, wherein the at least one processor is configured to determine the threshold distance based on a mode of transportation, the mode of transportation including walking or driving.

15. The apparatus of claim 12, wherein the popularity values for the clusters represent at least an average of popularity values corresponding to POIs included in each cluster of the clusters, a mean of popularity values corresponding to the POIs included in each cluster, or a weighted average of popularity values corresponding to the POIs included in each cluster.

16. The apparatus of claim 15, wherein the at least one processor is configured to calculate the popularity values based on at least a number of social media likes associated with the POIs included in each cluster or a number of online reviews associated with the POIs included in each cluster.

17. The apparatus of claim 12, wherein the at least one processor is configured to determine the preliminary geographic boundary for the selected cluster by:

calculating a density percentage of POIs in the selected cluster;

comparing the density percentage of POIs with a POI density percentage threshold; and

assigning geographic units of the geographic area to the selected cluster when the density percentage of POIs exceeds the POI density percentage threshold.

18. The apparatus of claim 12, wherein the threshold amount of area includes an amount of area within the geographic region.

19. The apparatus of claim 12, wherein the at least one processor is further configured to:

generate a name for the final geographic boundary and the selected cluster based on a POI located closest to a centroid of the final geographic boundary.

20. The apparatus of claim 12, wherein the at least one processor is further configured to:

select a geographic boundary formed by popular streets in the preliminary geographic boundary as the final geographic boundary for the selected cluster when the area within the preliminary geographic boundary exceeds the threshold amount of area, wherein the at least one processor is configured to determine the popular streets forming the final geographic boundary by;

computing a popularity score for each street in the preliminary geographic boundary by multiplying a number of POIs located on each street with popularity values corresponding to the POIs;

computing an average popularity score by averaging the computed popularity scores; and

identifying streets with popularity scores greater than the average popularity score.

21. The apparatus of claim 12, wherein the at least one processor is further configured to:

select, among the clusters, a second cluster of POIs having a popularity value, of the popularity values, exceeding a threshold popularity value;

determine a preliminary geographic boundary for the second selected cluster;

determine whether the preliminary geographic boundary for the selected cluster is located proximate to the preliminary geographic boundary for the second selected cluster; and

merge the preliminary geographic boundary for the selected cluster and the preliminary geographical boundary for the second selected cluster when it is determined that the preliminary geographic boundary for the selected cluster is located proximate to the preliminary geographic boundary for the second selected cluster.

22. The apparatus of claim 12, wherein determining the preliminary geographic boundary for the selected cluster includes:

defining an initial threshold percentage; and

modifying the initial threshold percentage during execution of a flood-fill algorithm.

23. A tangible, non-transitory computer readable medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform a method, comprising:

determining clusters of points of interest (POIs) within a geographic region;

calculating popularity values for the clusters based on popularity data associated with POIs included in the clusters;

selecting, among the clusters, a cluster of POIs having a popularity value, of the popularity values, exceeding a threshold popularity value;

determining a preliminary geographic boundary for the selected cluster based on a density percentage of the POIs from the selected cluster of POIs;

comparing an area within the preliminary geographic boundary with a threshold amount of area, and setting the preliminary geographic boundary as a final geographic boundary when the area within the preliminary geographic boundary does not exceed the threshold amount of area; and

storing data specifying an area of the final geographic boundary and a name of the selected cluster for display on a user device.