METHOD AND APPARATUS FOR HIERARCHICAL CLUSTERING OF GEOGRAPHICAL DATA

• US 20180113880A1
• Filed: 10/21/2016
• Published: 04/26/2018
• Est. Priority Date: 10/21/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: METCALF-PUTNAM, Evan, MILOJKOVIC, Dejan
• Granted Patent: US 10,437,863 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

An approach is provided for hierarchical clustering of geographical data. The approach involves receiving a request to cluster geographical data by location. The geographical area is represented by a hierarchical tile projection comprising a plurality of zoom levels, and tiles of each of the zoom levels represent different respective scales of a corresponding portion of the geographical area. The approach also involves determining that the geographical data is located in a border area of a first tile at a higher zoom level of the hierarchical tile projection. The approach further involves recursively forwarding the geographical data for clustering at a lower zoom level of the hierarchical tile projection until the geographical data is not located in a border area of a second tile at the lower zoom level. The approach then involves initiating the clustering of the geographical data into a cluster located in the second tile at the lower zoom level.

Claims

1. A method for real-time clustering of geographical data in a hierarchical tile projection of mapping data comprising:

receiving a request to cluster the geographical data by a location of the geographical data within a geographical area, wherein the geographical area is represented by the hierarchical tile projection comprising a plurality of zoom levels, and wherein one or more tiles of each of the plurality of zoom levels represent different respective scales of a corresponding portion of the geographical area;

determining, by a processor, that the geographical data is located in a border area of a first tile at a higher zoom level of the hierarchical tile projection;

recursively forwarding, by the processor, the geographical data for clustering at a lower zoom level of the hierarchical tile projection until the geographical data is not located in a border area of a second tile at the lower zoom level; and

initiating, by the processor, the clustering of the geographical data into a cluster located in the second tile at the lower zoom level.

2. The method of claim 1, further comprising:

initiating a clustering of the geographical data into an initial cluster at the first tile at the higher level of zoom,

wherein the forwarding of the geographical data comprises forwarding the initial cluster including the geographical data.

3. The method of claim 2, further comprising:

flagging the initial cluster to indicate that subsequently received geographical data that belongs in the initial cluster is to be forwarded to the second tile.

4. The method of claim 1, further comprising:

determining that the geographical data has expired;

initiating a removal of the expired geographical data from the initial cluster beginning at the higher zoom level of the hierarchical tile projection; and

recursively removing the expired geographical data from the cluster at the lower zoom level to which the geographical data was forwarded.

5. The method of claim 1, wherein the clustering is performed using a parallel processing system, and wherein respective computing threads of the parallel processing system are respectively assigned to cluster data for each of the one or more tiles of the hierarchical tile projection in parallel.

6. The method of claim 1, further comprising:

specifying the border area of the first tile, the border area of the second tile, or a combination thereof based on a predetermined distance from respective boundaries of the first tile, the second tile, or a combination thereof.

7. The method of claim 6, further comprising:

calculating the predetermined distance based on a clustering distance of the cluster.

8. The method of claim 1, wherein the geographical data relates to one or more location-based events occurring in the geographical area.

9. The method of claim 1, wherein the second tile is a parent tile of the first tile, and wherein the first tile has only one parent tile.

10. A non-transitory computer-readable storage medium for real-time clustering of geographical data in a hierarchical tile projection of mapping data, and carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform:

receiving geographical data at a first computing thread of a parallel processing system, wherein computing threads of the parallel processing system are respectively assigned to cluster data for one or more tiles of the hierarchical tile projection comprising a plurality of zoom levels, and wherein the first computing thread is assigned to a first tile at a higher zoom level of the hierarchical tile projection;

determining whether the geographical data is located in a border area of the first tile;

when the geographical data is not located in the border area of the first tile, initiating a clustering of the geographical data into a cluster in the first tile; and

when the geographical data is located in the border area of the first tile, initiating the clustering of the geographical data into the cluster in the first tile, and initiating a forwarding of the cluster including the geographical data to a second computing thread assigned to a second tile at a lower zoom level to perform another clustering.

11. The non-transitory computer-readable storage medium of claim 10, wherein the apparatus is further caused to perform:

when the geographical data is located in the border area of the first tile, flagging the cluster in the first tile to indicate that the cluster has been forwarded.

12. The non-transitory computer-readable storage medium of claim 11, wherein the apparatus is further caused to perform:

receiving subsequent geographical data at the first computing thread;

determining that the subsequent geographical data is to be clustered in the cluster in the first tile; and

initiating a forwarding to the subsequent geographical data to the second computing thread when the cluster is flagged.

13. The non-transitory computer-readable storage medium of claim 11, wherein the flagging of the cluster in the first tile comprises adding a value to metadata associated with the cluster to indicate that the cluster has been forwarded.

14. The non-transitory computer-readable storage medium of claim 11, wherein the flagging of the cluster in the first tile is maintained after the geographical data is expired.

15. The non-transitory computer-readable storage medium of claim 10, wherein the geographical data includes one or more incident reports reported by one or more vehicles traversing a transportation network, and wherein the clustering of the geographical data comprises grouping the one or more incident reports into a cluster when the one or more incident reports are determined to be related to a common location-based event.

16. The non-transitory computer-readable storage medium of claim 15, wherein the apparatus is further caused to perform:

transmitting a notification regarding the common location-based event to one or more devices determined to be within proximity of the common location-based event based on the clustering.

17. The computer-readable storage medium of claim 16, wherein the geographical data includes location data for the one or more devices, wherein the clustering further comprises clustering the one or more devices based on the location data into a device cluster, and wherein the notification is transmitted to the device cluster.

18. An apparatus for real-time clustering of geographical data in a hierarchical tile projection of mapping data comprising:

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

receive a request to cluster the geographical data by a location of the geographical data within a geographical area, wherein the geographical area is represented by the hierarchical tile projection comprising a plurality of zoom levels, and wherein one or more tiles of each of the plurality of zoom levels represent different respective scales of a corresponding portion of the geographical area;

determine, by a processor, that the geographical data is located in a border area of a first tile at a higher zoom level of the hierarchical tile projection;

recursively forward, by the processor, the geographical data for clustering at a lower zoom level of the hierarchical tile projection until the geographical data is not located in a border area of a second tile at the lower zoom level; and

initiate, by the processor, the clustering of the geographical data into a cluster located in the second tile at the lower zoom level.

19. The apparatus of claim 18, wherein the apparatus is further caused to:

initiate a clustering of the geographical data into an initial cluster at the first tile at the higher level of zoom,

wherein the forwarding of the geographical data comprises forwarding the initial cluster including the geographical data.

20. The apparatus of claim 18, wherein the apparatus is further caused to:

flag the initial cluster to indicate that subsequently received geographical data that belongs in the initial cluster is to be forwarded to the second tile.