Taxonomy-based system for discovering and annotating geofences from geo-referenced data

1. A computer executable method, comprising:

dividing a geographical area of interest into a plurality of cells representative of the geographical area of interest, wherein a cell includes a plurality of geo-referenced points, and wherein each geo-referenced point is associated with a label from among a plurality of labels;

assigning each cell an initial label corresponding to a label associated with a geo-referenced point included in a respective cell;

applying hierarchical clustering to create clusters by assigning two or more adjacent cells to a cluster based on a maximization of an objective function that favors spatially adjacent cells sharing a common label;

limiting overgeneralization of the common label while applying the hierarchical clustering;

updating boundaries on a map of the geographical area of interest to identify boundaries of the clusters; and

upon detecting a user moving from a first cluster of the clusters to a second cluster of the cluster, notifying a device associated with the user that the user is crossing from the first cluster to the second cluster, wherein the first cluster represents a first portion of the geographical area of interest and the second cluster represents a second portion of the geographical area of interest,

wherein the hierarchical clustering comprises:

identifying a cluster pair of at least two clusters spatially adjacent to one another;

computing a contribution to the objective function for each cell within the cluster pair;

calculating a cluster pair contribution by summing each contribution to the objective function for each cell within the cluster pair;

calculating, for each possible label, a total contribution to the objective function for cells in the cluster pair to find a maximum merged contribution; and

responsive to the maximum merged contribution corresponding to the total contribution to the objective function for one or more cells in the cluster pair exceeding the cluster pair contribution, assigning the cluster pair to a priority queue ranked according to the maximum merged contribution, and merging the cluster pair to form the cluster.

2. The computer executable method of claim 1 , wherein the initial label is a most popular label within the cell.

3. The computer executable method of claim 1 , wherein the objective function is defined based upon:

at least one cell;

at least one cluster;

at least one cell label;

at least one user-defined parameter between 0 and 1; and

at least one coverage function.

4. The computer executable method of claim 1 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a type of commercial activity.

5. The computer executable method of claim 1 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a demographic of at least a portion of the geographical area of interest represented by the cell.

6. The computer executable method of claim 1 , comprising overlaying the clusters on an image of at least one map.

7. The computer executable method of claim 1 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a type of commercial activity that occurs with at least a portion of the geographical area of interest represented by the cell.

8. A system, comprising:

a processor; and

memory comprising computer executable instructions that when executed by the processor perform operations, the operations comprising:

dividing a geographical area of interest into a plurality of cells representative of the geographical area of interest, wherein a cell includes a plurality of geo-referenced points, and wherein each geo-referenced point is associated with a label from among a plurality of labels;

assigning each cell an initial label corresponding to a label associated with a geo-referenced point included in a respective cell;

applying hierarchical clustering to create clusters by assigning two or more adjacent cells to a cluster based on a maximization of an objective function that favors spatially adjacent cells sharing a common label;

limiting overgeneralization of the common label while applying the hierarchical clustering;

updating boundaries on a map of the geographical area of interest to identify boundaries of the clusters; and

upon detecting a user moving from a first cluster of the clusters to a second cluster of the cluster, notifying a device associated with the user that the user is crossing from the first cluster to the second cluster, wherein the first cluster represents a first portion of the geographical area of interest and the second cluster represents a second portion of the geographical area of interest,

wherein the hierarchical clustering comprises:

identifying a cluster pair of at least two clusters spatially adjacent to one another;

computing a contribution to the objective function for each cell within the cluster pair;

calculating a cluster pair contribution by summing each contribution to the objective function for each cell within the cluster pair;

calculating, for each possible label, a total contribution to the objective function for cells in the cluster pair to find a maximum merged contribution; and

responsive to the maximum merged contribution corresponding to the total contribution to the objective function for one or more cells in the cluster pair exceeding the cluster pair contribution, assigning the cluster pair to a priority queue ranked according to the maximum merged contribution, and merging the cluster pair to form the cluster.

9. The system of claim 8 , wherein the initial label is a most popular label within the cell.

10. The system of claim 8 , wherein the objective function is defined based upon:

at least one cell;

at least one cluster;

at least one cell label;

at least one user-defined parameter between 0 and 1; and

is at least one coverage function.

11. The system of claim 8 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a type of commercial activity.

12. The system of claim 8 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a demographic of at least a portion of the geographical area of interest represented by the cell.

13. The system of claim 8 , the operations comprising overlaying the clusters on an image of at least one map.

14. The system of claim 8 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a type of commercial activity that occurs with at least a portion of the geographical area of interest represented by the cell.

15. A non-transitory storage device having computer executable instruction stored thereon, that when executed by a processor, cause a computing device to perform a method comprising:

dividing a geographical area of interest into a plurality of cells representative of the geographical area of interest, wherein a cell includes a plurality of geo-referenced points, and wherein each geo-referenced point is associated with a label from among a plurality of labels;

assigning each cell an initial label corresponding to a label associated with a geo-referenced point included in a respective cell;

applying hierarchical clustering to create clusters by assigning two or more adjacent cells to a cluster based on a maximization of an objective function that favors spatially adjacent cells sharing a common label;

limiting overgeneralization of the common label while applying the hierarchical clustering;

updating boundaries on a map of the geographical area of interest to identify boundaries of the clusters; and

upon detecting a user moving from a first cluster of the clusters to a second cluster of the cluster, notifying a device associated with the user that the user is crossing from the first cluster to the second cluster, wherein the first cluster represents a first portion of the geographical area of interest and the second cluster represents a second portion of the geographical area of interest,

wherein the hierarchical clustering comprises:

identifying a cluster pair of at least two clusters spatially adjacent to one another;

computing a contribution to the objective function for each cell within the cluster pair;

calculating a cluster pair contribution by summing each contribution to the objective function for each cell within the cluster pair;

calculating, for each possible label, a total contribution to the objective function for cells in the cluster pair to find a maximum merged contribution; and

responsive to the maximum merged contribution corresponding to the total contribution to the objective function for one or more cells in the cluster pair exceeding the cluster pair contribution, assigning the cluster pair to a priority queue ranked according to the maximum merged contribution, and merging the cluster pair to form the cluster.

16. The non-transitory storage device of claim 15 , wherein the initial label is a most popular label within the cell.

17. The non-transitory storage device of claim 15 , wherein the objective function is defined based upon:

at least one cell;

at least one cluster;

at least one cell label;

at least one user-defined parameter between 0 and 1; and

is at least one coverage function.

18. The non-transitory storage device of claim 15 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a type of commercial activity.

19. The non-transitory storage device of claim 15 , wherein assigning each cell an initial label comprises assigning each cell an initial label based upon a demographic of at least a portion of the geographical area of interest represented by the cell.

20. The non-transitory storage device of claim 15 , the method comprising overlaying the clusters on an image of at least one map.