IDENTIFYING, PROCESSING AND DISPLAYING DATA POINT CLUSTERS

• US 20190101402A1
• Filed: 06/24/2016
• Published: 04/04/2019
• Est. Priority Date: 06/24/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chien, Steve, Li, Mark Yinan, Schaub, Marc, Anderson, Benjamin, Aspinall, James, Bailiang, Zhou, Hess, Ruwen
• Granted Patent: US 10,415,987 B2
• Time in Patent Office: 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-15. -15. (canceled)

16. 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 road segment,

identifying a geographically-located object having a characteristic associated with the road segment,

generating a polygon wherein the locations of the polygon'"'"'s edges are based on the footprint of the road segment and the footprint of the geographically-located object, and

providing for display a map that displays the road segments and the polygon relative to the geographic locations of the road segments.

17. The system of claim 16 wherein the road segment is identified based on the number of points-of-interest located on the segment.

18. The system of claim 16 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 geographic-located object, and the polygon that is provided for display is based on the union of the first polygon and the second polygon.

19. The system of claim 18 wherein the characteristic is that the geographically-located object has a footprint within a threshold distance of the road segment.

20. The system of claim 16 wherein the geographically-located object is a building and the characteristic is that the building has an access route associated with the segment.

21. The system of claim 20 wherein identifying the geographically-located object further comprises identifying the geographically-located object based on whether the building contains a point of interest associated with a selected category.

22. The system of claim 16 further comprising:

identifying, using the one or more computing devices, a plurality of road segments,

identifying, using the one or more computing devices, a plurality of geographically-located objects having a characteristic associated with at least one of the plurality of road segments, and

wherein generating the polygon further comprises generating a polygon wherein the locations of the polygon'"'"'s edges are based on the footprints of the road segments and the footprints of the geographically-located objects.

23. The system of claim 16 wherein the polygon does not contain any edges collectively forming a hole inside the polygon.

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

25. The system of claim 16 wherein the polygon is not a rectangle.

26. A method comprising:

identifying, using one or more computing devices, a plurality of road segments,

identifying, using the one or more computing devices, a plurality of buildings containing a point of interest (POI) associated with a selected category and having an access route associated with a segment of the identified plurality of segments,

generating, using the one or more computing devices, a polygon wherein the locations of the polygon'"'"'s edges are based on the footprints of the plurality of road segments and the footprint of the building,

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

27. The method of claim 26 wherein identifying the road segments comprises determining a second plurality of road segments and comprises:

determining a score for each road segment of a first plurality of road segments based on (a) the number of points of interests that are associated are the selected category and the road segment and (b) the score of another road segment that shares an intersection with the road segment; and

determining the second plurality by selecting a portion of the road segments in the first plurality, wherein road segments are selected based on (a) a comparison of the score of each road segment in the first plurality with a threshold value, wherein the threshold value is selected in order to limit the size of the second plurality of road segments and (b) the number of points of interests that are associated with a road segment relative to the length of the road segment.

28. The method of claim 27 wherein selecting road segments based on the number of points of interests that are associated with a road segment relative to the length of the road segment further comprises:

determining, with respect to at least a portion of the road segments of the first plurality, a second score for each road segment based on the formula

Score_s=max(L−

D*N,0),

where

Score_s=score of segment S,

L=physical length of segment S,

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

N=number of POI'"'"'s located on segment S;

determining all unique pairs of intersections associated with the road segments of said portion; and

selecting those road segments that would be on the shortest path between any pair of intersections, where the length of a path is based on the second score.

29. The method of claim 26 wherein the footprints of the road segments and buildings comprise edges and the distance from each edge of the polygon to the closest edge of a road segment or building is substantially equal.

30. The method of claim 26 wherein identifying a plurality of road segments comprising identifying road segments upon which POI of category are located.

31. The method of claim 26 wherein the category comprises restaurants.

32. The method of claim 26 wherein the polygon does not contain any holes.

33. 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 satisfy POI-related criteria,

identifying a plurality of geographically-located objects that are associated with at least one POI satisfying the POI-related criteria and are located on at least one of the identified road segments,

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

providing for display a map that that includes the polygon.

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

35. The medium of claim 33 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.