Deduplicating Location Fingerprint Data

• US 20150346317A1
• Filed: 05/31/2014
• Published: 12/03/2015
• Est. Priority Date: 05/31/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Millman, David Benjamin, Huang, Joseph Ding-Jiu, Mayor, Robert, Lovich, Vitali, Patel, Abhinav R., Tay, Darin, Tsoong, Jessica Noel
• Granted Patent: US 9,304,185 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Methods, systems, and computer program product for deduplicating location fingerprint data for a venue are described. A system including a location server, or a mobile device, or both, can deduplicate the location fingerprint data. Deduplicating the location fingerprint data can include identifying correlated signal sources the signals of which are mutually dependent such that measurements of one signal source can be used to predict measurements of another. The system can determine a mutual information entropy value for each pair of signal sources, and identify the correlated signal sources based on high mutual information entropy value. The system can adjust weights of the correlated signal sources in location determination

Claims

1. A method comprising:

receiving survey data, the survey data comprising first measurements of signals from a first signal source and second measurements of signals from a second signal source;

determining a mutual information entropy value between the first measurements and the second measurements, the mutual information entropy value measuring a degree of mutual dependency between the first measurements and the second measurements;

storing the mutual information entropy value in an affinity matrix having a first dimension corresponding to the first signal source and the second signal source and a second dimension corresponding to the first signal source and the second signal source;

storing a respective control value for each of the first signal source and the second signal source in the affinity matrix, each control value measuring a degree of dependency of measurements obtained in a first survey of the respective signal source and measurements obtained in a second survey of the respective signal source, the first survey and second survey conducted at a same venue, the first survey and second survey conducted at different time or by different sampling devices; and

determining a respective weight of measurements of signals from the first signal source and measurements of signals from the second signal source, the weights being used in location determination at the venue using the signals from the first and second signal sources respectively, wherein determining each weight to a respective signal source comprises determining a ratio between a control value of the signal source and a sum of the control value of the signal source and the mutual information entropy value.

2. The method of claim 1, wherein:

the signals are radio frequency (RF) signals detectable at the venue by at least one of the sampling devices,

each signal source is a wireless access point, and

each measurement comprises a measurement of a received signal strength indication (RSSI), a measurement of round-trip time (RTT), or both.

3. The method of claim 2, where determining the mutual information entropy value comprises determining a degree of linear correspondence between the first measurements and the second measurements, a higher degree of linear correspondence corresponds to a higher mutual information entropy value.

4. The method of claim 1, wherein each weight is applied to a measurement of a signal of a respective signal source as determined by a mobile device configured to determine a location, at the venue, of the mobile device.

5. The method of claim 1, comprising determining a respective weight of the first signal source and the second signal source against a third signal source based on a respective mutual information entropy value of the respective signal source and the third signal source and based on a control value of the third signal source.

6. A method comprising:

receiving survey data, the survey data including measurements of signals from a signal source, the measurements being recorded in a survey at a venue;

determining a grid for the signal source, the grid including a plurality of cells and covering at least a portion of the venue, each cell corresponding to a portion of the venue and is associated with a distribution of measurements of the signals from the signal source as recorded in the cell; and

providing a representation of the grid, including the cells and corresponding distributions of measurements, to a user device as location fingerprint data for determining a location of the user device at the venue by matching readings of a sensor of the user device to the distributions of measurements in the grid.

7. The method of claim 6, wherein:

the signal source is a radio frequency (RF) signal source, and

the measurements include at least one of received signal strength indicators (RSSIs) or round trip time (RTT) of RF signals from the signal source.

8. The method of claim 6, wherein:

each cell having a cell size corresponding to a number of measurements recorded at the venue, wherein more measurements correspond to smaller cell.

9. The method of claim 6, wherein each cell is a rectangular area.

10. The method of claim 6, wherein each cell is associated with a number of measurements recorded in the cell, the number of measurements indicating a statistical confidence for determining the location of the user device in the venue, wherein a higher number indicates higher confidence.

11. The method of claim 6, wherein the distribution of measurements of signals includes a discrete distribution of a set of ranges of signal strength measurements and a number of measurements corresponding to each range.

12. The method of claim 6, wherein the distribution of measurements of signals includes a continuous distribution of a number of measurements over signal strength values, the continuous distributions being determined by performing a statistical fit of the number measurements over the signal strength values.

