Clustering location data to determine locations of interest

• US 9,167,389 B1
• Filed: 01/15/2015
• Issued: 10/20/2015
• Est. Priority Date: 01/15/2015
• Status: Active Grant

• Current Assignee: Blackpoint Holdings, LLC
• Original Assignee: Blackpoint Holdings, LLC
• Inventors: Murchison, Jon, Johnson, Bryan
• Primary Examiner(s): Elhag, Magdi
• Application Number:
  US14/598,092
• Time in Patent Office: 278 Days
• Field of Search: 455/404.2, 455/456.1, 455/456.2, 455/456.3, 455/457
• US Class Current: 1/1
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Systems and methods are disclosed for determining locations visited by a mobile device. In an embodiment, a first location point is identified from a plurality of location points associated with the mobile device. The first location point may be combined with one or more of the plurality of location points to construct a time block. A time block may indicate a continuous period of time when the mobile device is in the same location. An aggregate location is calculated for the time block based on the plurality of points in the time block. One or more time blocks may be grouped based on the aggregate location of each time block, and a spatial clustering procedure is applied to transform the aggregate locations of time blocks in the group into one or more locations of interest.

Claims

1. A system for determining locations visited by a mobile device, comprising:

one or more computing devices;

a database storing a plurality of location points, wherein each location point is associated with the mobile device;

an updater, implemented on the one or more computing devices, configured to;

receive a location point from the mobile device; and

store the location point in the database;

a query manager, implemented on the one or more computing devices, configured to;

receive a query for a plurality of location points associated with the mobile device; and

retrieve the plurality of location points associated with the mobile device from the database based on the query;

an analyzer, implemented on the one or more computing devices, configured to;

send a query to the query manager for the plurality of location points;

receive the plurality of location points from the query manager;

identify a first location point from the plurality of location points;

construct a time block from the first location point and one or more of the plurality of location points, wherein the time block indicates a period of time when the mobile device is in a determined location, and wherein the analyzer is further configured to construct a time block by;

iterating chronologically through the plurality of location points from the first location point to identify a second location point, wherein the second location point is identified based on a calculated score above a first score threshold or below a second score threshold, and wherein the first score threshold is higher than the second score threshold; and

including the second location point and each iterated location point between the first and second location points in the time block when the calculated score is above the first score threshold; and

calculate an aggregate location for the time block based on the plurality of location points in the time block; and

a consolidator, implemented on the one or more computing devices, configured to apply a spatial clustering procedure to transform the aggregate locations of one or more time blocks into one or more locations of interest.

2. The system of claim 1, further comprising a presenter configured to display the one or more locations of interest on a map in a graphical user interface.

3. The system of claim 1, wherein the analyzer is further configured to:

receive a location speed and a horizontal location accuracy for the first location point, and wherein the location speed of the first location point is below a speed threshold and the horizontal location accuracy of the first location point is above a location accuracy threshold.

4. The system of claim 1, wherein the analyzer is further configured to construct the time block by:

iterating chronologically through the plurality of location points from the second location point to identify an additional location point based on a second calculated score, wherein the second calculated score is above the first score threshold or below the second score threshold;

including the additional location point and each iterated location point between the second location point and the additional location point in the time block when the second calculated score is above the first score threshold; and

repeating the steps of iterating and including when the second calculated score is above the first score threshold, wherein the plurality of location points are iterated chronologically from the additional location point.

5. The system of claim 1, wherein the iterating comprises iterating through the plurality of location points chronologically forward in time based on a timestamp of each location point.

6. The system of claim 1, wherein the iterating comprises iterating through the plurality of location points chronologically backward in time based on a timestamp of each location point.

7. The system of claim 1, wherein the analyzer is further configured to calculate the calculated score by:

determining a speed score based on a location speed of the second location point;

determining a distance score based on a computed distance between the first location point and the second location point;

determining an accuracy score based on a horizontal location accuracy of the second location point; and

transforming the speed score, the distance score, and the accuracy score into a single score based on predefined weights assigned to the speed score, the distance score, and the accuracy score.

8. The system of claim 1, wherein the calculated aggregate location is an average of the location points in the time block.

9. The system of claim 1, wherein the consolidator is further configured to group one or more constructed time blocks by:

determining a starting location;

identifying time blocks having aggregate locations within a threshold distance of the starting location; and

