Deduplicating location fingerprint data

• US 9,638,784 B2
• Filed: 09/29/2015
• Issued: 05/02/2017
• Est. Priority Date: 05/31/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Patel, Abhinav R., Tay, Darin, Millman, David Benjamin, Tsoong, Jessica Noel, Huang, Joseph Ding-Jiu, Mayor, Robert, Lovich, Vitali
• Primary Examiner(s): CAI, WAYNE HUU
• Application Number:
  US14/868,813
• Publication Number:
  US 20160021498A1
• Time in Patent Office: 581 Days
• Field of Search: 4554561-4565, 4554142
• 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 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;

determining that a first cell of the cells has not been surveyed by a sampling device performing the survey;

estimating measurements of signals from the signal sources at the first cell based on measurements recorded at cells surveyed by the sampling device;

associating the first cell with the estimated measurements; and

providing a representation of the grid, including the first cell and the associated estimated measurements, to a user device as location fingerprint data of the venue.

2. The method of claim 1, wherein:

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

the measurements include at least one of;

measured or estimated received signal strength indicators (RSSIs);

or

measured or estimated round trip time (RTT) of RF signals from the signal source.

3. The method of claim 1, wherein:

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

4. The method of claim 1, wherein estimating the measurements of signals from the signal sources at the first cell is based on at least one of interpolation or extrapolation of the measurements recorded at cells surveyed by the sampling device.

5. The method of claim 4, wherein estimating the measurements of signals from the signal sources at the first cell comprises:

determining that the first cell is located between two or more surveyed cells; and

estimating the measurements of signals from the signal sources at the first cell by interpolating measurements of the two or more surveyed cells.

6. The method of claim 4, wherein estimating the measurements of signals from the signal sources at the first cell comprises:

determining that the first cell is not located between surveyed cells; and

estimating the measurements of signals from the signal sources at the first cell by extrapolating measurements of surveyed cells based on signal propagation characteristics.

7. The method of claim 1, wherein the signal propagation characteristics include signal loss characteristics corresponding to a structure of the venue.

8. The method of claim 1, wherein the user device is configured to determine a location of the user device at the venue by 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.

9. 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 having a respective size;

determining respective measurements of each cell based on the survey data;

determining whether at least one set of the measurements of a corresponding cell is repetitive of previously stored measurements;

upon determining that the set of measurements is not repetitive, shrinking the size of the corresponding cell; and

providing a representation of the grid, including the cells, the sizes and corresponding measurements, to a user device as location fingerprint data of the venue.

10. The system of claim 9, wherein:

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

the measurements include at least one of;

measured or estimated received signal strength indicators (RSSIs);

or

measured or estimated round trip time (RTT) of RF signals from the signal source.

11. The system of claim 9, wherein:

at least a portion of the measurements are determined based on interpolation or extrapolation.

12. 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;

determining that a first cell of the cells has not been surveyed by a sampling device performing the survey;

estimating measurements of signals from the signal sources at the first cell based on measurements recorded at cells surveyed by the sampling device;

associating the first cell with the estimated measurements; and

providing a representation of the grid, including the first cell and the associated estimated measurements, to a user device as location fingerprint data of the venue.