13. The method of claim 6, wherein determining the location of the user device at the venue comprising eliminating impossible locations in the venue where the user device is expected to have measurements corresponding to a cell but does not receive those measurements.

14. A system comprising:

one or more processors; and

a storage device storing computer instructions operable to cause the one or more processors to perform operations comprising;

receiving survey data, the survey data comprising first measurements of signals from a first signal source and second measurements of signals from a second signal source;

determining a mutual information entropy value between the first measurements and the second measurements, the mutual information entropy value measuring a degree of mutual dependency between the first measurements and the second measurements;

storing the mutual information entropy value in an affinity matrix having a first dimension corresponding to the first signal source and the second signal source and a second dimension corresponding to the first signal source and the second signal source;

storing a respective control value for each of the first signal source and the second signal source in the affinity matrix, each control value measuring a degree of dependency of measurements obtained in a first survey of the respective signal source and measurements obtained in a second survey of the respective signal source, the first survey and second survey conducted at a same venue, the first survey and second survey conducted at different time or by different sampling devices; and

determining a respective weight of measurements of signals from the first signal source and measurements of signals from the second signal source, the weights being used in location determination at the venue using the signals from the first and second signal sources respectively, wherein determining each weight to a respective signal source comprises determining a ratio between a control value of the signal source and a sum of the control value of the signal source and the mutual information entropy value.

15. The system of claim 14, wherein each weight is applied to a measurement of a signal of a respective signal source as determined by a mobile device configured to determine a location, at the venue, of the mobile device.

16. A non-transitory storage device storing computer instructions operable to cause one or more processors to perform operations comprising:

receiving survey data, the survey data comprising first measurements of signals from a first signal source and second measurements of signals from a second signal source;

determining a mutual information entropy value between the first measurements and the second measurements, the mutual information entropy value measuring a degree of mutual dependency between the first measurements and the second measurements;

storing the mutual information entropy value in an affinity matrix having a first dimension corresponding to the first signal source and the second signal source and a second dimension corresponding to the first signal source and the second signal source;

storing a respective control value for each of the first signal source and the second signal source in the affinity matrix, each control value measuring a degree of dependency of measurements obtained in a first survey of the respective signal source and measurements obtained in a second survey of the respective signal source, the first survey and second survey conducted at a same venue, the first survey and second survey conducted at different time or by different sampling devices; and

determining a respective weight of measurements of signals from the first signal source and measurements of signals from the second signal source, the weights being used in location determination at the venue using the signals from the first and second signal sources respectively, wherein determining each weight to a respective signal source comprises determining a ratio between a control value of the signal source and a sum of the control value of the signal source and the mutual information entropy value.

17. A system comprising:

one or more processors; and

a storage device storing computer instructions operable to cause the one or more processors to perform operations comprising;

receiving survey data, the survey data including measurements of signals from a signal source, the measurements being recorded in a survey at a venue;

determining a grid for the signal source, the grid including a plurality of cells and covering at least a portion of the venue, each cell corresponding to a portion of the venue and is associated with a distribution of measurements of the signals from the signal source as recorded in the cell; and

providing a representation of the grid, including the cells and corresponding distributions of measurements, to a user device as location fingerprint data for determining a location of the user device at the venue by matching readings of a sensor of the user device to the distributions of measurements in the grid.

18. The system of claim 17, wherein:

the signal source is a radio frequency (RF) signal source, and

the measurements include at least one of received signal strength indicators (RSSIs) or round trip time (RTT) of RF signals from the signal source.

19. The system of claim 17, wherein:

each cell having a cell size corresponding to a number of measurements recorded at the venue, wherein more measurements correspond to smaller cell.

20. A non-transitory storage device storing computer instructions operable to cause one or more processors to perform operations comprising:

receiving survey data, the survey data including measurements of signals from a signal source, the measurements being recorded in a survey at a venue;

determining a grid for the signal source, the grid including a plurality of cells and covering at least a portion of the venue, each cell corresponding to a portion of the venue and is associated with a distribution of measurements of the signals from the signal source as recorded in the cell; and

providing a representation of the grid, including the cells and corresponding distributions of measurements, to a user device as location fingerprint data for determining a location of the user device at the venue by matching readings of a sensor of the user device to the distributions of measurements in the grid.