Identifying, processing and displaying data point clusters

• US 10,415,987 B2
• Filed: 06/24/2016
• Issued: 09/17/2019
• Est. Priority Date: 06/24/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Chien, Steve, Li, Mark Yinan, Schaub, Marc, Anderson, Benjamin, Aspinall, James, Bailiang, Zhou, Hess, Ruwen
• Primary Examiner(s): Antonucci, Anne M
• Application Number:
  US15/108,510
• Publication Number:
  US 20190101402A1
• Time in Patent Office: 1,180 Days
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• 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/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

Presented are techniques of identifying, processing and displaying data point clusters (850, 851) associated with map information (200) in an efficient manner. Methods and systems are disclosed which process map information (200) to identify clusters (850, 851) of requested data points for display (1020), based on iterative clustering and filtering of the data points. Methods and systems are also disclosed which generate polygons (1860, 1861, 1901-05) representing the clusters. The amount of data to be processed and/or displayed can be reduced, without loss of any associated information content in a displayed map.

Claims

1. A system comprising:

one or more computing devices; and

memory storing instructions, the instructions being executable by the one or more computing devices;

wherein the instructions comprise;

identifying a geographically-located road segment, the road segment having a footprint,

identifying a geographically-located object based on a characteristic associated with the road segment and the object, wherein the object is not a segment of a road and the object has a footprint,

generating a polygon, the polygon having edges at locations, wherein the locations of the edges are based on the footprint of the road segment and the footprint of the object, and

providing for display a map that displays the road segment and the polygon relative to the footprint of the road segment.

2. The system of claim 1 wherein the road segment is identified based on a number of points-of-interest located on the road segment.

3. The system of claim 1 wherein generating the polygon comprises generating a first polygon wherein at least a portion of each edge of the first polygon is a first fixed distance from the footprint of the road segment, generating a second polygon wherein at least a portion of each edge of the second polygon is a second fixed distance from the footprint of the object, and the polygon that is provided for display is based on a union of the first polygon and the second polygon.

4. The system of claim 3 wherein the characteristic is that the footprint of the object is within a threshold distance of the road segment.

5. The system of claim 1 wherein the object is a building and the characteristic is that the building has an access route associated with the road segment.

6. The system of claim 5 wherein identifying the object further comprises identifying the object based on whether the building contains a point of interest associated with a selected category.

7. The system of claim 1 further comprising:

identifying, using the one or more computing devices, a plurality of road segments wherein each road segment of the plurality of road segments has a footprint,

identifying, using the one or more computing devices, a plurality of objects where each object has a characteristic associated with at least one of the plurality of road segments and where each object has a footprint, and

wherein generating the polygon further comprises generating a polygon wherein the locations of the edges of the polygon are based on the footprints of the plurality of road segments and the footprints of the plurality of objects.

8. The system of claim 1 wherein the polygon does not contain edges collectively forming a hole inside the polygon.

9. The system of claim 1 further comprising determining a region name based on a name of the road segment and wherein the map displays the region name within or proximate to the edges of the polygon.

10. The system of claim 1 wherein the polygon is not a rectangle.

11. A method comprising:

identifying, using one or more computing devices, a plurality of road segments wherein each road segment has a footprint,

identifying, using the one or more computing devices, a plurality of buildings based on whether the building contains a point of interest (POI) associated with a selected category and has an access route associated with at least one road segment of the plurality of road segments, each building having a footprint,

generating, using the one or more computing devices, a polygon having edges at locations, wherein the locations of the edges are based on the footprints of the plurality of road segments and the footprints of the plurality of buildings,

providing for display, using the one or more computing devices, a map that displays the plurality of road segments and the polygon relative to the plurality of road segments.

12. The method of claim 11 wherein identifying said plurality of road segments comprises selecting road segments from a second plurality of road segments where each road segment of the second plurality of road segments has a length and is associated with a number of POI in the selected category, and wherein selecting road segments from the second plurality of road segments comprises:

determining a score for each road segment of the second plurality of road segments based on (a) the number of POI associated with the road segment and (b)a score of another road segment that shares an intersection with the road segment; and

selecting a given road segment from the second plurality of road segments for inclusion in said plurality of road segments, based on (a) a comparison of the score of the given road segment to a threshold value and (b) the number of POI associated with the given road segment relative to the length of the given road segment.

13. The method of claim 12 wherein selecting a given road segment based on the number of POI associated with the given road segment relative to the length of the given road segment further comprises:

determining a second score associated with the given road segment based on a formula

Score_s=max(L−

D*N,0),

where

S=the given road segment,

Score_s=the second score of the given road segment,

L=a physical length of the given road segment,

D=a coefficient equal to (a benchmark length)/(a preferred minimum number of POI within the benchmark length), and

N=the number of POI associated with the given road segment;

determining unique pairs of intersections associated with at least a portion of the second plurality of road segments;

determining a shortest path based on the second score associated with each road segment of said portion; and

selecting the given road segment when the given road segment is on the shortest path.

14. The method of claim 11 wherein the footprints of the plurality of road segments and the footprints of the plurality of buildings comprise edges, there is a distance between each edge of the polygon and the closest edge of the footprints of the plurality of road segments and the footprints of the plurality of buildings, and the distance from each edge of the polygon to the closest edge is substantially equal.

15. The method of claim 11 wherein identifying the plurality of road segments comprises identifying road segments upon which POI associated with the selected category are located.

16. The method of claim 11 wherein the selected category comprises restaurants.

17. The method of claim 11 wherein the polygon does not contain holes.

18. A non-transitory computing-device readable storage medium on which computing-device readable instructions of a program are stored, the instructions, when executed by one or more computing devices, causing the one or more computing devices to perform a method, the method comprising:

identifying a plurality of road segments that are within a geographic area and are associated with at least one point of interest (POI) that satisfies a POI-related criteria, where each road segment has a footprint,

identifying a plurality of geographically-located objects that are associated with at least one POI that satisfies the POI-related criteria, where each geographically-located object is located on at least one of the plurality of road segments, where each geographically-located object has a footprint and is not a road segment,

generating a polygon based on a union of the footprints of the plurality of geographically-located objects and the footprints of the plurality of road segments, and

providing for display a map that includes the polygon.

19. The medium of claim 18 further comprising determining and providing for display on the map a name, wherein the name is determined based on a name of a town or neighborhood in which a region appears.

20. The medium of claim 18 further comprising determining and providing for display on the map a name, wherein a portion of the name is determined based on the POI-related criteria.