Grouping Ambient-Location Updates

• US 20140221022A1
• Filed: 02/06/2013
• Published: 08/07/2014
• Est. Priority Date: 02/06/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Gabriel Grise
• Inventors: Vaccari, Andrea, Gris, Gabriel, Lahiri, Mayank
• Granted Patent: US 9,119,055 B2
• Time in Patent Office: Days
• US Class Current: 455/456.6
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/022 with dynamic range variability
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

In one embodiment, a method includes receiving location data from a mobile device associated with a user. The location data includes one or more location readings sent automatically and without manual input from the user. The method also includes representing the location data as one or more geo-location data points based at least in part on a distance between the location readings and the geo-location data points; and grouping one or more of the geo-location data points into one or more geo-location clusters based at least in part on a distance between each geo-location data point and a geo-location centroid of each geo-location cluster.

Claims

1. A method comprising:

by a computing device, receiving location data from a mobile computing device associated with a user, the location data comprising one or more location readings being sent automatically and without manual input from the user;

by the computing device, representing the location data as one or more geo-location data points based at least in part on a distance between the location readings and the geo-location data points; and

by the computing device, grouping one or more of the geo-location data points into one or more geo-location clusters based at least in part on a distance between each geo-location data point and a geo-location centroid of each geo-location cluster.

2. The method of claim 1, further comprising:

by the computing device, updating a geo-location of the geo-location centroid of each geo-location cluster based at least in part on determining a center of the geo-location data points within each geo-location cluster; and

by the computing device, re-grouping the geo-location data points into the geo-location clusters based at least in part on the updated geo-location of the geo-location centroid.

3. The method of claim 2, further comprising by the computing device, performing the updating of the geo-location centroid and the regrouping of the geo-location data points a pre-determined number of times.

4. The method of claim 1, further comprising by the computing device, updating a geo-location of the geo-location centroid of one or more of the geo-location clusters in response to receiving subsequent location data from the mobile computing device.

5. The method of claim 1, further comprising by the computing device, adding an additional geo-location data point to a particular one of the geo-location clusters in response to a distance between the subsequent geo-location data point and the geo-location centroid of the particular one of the geo-location clusters being less than a pre-determined threshold value.

6. The method of claim 1, wherein grouping the geo-location data points comprises by the computing device, placing each geo-location data point with a particular one of the geo-location clusters based at least in part on a distance between each geo-location data point and the geo-location centroid of the particular one of the geo-location clusters being less than a pre-determined threshold value.

7. The method of claim 1, wherein representing the location data comprises by the computing device, combining the consecutive location readings as a single geo-location data point in response to distance between consecutive location readings being less than a measurement accuracy of the location data.

8. The method of claim 1, wherein representing the location data comprises by the computing device, adding an additional geo-location data point in response to distance between consecutive location readings being more than a measurement accuracy of the location data.

9. The method of claim 1, wherein grouping the geo-location data points comprises by the computing device, grouping the geo-location data points through a k-means spatial-clustering algorithm.

10. One or more computer-readable non-transitory storage media embodying software configured when executed to:

receive location data from a mobile computing device associated with a user, the location data comprising one or more location readings being sent automatically and without manual input from the user;

represent the location data as one or more geo-location data points based at least in part on a distance between consecutive location readings; and

group one or more of the geo-location data points into one or more geo-location clusters based at least in part on a distance between each geo-location data point and a geo-location centroid of each geo-location cluster.

11. The media of claim 10, wherein the software is further configured to:

update a geo-location of the geo-location centroid of each geo-location cluster based at least in part on determining a center of the geo-location data points within each geo-location cluster; and

re-group the geo-location data points into the geo-location clusters based at least in part on the updated geo-location of the geo-location centroid.

12. The media of claim 11, wherein the software is further configured to perform the updating of the geo-location centroid and the regrouping of the geo-location data points a pre-determined number of times.

13. The media of claim 10, wherein the software is further configured to update a geo-location of the geo-location centroid of one or more of the geo-location clusters in response to receiving subsequent location data from the mobile computing device.

14. The media of claim 10, wherein the software is further configured to add an additional geo-location data point to a particular one of the geo-location clusters in response to a distance between the subsequent geo-location data point and the geo-location centroid of the particular one of the geo-location clusters being less than a pre-determined threshold value.

15. The media of claim 10, wherein the software is further configured to place each geo-location data point with a particular one of the geo-location clusters based at least in part on a distance between each geo-location data point and the geo-location centroid of the particular one of the geo-location clusters being less than a pre-determined threshold value.

16. The media of claim 10, wherein the software is further configured to combine the consecutive location readings as a single geo-location data point in response to distance between consecutive location readings being less than a measurement accuracy of the location data.

17. The media of claim 10, wherein the software is further configured to add an additional geo-location data point in response to distance between consecutive location readings being more than a measurement accuracy of the location data.

18. The media of claim 10, wherein the software is further configured to group the geo-location data points through a k-means spatial-clustering algorithm.

19. A device comprising:

one or more processors; and

one or more computer-readable non-transitory storage media coupled to the processors and embodying software configured when executed to;

receive location data from a mobile computing device associated with a user, the location data comprising one or more location readings being sent automatically and without manual input from the user;

represent the location data as one or more geo-location data points based at least in part on a distance between consecutive location readings; and

group one or more of the geo-location data points into one or more geo-location clusters based at least in part on a distance between each geo-location data point and a geo-location centroid of each geo-location cluster.

20. The device of claim 19, wherein the software is further configured to group the geo-location data points through a k-means spatial-clustering algorithm.