Analyzing Semantic Places and Related Data from a Plurality of Location Data Reports

Patent metadata

Field	Value
Publication number	US-2016189186-A1
Application number	US-201514595256-A
Country	US
Kind code	A1
Filing date	Jan 13, 2015
Priority date	Dec 29, 2014
Publication date	Jun 30, 2016
Grant date	—

Abstract

Computer-implemented methods and systems of determining semantic place data include receiving a plurality of location data reports from a plurality of mobile devices, partitioning them into localized segments, and estimating a geographic region bucket for each segment. For clustering canopies of localized segments identified as satisfying a potential geographic overlap characterization, an overlap score is calculated that correlates the overlap among actual geographic regions covered by movement of the mobile devices generating the localized segments in that given clustering canopy. A data structure that provides a hierarchical clustering configuration of the localized segments in each geographic region bucket is generated from the determined overlap scores. Additional semantic data for nodes in the data structure can also be provided.

First claim

What is claimed is:

1 . A computer-implemented method of determining semantic place data, comprising:
examining, by one or more computing devices, a plurality of time series of historical location data reports to determine their overlap; grouping, by the one or more computing devices, selected time series of location data reports that are determined to be sufficiently overlapping; assigning, by the one or more computing devices, location classifiers distinguishing one or more location entities based on the groupings of selected time series of historical location data reports that are determined to be sufficiently overlapping; and determining, by the one or more computing devices, semantic location data for one or more time series of current or historical location data reports using the assigned location classifiers.

2 . The computer-implemented method of claim 1 , wherein the semantic location data comprises one or more of a semantic place label for a location entity, categories or other metadata associated with a location entity, information about a venue location or geometry associated with a location entity, and one or more characterizations of distributions of behaviors, demographics, or psychographics of users who visit a location entity.

3 . The computer-implemented method of claim 1 , wherein examining the plurality of time series of historical location data reports to determine their overlap comprises determining an overlap score for pairs of time series that correlates with the overlap between geographic areas covered by movement of mobile devices generating the pairs of time series.

4 . The computer-implemented method of claim 3 , wherein grouping selected time series of historical location data reports that are determined to be sufficiently overlapping comprises clustering together time series of historical location data reports using their overlap scores as a clustering metric.

5 . A computing system, comprising:
one or more processors; and one or more memory devices, the one or more memory devices storing computer-readable instructions that when executed by the one or more processors, cause the one or more processors to perform operations, the operations comprising:
receiving a semantic location model that provides information about semantic places within one or more geographic region buckets, wherein the semantic location model is generated at least in part from hierarchical clustering algorithms performed on data derived from previous location data reports collected from a plurality of mobile devices operating in the one or more geographic region buckets;
providing one or more new location data reports indicative of a user's current or past geographic location; and
generating semantic place data associated with the provided one or more new location data reports by processing the one or more new location data reports using the semantic location model.

6 . The computing system of claim 5 , wherein the operation of receiving a semantic location model comprises receiving a hierarchical clustering configuration of the location data reports from each geographic region bucket, wherein the hierarchical clustering configuration comprises a forest data structure whose leaves correspond to the historical localized segments.

7 . The computing system of claim 5 , wherein the generated semantic place data comprise one or more of semantic place label for a location entity, categories or other metadata associated with a location entity, information about a venue location or geometry associated with a location entity, and one or more characterizations of distributions of behaviors, demographics, or psychographics of users who visit a location entity.

8 . The computing system of claim 5 , wherein the operation of receiving a semantic location model comprises receiving a model generated by the operations of:
identifying one or more clustering canopies of localized segments that satisfy a potential geographic overlap characterization; determining an overlap score for each pair of localized segments that have at least one clustering canopy in common, wherein the overlap score correlates with the overlap among the actual geographic areas covered by movement of mobile devices generating the localized segments in that given pair; and generating a data structure that provides a clustering configuration of the localized segments in each geographic region bucket, wherein the data structure is generated at least in part from the determined overlap scores.

9 . A computer-implemented method of determining semantic place data, comprising:
receiving, by one or more computing devices, a plurality of location data reports from a plurality of mobile devices; partitioning, by the one or more computing devices, the plurality of location data reports into localized segments; estimating, by the one or more computing devices, a geographic region bucket for each localized segment; identifying, by the one or more computing devices, within each geographic region bucket, one or more clustering canopies of localized segments that satisfy a potential geographic overlap characterization; determining, by the one or more computing devices, an overlap score for each pair of localized segments that have at least one clustering canopy in common, wherein the overlap score correlates with the overlap among the actual geographic areas covered by movement of the mobile devices generating the localized segments in that given pair; generating, by the one or more computing devices, a data structure that provides a clustering configuration of the localized segments in each geographic region bucket, wherein the data structure is generated at least in part from the determined overlap scores; and determining, by the one or more computing devices, semantic place data for one or more localized segments based at least in part on the clustering configuration of the generated data structure.

10 . The computer-implemented method of claim 9 , wherein the plurality of location data reports respectively comprise one or more of a time stamp, an estimated physical location, a model of the error in the physical location, sensor observations about one or more beacons containing a beacon identifier and a metric that correlates with distance to the beacon, a geocode, and a mobile device identifier.

11 . The computer-implemented method of claim 10 , wherein the plurality of location data reports comprise sensor observations about one or more beacons, wherein each sensor observation about a beacon comprises a Wi-Fi access point BSSID provided as a beacon identifier and a received signal strength indicator (RSSI) provided as a beacon distance metric.

12 . The computer-implemented method of claim 9 , wherein each localized segment corresponds to a time series during which a given mobile device stayed within a given localized geographic area.

13 . The computer-implemented method of claim 9 , wherein a clustering canopy is characterized by a beacon identifier, and includes all localized segments where the beacon identifier appears in at least a fixed number or fraction of the location data reports.

14 . The computer-implemented method of claim 9 , wherein the plurality of location data reports from the plurality of mobile devices respectively comprise one or more sensor beacon observations, and wherein determining, by the one or more computing devices, an overlap score for each pair of localized segments in each geographic region bucket that have at least one clustering canopy in common comprises:
designating, by the one or more computing devices, an eligible beacon

Assignees

• Google Inc

Inventors

• Fabrikant Alexander
• Abdullah Amirali
• Vee Erik Nathan

Classifications

• H04W4/029

  Location-based management or tracking services · CPC title

• H04W4/026

  using orientation information, e.g. compass · CPC title

• H04W4/80

  Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication · CPC title

• H04W4/027

  using movement velocity, acceleration information · CPC title

• G06F16/29

  Geographical information databases · CPC title