Filtering and clustering crowd-sourced data for determining beacon positions

• US 9,179,435 B2
• Filed: 10/23/2013
• Issued: 11/03/2015
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lin, Jyh-Han, Bandhakavi, Sindhura, Basu, Pradipta Kumar
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): BHATTI, HASHIM S
• Application Number:
  US14/061,560
• Publication Number:
  US 20140057651A1
• Time in Patent Office: 741 Days
• Field of Search: None
• US Class Current: 1/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 identify a change in at least an elevation of a 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 and an altitude value 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 three dimensional 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 three-dimensional position for the beacon to identify a change in at least an elevation of the beacon by;

grouping the selected positioned observations into a plurality of clusters based at least on the altitude values;

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

determining the revised three-dimensional position for the beacon based on the positioned observations corresponding to the selected cluster.

2. The system of claim 1, wherein the processor is further programmed to:

adjust, in the memory area, the cluster start time for the beacon based on an earliest timestamp associated with the positioned observations corresponding to the selected cluster; and

remove from subsequent consideration the positioned observations having timestamps earlier than the adjusted cluster start time.

3. The system of claim 1, wherein the revised three-dimensional position for the beacon includes a revision to only the altitude value of the beacon.

4. The system of claim 1, wherein the processor is programmed to calculate the revised three-dimensional 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, wherein the error radius is based on a type or signal strength of the beacon.

7. The system of claim 1, wherein selecting one of the plurality of clusters based on the timestamps comprises selecting the cluster having a later initial observation time.

8. A method comprising:

grouping, by a computing device, a plurality of positioned observations for a beacon into a plurality of clusters based on a spatial distance, each positioned observation having a timestamp associated therewith, each cluster having positioned observations within a timestamp range associated with the respective cluster;

identifying, by a computing device, one of the plurality of clusters having a most recent timestamp;

for clusters other than the one of the plurality of clusters, determining, by a computing device, whether the timestamp range associated with the one of the plurality of clusters overlaps with the timestamp ranges associated with the other clusters; and

based on the determination, publishing a position associated with the one of the plurality of clusters as the position of the beacon.

9. The method of claim 8, wherein based on the determination that the timestamp range overlaps, the published position represents a most recent position of the beacon, and further comprising designating the beacon as a moving beacon.

10. The method of claim 8, wherein based on the determination that the timestamp range does not overlap, the published position represents a current position of the beacon, and further comprising designating the beacon as a moved beacon.

11. The method of claim 8, further comprising associating a threshold time with the beacon.

12. The method of claim 11, wherein one or more of the plurality of positioned observations are excluded, from being grouped into the plurality of clusters, based on the threshold time.

13. The method of claim 11, wherein each timestamp associated with the positioned observations is later than or equal to the threshold time.

14. The method of claim 8, wherein the plurality of positioned observations comprise crowd-sourced records each identifying one or more beacons observed by one of a plurality of computing devices.

15. The method of claim 8, wherein publishing the position comprises publishing a three-dimensional position of the beacon.

16. The method of claim 8, wherein the spatial distance is based on a type or signal strength of the beacon.

17. The method of claim 8, wherein said grouping, said identifying, and said determining are performed periodically.

18. A computing device comprising:

a memory area storing a plurality of three-dimensional positioned observations for a beacon; and

a processor configured to;

select, from the plurality of three-dimensional positioned observations for the beacon, one or more of the three-dimensional positioned observations having a timestamp later than or equal to a threshold time associated with the beacon;

group the selected three-dimensional positioned observations into a plurality of clusters based at least on a spatial distance;

select one of the plurality of clusters based on the timestamps; and

determine a revised three-dimensional position for the beacon based on the positioned observations corresponding to the selected cluster.

19. The computing device of claim 18, wherein the processor is further configured to:

adjust the threshold time for the beacon based on an earliest timestamp associated with the positioned observations corresponding to the selected cluster; and

remove from subsequent consideration the positioned observations having timestamps earlier than adjusted threshold time.

20. The computing device of claim 18, wherein the spatial distance includes elevation, and the revised three-dimensional position for the beacon includes a change in at least an altitude value for the beacon.