Filtering and clustering crowd-sourced data for determining beacon positions

• US 8,577,389 B2
• Filed: 07/19/2011
• Issued: 11/05/2013
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Jyh-Han, Bandhakavi, Sindhura, Basu, Pradipta Kumar
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): BHATTI, HASHIM S
• Application Number:
  US13/185,520
• Publication Number:
  US 20120184292A1
• Time in Patent Office: 840 Days
• Field of Search: 370/328, 370/400, 455/456.1
• US Class Current: 455/456.1
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Embodiments analyze crowd-sourced data to identify a moved or moving beacon. The crowd-sourced data involving a particular beacon is filtered based on a cluster start time associated with the beacon. A clustering analysis groups the filtered crowd-sourced data for the beacon into a plurality of clusters based on spatial distance. Timestamps associated with the crowd-sourced data in the clusters are compared to select one of the clusters. The crowd-sourced data associated with the selected cluster is used to determine position information for the moved beacon. The cluster start time for the beacon is adjusted based on the earliest timestamp associated with the positioned observations corresponding to the selected cluster. Adjusting the cluster start time removes from a subsequent analysis the positioned observations associated with one or more prior positions of the beacon.

Claims

1. A system for applying a clustering analysis to a subset of positioned observations to determine a position of a moved beacon, said system comprising:

a memory area associated with a computing device, said memory area storing a plurality of positioned observations for a beacon, each of said positioned observations having a timestamp associated therewith, said beacon having a cluster start time associated therewith; and

a processor programmed to;

select, from the memory area, one or more of the positioned observations having a timestamp later than or equal to the cluster start time;

determine, for the beacon, a position and associated error radius based on the selected positioned observations;

compare the determined error radius with a pre-defined threshold radius; and

based on the comparison, calculate a revised position for the beacon by;

grouping the selected positioned observations into a plurality of clusters based on spatial distance;

selecting one of the plurality of clusters based on the timestamps;

determining the revised position for the beacon based on the positioned observations corresponding to the selected cluster; and

adjusting, in the memory area, the cluster start time for the beacon based on the earliest timestamp associated with the positioned observations corresponding to the selected cluster to remove from subsequent consideration the positioned observations associated with one or more prior positions of the beacon.

2. The system of claim 1, wherein the processor is further programmed to identify the positioned observations, stored in the memory area, having a timestamp earlier than the adjusted cluster start time.

3. The system of claim 2, wherein the processor is further programmed to delete the identified positioned observations from the memory area, flag the identified positioned observations in the memory area as being associated with a prior position of the beacons, or move the identified positioned observations from one portion of the memory area to another portion of the memory area.

4. The system of claim 1, wherein the processor is programmed to calculate the revised position if the determined error radius exceeds the pre-defined radius.

5. The system of claim 1, wherein the plurality of positioned observations comprise crowd-sourced records each identifying one or more beacons observed by one of a plurality of mobile computing devices.

6. The system of claim 1, further comprising means for using the cluster start time to omit positioned observations associated with one or more prior positions of the beacon from a k-means clustering analysis to determine the revised position of the beacon.

7. The system of claim 1, further comprising means for performing a k-means clustering analysis using a selected subset of the positioned observations to determine the position of the beacon that has changed position at least two times.

8. A method comprising:

selecting, by a computing device, one or more positioned observations from a plurality of positioned observations for a beacon, each of said selected positioned observations having a timestamp associated therewith that is later than or equal to a cluster start time associated with the beacon;

grouping, by a computing device, the selected positioned observations for the beacon into a plurality of clusters based on spatial distance;

selecting, by a computing device, one of the plurality of clusters based on the timestamps associated with the positioned observations corresponding to the clusters;

calculating, by a computing device, a position for the beacon based on the positioned observations corresponding to the selected cluster; and

adjusting the cluster start time for the beacon based on the earliest timestamp associated with the positioned observations corresponding to the selected cluster to remove from subsequent consideration the positioned observations associated with one or more prior positions of the beacon.

9. The method of claim 8, further comprising dividing the plurality of positioned observations into time periods based on the timestamps associated therewith.

10. The method of claim 9, further comprising performing the following operations using the positioned observations associated with each of the time periods in sequence:

said selecting the one or more positioned observations, said grouping the selected positioned observations, said selecting the one of the plurality of clusters, said calculating the position, and said adjusting the cluster start time.

11. The method of claim 8, wherein selecting one of the plurality of clusters comprises selecting one of the clusters having positioned observations with the most recent timestamps.

12. The method of claim 8, wherein grouping the positioned observations into the plurality of clusters comprises identifying one or more of the following:

a beacon identifier, a cluster number, a location of the beacon, a radius of the beacon, a maximum time stamp associated with the positioned observations, and a minimum time stamp associated with the positioned observations.

13. The method of claim 8, wherein grouping the positioned observations into the plurality of clusters comprises performing a k-means clustering analysis with spatial distance as a partition dimension.

14. The method of claim 8, further comprising comparing the timestamps associated with the positioned observations in a first cluster with the timestamps associated with the positioned observations in a second cluster.

15. The method of claim 14, further comprising defining the beacon as a moved beacon if the timestamps associated with the positioned observations in the first cluster are mutually exclusive to the timestamps associated with the positioned observations in the second cluster.

16. The method of claim 14, further comprising defining the beacon as a moving beacon if the timestamps associated with the positioned observations in the first cluster are not mutually exclusive to the timestamps associated with the positioned observations in the second cluster.

17. The method of claim 8, further comprising determining a position and error radius for the beacon based on the positioned observations, and wherein said grouping, said selecting, and said calculating are performed only if the determined error radius exceeds a pre-defined threshold radius, said pre-defined threshold radius being defined based on a type of the beacon.

18. One or more computer storage media embodying computer-executable components, said components comprising:

a pre-processing component that when executed by at least one processor causes the at least one processor to select one or more positioned observations from a plurality of positioned observations for a beacon, each of said selected positioned observations having a timestamp associated therewith that is later than or equal to a cluster start time associated with the beacon;

a cluster component that when executed by at least one processor causes the at least one processor to group the positioned observations selected by the pre-processing component into two clusters based on spatial distance, each of the two clusters having an initial observation time based on the positioned observations associated therewith;

a filter component that when executed by at least one processor causes the at least one processor to analyze the timestamps associated with the positioned observations corresponding to the two clusters from the cluster component to determine whether the timestamps associated with each cluster overlap with timestamps associated with the other cluster; and

a classification component that when executed by at least one processor causes the at least one processor to define the beacon as a moved beacon or a moving beacon based on the comparison performed by the filter component,

wherein the pre-processing component further adjusts the cluster start time for the beacon based on the earliest timestamp associated with the positioned observations corresponding to the cluster having a later initial observation time thereby removing from subsequent consideration the positioned observations associated with a prior position of the beacon.

19. The computer storage media of claim 18, further comprising a refiner component that when executed by at least one processor causes the at least one processor to calculate a position for the beacon based on the positioned observations corresponding to the cluster having the later initial observation time.

20. The computer storage media of claim 18, wherein the spatial distance includes elevation, and wherein the pre-processing component, the cluster component, the filter component, and the classification component are executed daily by a cloud-based service.