Deduplicating location fingerprint data

Patent metadata

Field	Value
Publication number	US-9638784-B2
Application number	US-201514868813-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	May 31, 2014
Publication date	May 2, 2017
Grant date	May 2, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Apple Inc

Inventors

• Patel Abhinav R
• Tay Darin
• Millman David Benjamin
• Tsoong Jessica Noel
• Huang Joseph Ding-Jiu
• Mayor Robert
• Lovich Vitali

Classifications

• G01S5/02521 Primary

  using a radio-map · CPC title

• H04W4/02 Primary

  Services making use of location information · CPC title

• G01S5/0294

  Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering · CPC title

• G01S5/0289 Primary

  of multiple transceivers, e.g. in ad hoc networks · CPC title

• G01S5/0252

  Radio frequency fingerprinting · CPC title