Back to results
US 10,592,914 B2Granted
Device-dwell graphs
AssigneePlaceIQ, Inc.
InventorSteven Milton
Life of this patent
Estimating the term…
Abstract
Provided is a process that determines a device-dwell graph based on noisy reported geolocations for mobile computing devices.
Claims20
A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations to infer a geographic place of interest visited by a mobile computing device based on geolocation measurements of the mobile computing device that are individually too inaccurate to determine whether the mobile computing device is at the geographic place of interest or other adjacent geographic places of interest, the operations comprising:
- obtaining, with one or more processors, a location history of a mobile computing device, wherein:
- the location history comprises a plurality of time-stamped geolocations of the mobile computing device determined based on wireless signals received by the mobile computing device;
- the time-stamped geolocations have respective geographic confidence areas associated therewith;
- at least some of the time-stamped geolocations indicate a less than 80% probability that the mobile computing device is within 10 meters of a respective time-stamped geolocation at a time at least some wireless signals upon which the respective time-stamped geolocation is determined were received by the mobile computing device;
- and
- the obtained location history includes time-stamped geolocations that collectively span a duration of time greater than one minute;
- for each of the geographic confidence areas of the time-stamped geolocations, determining, with one or more processors, a respective set of places of interest geographically overlapping the respective confidence area by:
- querying a geographic information system for places of interest that geographically overlap the respective geographic confidence areas;
- and
- receiving the respective set of places of interest in a response to the query from the geographic information system, wherein:
- the respective places of interest are specified by a respective bounding polygon in which vertices of the respective bounding polygon correspond to geographic coordinates;
- and
- the respective bounding polygons define perimeters of geographic areas of the respective places of interest for which overlap is determined;
- forming, with one or more processors, based on the determined sets of places of interest, a device-dwell graph, wherein:
- nodes of the device-dwell graph correspond to respective places of interest in the determined sets of places of interest;
- edges of the device-dwell graph respectively connect a first node and a second node of a pair of nodes in the nodes of the device-dwell graph, at least some of the edges connecting different pairs of nodes;
- and
- edges of the device-dwell graph correspond to respective co-occurrences of places of interest in respective determined sets of places of interest, such that a given edge is based on a given time-stamped geolocation having a given geographic confidence area that overlaps a given pair of places of interest that correspond to a given pair of nodes connected by the given edge;
- determining, with one or more processors, based on the device-dwell graph, a plurality of strongly connected components of the device-dwell graph, wherein:
- each strongly connected component is a subgraph of the device-dwell graph;
- each strongly connected component comprises a plurality of nodes;
- and
- each node in each strongly connected component is reachable by every other node in the respective strongly connected component via edges of the respective strongly connected component;
- for each strongly connected component, selecting, with one or more processors, a place of interest from among a plurality of places of interest corresponding to nodes of the respective strongly connected component as a place of interest visited by the mobile computing device, wherein selecting comprises determining that at least some places of interest corresponding to nodes of the respective strongly connected component were not visited by the mobile computing device at times of at least some of the time-stamped geolocations;
- and
- storing, with one or more processors, the selected places of interest in memory in association with the mobile computing device.
23 more elements
A method, comprising:
- obtaining, with one or more processors, a location history of a mobile computing device, wherein:
- the location history comprises a plurality of time-stamped geolocations of the mobile computing device determined based on wireless signals received by the mobile computing device;
- the time-stamped geolocations have respective geographic confidence areas associated therewith;
- at least some of the time-stamped geolocations indicate a less than 80% probability that the mobile computing device is within 10 meters of a respective time-stamped geolocation at a time at least some wireless signals upon which the respective time-stamped geolocation is determined were received by the mobile computing device;
- and
- the obtained location history includes time-stamped geolocations that collectively span a duration of time greater than one minute;
- for each of the geographic confidence areas of the time-stamped geolocations, determining, with one or more processors, a respective set of places of interest geographically overlapping the respective confidence area by:
- querying a geographic information system for places of interest that geographically overlap the respective geographic confidence areas;
- and
- receiving the respective set of places of interest in a response to the query from the geographic information system, wherein:
- the respective places of interest are specified by a respective bounding polygon in which vertices of the respective bounding polygon correspond to geographic coordinates;
- and
- the respective bounding polygons define perimeters of geographic areas of the respective places of interest for which overlap is determined;
- forming, with one or more processors, based on the determined sets of places of interest, a device-dwell graph, wherein:
- nodes of the device-dwell graph correspond to respective places of interest in the determined sets of places of interest;
- edges of the device-dwell graph respectively connect a first node and a second node of a pair of nodes in the nodes of the device-dwell graph, at least some of the edges connecting different pairs of nodes;
- and
- edges of the device-dwell graph correspond to respective co-occurrences of places of interest in respective determined sets of places of interest, such that a given edge is based on a given time-stamped geolocation having a given geographic confidence area that overlaps a given pair of places of interest that correspond to a given pair of nodes connected by the given edge;
- determining, with one or more processors, based on the device-dwell graph, a plurality of strongly connected components of the device-dwell graph, wherein:
- each strongly connected component is a subgraph of the device-dwell graph;
- each strongly connected component comprises a plurality of nodes;
- and
- each node in each strongly connected component is reachable by every other node in the respective strongly connected component via edges of the respective strongly connected component;
- for each strongly connected component, selecting, with one or more processors, a place of interest from among a plurality of places of interest corresponding to nodes of the respective strongly connected component as a place of interest visited by the mobile computing device, wherein selecting comprises determining that at least some places of interest corresponding to nodes of the respective strongly connected component were not visited by the mobile computing device at times of at least some of the time-stamped geolocations;
- and
- storing, with one or more processors, the selected places of interest in memory in association with the mobile computing device.
23 more elements
Dependencies are inferred from the claim text.