US 9,432,805 B2 · Discovering and automatically sizing a place of relevance

Abstract

One or more mobile devices make measurements while moving along a path. Each measurement may comprise a specific group of identifiers of wireless transmitters, and strengths of corresponding wireless signals. A set of measurements are made in a sequence along a path, and the subsets of the measurements are identified for satisfying a test on a value of a measure of similarity of measurements included in the subset. A new place of relevance is identified, by comparing the just-described subsets of the measurements with similar subsets of additional measurements (e.g. by clustering). Alternatively, a known place of relevance (e.g. having a label) is identified, by comparing the just-described subsets of the measurements with pre-computed model of measurements. Also, the just-described subsets of the measurements may be compared with corresponding subsets of measurements of another path, e.g. to identify common portions therein.

Claims66

Dependent claims

A method of discovering places of relevance, comprising:

receiving, by a computing device, a set of measurements of wireless signals;
identifying, by the computing device, one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determining, by the computing device, based at least on comparing two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
storing in non-transitory memory, by the computing device, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the comparing comprises at least executing a similarity function to compare the two vectors.

5 more elements

A device for processing measurements, the device comprising:

a wireless transceiver;
one or more processors coupled to the wireless transceiver;
non-transitory memory coupled to the one or more processors;
and
software held in the non-transitory memory that when run in the one or more processors, causes the one or more processors to:
receive a set of measurements of wireless signals;
identify one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determine, based at least on comparison of two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
store in the non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the comparison comprises at least executing a similarity function to compare the two vectors.

10 more elements

A non-transitory computer readable storage medium comprising software to discover places of relevance, which when executed by a processor performs steps in a method comprising:

receiving a set of measurements of wireless signals;
identifying one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determining based at least on comparison of two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
storing in non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the comparison comprises at least executing a similarity function to compare the two vectors.

5 more elements

A system comprising a processor coupled to a memory and a wireless receiver, the system comprising:

means for obtaining a set of measurements of wireless signals;
means for identifying one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
means for determining based at least on comparing two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
means for storing in non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the comparison comprises at least executing a similarity function to compare the two vectors.

5 more elements

A method of discovering places of relevance, comprising:

receiving, by a computing device, a set of measurements of wireless signals;
identifying, by the computing device, one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determining, by the computing device, based at least on comparing two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
storing in non-transitory memory, by the computing device, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the identifying of the one or more places is based on comparing to a similarity threshold, a value of a measure of similarity of each measurement in the subset.

5 more elements

A device for processing measurements, the device comprising:

a wireless transceiver;
one or more processors coupled to the wireless transceiver;
non-transitory memory coupled to the one or more processors;
and
software held in the non-transitory memory that when run in the one or more processors, causes the one or more processors to:
receive a set of measurements of wireless signals;
identify one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determine, based at least on comparison of two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
store in the non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein identification of the one or more places is based on comparing to a similarity threshold, a value of a measure of similarity of each measurement in the subset.

10 more elements

A non-transitory computer readable storage medium comprising software to discover places of relevance, which when executed by a processor performs steps in a method comprising:

receiving a set of measurements of wireless signals;
identifying one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
determining based at least on comparison of two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
storing in non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the identifying of the one or more places is based on comparing to a similarity threshold, a value of a measure of similarity of each measurement in the subset.

5 more elements

A system comprising a processor coupled to a memory and a wireless receiver, the system comprising:

means for obtaining a set of measurements of wireless signals;
means for identifying one or more places, each place having a signal measurements centroid and a size of spatial expansion, the signal measurements centroid being computed by using at least a subset of measurements from multiple transmitters in the set of measurements of wireless signals;
wherein the signal measurements centroid comprises a vector of values of signal strengths, each value in the vector being computed based on a plurality of strengths of a corresponding wireless signal of a transmitter;
wherein the signal measurements centroid is based on measurements in the subset of each place being measured sequentially in time relative to one another along a real world path that starts in, ends in or passes through the each place;
means for determining based at least on comparing two vectors of values of signal strengths of two signal measurements centroids to one another, whether corresponding two places that have the two signal measurements centroids, are similar;
and
means for storing in non-transitory memory, a new place based on the corresponding two places being determined to be similar at least by comparison of the two vectors of values of signal strengths, the new place having a new signal measurements centroid and a new size of spatial expansion;
wherein the means for identifying comprises means for comparing to a similarity threshold, a value of a measure of similarity of each measurement in the subset.

5 more elements

Dependencies are inferred from the claim text.

Discovering and automatically sizing a place of relevance

Life of this patent

Discovering and automatically sizing a place of relevance

Life of this patent

Abstract

Claims66