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

• US 20160189186A1
• Filed: 01/13/2015
• Published: 06/30/2016
• Est. Priority Date: 12/29/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Abdullah, Amirali, Vee, Erik Nathan, Fabrikant, Alexander
• Granted Patent: US 9,904,932 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

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.

Claims

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 set that includes the beacons observed by mobile devices tracked in each pair of localized segments where the beacon observations satisfy a predetermined beacon threshold level;

determining, by the one or more computing devices, a beacon overlap score for each beacon in the eligible beacon set; and

generating, by the one or more computing devices, an overall overlap score for each pair of localized segments under consideration by combining the beacon overlap scores for all beacons in the eligible beacon set for that pair of localized segments.

15. The computer-implemented method of claim 14, wherein lower beacon overlap scores for a given pair of localized segments indicate that signals from that beacon give stronger evidence that the given pair of localized segments do not overlap.

16. The computer-implemented method of claim 14, wherein the predetermined beacon threshold level is defined in terms of one or more of beacon distance metric values, the frequency with which the beacon is observed during the localized segment, and the number of times the beacon is observed during the localized segment.

17. The computer-implemented method of claim 9, wherein 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 comprises generating a forest data structure whose leaves correspond to the localized segments.

18. The computer-implemented method of claim 9, wherein determining semantic place data for one or more localized segments based at least in part on the clustering configuration comprises a pre-processing training subroutine that associates, by the one or more computing devices, a semantic data label to certain parts of the data structure responsive to receiving one or more localized segments with semantic data labels, and identifying, based at least in part on the clustering configuration, a classifier for one or more of the semantic data labels received, and an online subroutine which, responsive to one or more localized segments, associates, by the one or more computing devices, semantic data with the received segments, using the classifiers identified by the pre-processing training subroutine.

19. The computer-implemented method of claim 9, wherein determining semantic place data for one or more localized segments in each geographic region bucket based at least in part on the clustering configuration comprises determining, by the one or more computing devices, a semantic location probability value representing a likelihood that the plurality of location data reports constituting the localized segment was obtained while the device was at a given semantic location, wherein determining the semantic location probability value is based at least in part on the clustering configuration.

20. The computer-implemented method of claim 9, wherein determining semantic place data for one or more localized segments in each geographic region bucket based at least in part on the clustering configuration comprises generating, by the one or more computing devices, a prediction of the semantic place location for a new localized segment or one or more new location data reports based at least in part on the clustering configuration.

21. 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 plurality of location data reports from a plurality of mobile devices;

partitioning the plurality of location data reports into localized segments;

estimating a geographic region bucket for each localized segment;

identifying within each geographic region bucket, 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 the mobile devices generating the localized segments in that given pair;

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; and

determining semantic place data for one or more localized segments based at least in part on the clustering configuration of the generated data structure.

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.

22. The computing system of claim 21, 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.

23. The computing system of claim 21, wherein determining semantic place data for one or more localized segments in each geographic region bucket based at least in part on the clustering configuration comprises generating, by the one or more computing devices, a prediction of the semantic place location for a new localized segment or one or more new location data reports based at least in part on the clustering configuration.

23-1. The computing system of claim 21, wherein the semantic place 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.