grouping together the identified time blocks into a group.

10. The system of claim 1, wherein the plurality of location points comprise locations derived from global positioning system (GPS) data.

11. The system of claim 1, wherein the plurality of location points comprise locations derived from cellular, Wi-Fi, and Bluetooth connections of the mobile device.

12. The system of claim 1, wherein the location of interest is assigned a label and one or more tags.

13. The system of claim 1, wherein:

the calculated score being above the first score threshold indicates that the second location point should be included in the time block;

the calculated score being below the second threshold indicates that the second location point should not be included in the time block; and

the calculated score being between the first score threshold and the second score threshold indicates that it cannot be determined from the calculated score whether the second location point should be included in the time block.

14. A method for determining locations visited by a mobile device, comprising:

identifying a first location point from a plurality of location points associated with the mobile device;

constructing a time block from the first location point and one or more of the plurality of location points, wherein the time block indicates a period of time when the mobile device is in a determined location, and wherein constructing the time block further comprises;

iterating chronologically through the plurality of location points from the first location point to identify a second location point, wherein the second location point is identified based on a calculated score above a first score threshold or below a second score threshold, and wherein the first score threshold is higher than the second score threshold; and

including the second location point and each iterated location point between the first and second location points in the time block when the calculated score is above the first score threshold;

calculating an aggregate location for the time block based on the plurality of location points in the time block; and

applying a spatial clustering procedure to transform the aggregate locations of one or more time blocks into one or more locations of interest.

15. The method of claim 14, further comprising displaying the one or more locations of interest on a map in a graphical user interface.

16. The method of claim 14, further comprising:

receiving a location speed and a horizontal location accuracy for the first location point, wherein the location speed of the first location point is below a speed threshold and the horizontal location accuracy of the first location point is above a location accuracy threshold.

17. The method of claim 14, wherein the constructing further comprises:

iterating chronologically through the plurality of location points from the second location point to identify an additional location point based on a second calculated score, wherein the second calculated score is above the first score threshold or below the second score threshold;

including the additional location point and each iterated location point between the second location point and the additional location point in the time block when the second calculated score is above the first score threshold; and

repeating the steps of iterating and including when the second calculated score is above the first score threshold, wherein the plurality of location points are iterated chronologically from the additional location point.

18. The method of claim 14, wherein the iterating comprises iterating through the plurality of location points forward in time based on a timestamp of each location point.

19. The method of claim 14, wherein the iterating comprises iterating through the plurality of location points backward in time based on a timestamp of each location point.

20. The method of claim 17, further comprising calculating the calculated score, wherein the calculating comprises:

determining a speed score based on a speed of the second location point;

determining a distance score based on a computed distance between the first location point and the second location point;

determining an accuracy score based on a horizontal location accuracy of the second location point; and

transforming the speed score, the distance score, and the accuracy score into a single score based on predefined weights assigned to the speed score, the distance score, and the accuracy score.

21. The method of claim 14, wherein the calculated aggregate location is an average of the location points in the time block.

22. The method of claim 14, further comprising grouping the time blocks into a group, wherein the grouping comprises:

determining a starting location;

identifying time blocks having aggregate locations within a threshold distance of the starting location; and

grouping together the identified time blocks into a group.

23. The method of claim 14, wherein:

the calculated score being above the first score threshold indicates that the second location point should be included in the time block;

the calculated score being below the second threshold indicates that the second location point should not be included in the time block; and

the calculated score being between the first score threshold and the second score threshold indicates that it cannot be determined from the calculated score whether the second location point should not be included in the time block.

24. A non-transitory computer-readable storage device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

identifying a first location point from a plurality of location points associated with a mobile device;

constructing a time block from the first location point and one or more of the plurality of location points, wherein the time block indicates a period of time when the mobile device is in a determined location, and wherein constructing the time block further comprises;

iterating chronologically through the plurality of location points from the first location point to identify a second location point, wherein the second location point is identified based on a calculated score above a first score threshold or below a second score threshold, and wherein the first score threshold is higher than the second score threshold; and

including the second location point and each iterated location point between the first and second location points in the time block when the calculated score is above the first score threshold;

calculating an aggregate location for the time block based on the plurality of location points in the time block; and

applying a spatial clustering procedure to transform the aggregate locations of one or more time blocks into one or more locations of interest.