Grouping ambient-location updates

• US 9,119,055 B2
• Filed: 02/06/2013
• Issued: 08/25/2015
• Est. Priority Date: 02/06/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Vaccari, Andrea, Gris, Gabriel, Lahiri, Mayank
• Primary Examiner(s): SIVJI, NIZAR N
• Application Number:
  US13/760,796
• Publication Number:
  US 20140221022A1
• Time in Patent Office: 930 Days
• Field of Search: 370/338, 705/14.25, 705/14.1, 705/14.35, 707/748, 707/769, 707/802, 707/9, 709/204, 455/445, 455/456
• US Class Current: 1/1
• 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, through a k-means spatial-clustering algorithm, 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, wherein each geo-location data points is placed with a particular one of the geo-location clusters based at least in part on a distance between the 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.

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 representing the location data comprises by the computing device, combining consecutive location readings as a single geo-location data point in response to a distance between the consecutive location readings being less than a measurement accuracy of the location data.

7. 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 a distance between consecutive location readings being more than a measurement accuracy of the location data.

8. 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, through a k-means spatial-clustering algorithm, 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, wherein each of the geo-location data points is placed with a particular one of the geo-location clusters based at least in part on a distance between the 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.

9. The media of claim 8, 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.

10. The media of claim 9, 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.

11. The media of claim 8, 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.

12. The media of claim 8, 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.

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

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

15. 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, through a k-means spatial-clustering algorithm, 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, wherein each of the geo-location data points is placed with a particular one of the geo-location clusters based at least in part on a distance between the 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 device of claim 15, 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.

17. The device of claim 16, 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.

18. The device of claim 15, 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.

19. The device of claim 15, 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.

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

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