Analyzing semantic places and related data from a plurality of location data reports

• US 9,904,932 B2
• Filed: 01/13/2015
• Issued: 02/27/2018
• Est. Priority Date: 12/29/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Fabrikant, Alexander, Abdullah, Amirali, Vee, Erik Nathan
• Primary Examiner(s): Jeanty, Romain
• Application Number:
  US14/595,256
• Publication Number:
  US 20160189186A1
• Time in Patent Office: 1,141 Days
• Field of Search: 705 711
• 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

1. A computer-implemented method of determining semantic place data, the method comprising:

receiving, by a computing system and from a plurality of different mobile computing devices, a plurality of location sensor time series;

partitioning, by the computing system, the plurality of location sensor time series into a plurality of localized segments, each localized segment of the plurality of localized segments corresponding to a time when a mobile device of the plurality of different mobile devices stayed within a given localized area;

characterizing, by the computing system, each localized segment of the plurality of localized segments as belonging to one or more geographic region buckets of a plurality of different geographic region buckets;

identifying, by the computing system, a plurality of clustering canopies, wherein identifying the plurality of clustering canopies comprises identifying, for each geographic region bucket of the plurality of different geographic region buckets, one or more clustering canopies;

determining, by the computing system, a set of overlap scores, wherein determining the set of overlap scores comprises determining, for each group of localized segments of the plurality of localized segments that shares at least one clustering canopy of the plurality of clustering canopies an overlap score that correlates with an overlap among geographic regions covered by movement of one or more mobile computing devices of the plurality of different mobile computing devices associated with one or more localized segments of the plurality of localized segments in the group;

generating, by the computing system and based on the set of overlap scores, a data structure that provides a hierarchical clustering of one or more localized segments of the plurality of localized segments in each geographic region bucket of the plurality of different geographic region buckets; and

determining, by the computing system and based on the data structure, semantic place data for one or more localized segments of the plurality of localized segments.

2. The computer-implemented method of claim 1, 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 psychographies of users who visit a location entity.

3. The computer-implemented method of claim 1, wherein the characterizing comprises:

determining a median estimated physical location of a user within a time slot of the localized segment; and

rounding the median estimated physical location to the one or more geographic region buckets.

4. The computer-implemented method of claim 1, wherein each clustering canopy of the plurality of clustering canopies comprises a group of localized segments of the plurality of localized segments in a geographic region bucket of the plurality of different geographic region buckets that satisfy a potential geographic overlap characterization.

5. The computer-implemented method of claim 4, wherein the potential geographic overlap characterization comprises the group of localized segments comprising data indicating that a given beacon identifier was observed.

6. The computer-implemented method of claim 1, wherein the data structure comprises a forest data structure comprising leaves that correspond to the plurality of localized segments.

7. The computer-implemented method of claim 1, wherein generating the data structure comprises utilizing a hierarchical agglomerative clustering algorithm to generate the data structure.

8. The computer-implemented method of claim 1, the method comprising, responsive to receiving, from a mobile computing device, a query comprising a location data report, predicting, based on the data structure, semantic place data for the mobile computing device.

9. A system for determining semantic place data, the system comprising:

one or more processors; and

a memory storing instructions that when executed by the one or more processors cause the system to perform operations, the operations comprising;

receiving, from a plurality of different mobile computing devices, a plurality of location sensor time series;

partitioning the plurality of location sensor time series into a plurality of localized segments, each localized segment of the plurality of localized segments corresponding to a time when a mobile device of the plurality of different mobile devices stayed within a given localized area;

characterizing each localized segment of the plurality of localized segments as belonging to one or more geographic region buckets of a plurality of different geographic region buckets;

identifying a plurality of clustering canopies, wherein identifying the plurality of clustering canopies comprises identifying, for each geographic region bucket of the plurality of different geographic region buckets, one or more clustering canopies;

determining a set of overlap scores, wherein determining the set of overlap scores comprises determining, for each group of localized segments of the plurality of localized segments that shares at least one clustering canopy of the plurality of clustering canopies an overlap score that correlates with an overlap among geographic regions covered by movement of one or more mobile computing devices of the plurality of different mobile computing devices associated with one or more localized segments of the plurality of localized segments in the group;

generating, based on the set of overlap scores, a data structure that provides a hierarchical clustering of one or more localized segments of the plurality of localized segments in each geographic region bucket of the plurality of different geographic region buckets; and

determining, based on the data structure, semantic place data for one or more localized segments of the plurality of localized segments.

10. The system of claim 9, 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.

11. The system of claim 9, wherein the characterizing comprises:

determining a median estimated physical location of a user within a time slot of the localized segment; and

rounding the median estimated physical location to the one or more geographic region buckets.

12. The system of claim 9, wherein each clustering canopy of the plurality of clustering canopies comprises a group of localized segments of the plurality of localized segments in a geographic region bucket of the plurality of different geographic region buckets that satisfy a potential geographic overlap characterization.

13. The system of claim 12, wherein the potential geographic overlap characterization comprises the group of localized segments comprising data indicating that a given beacon identifier was observed.

14. The system of claim 9, wherein the data structure comprises a forest data structure comprising leaves that correspond to the plurality of localized segments.

15. The system of claim 9, wherein generating the data structure comprises utilizing a hierarchical agglomerative clustering algorithm to generate the data structure.

16. The system of claim 9, the operations comprising, responsive to receiving, from a mobile computing device, a query comprising a location data report, predicting, based on the data structure, semantic place data for the mobile computing device.

17. One or more non-transitory computer-readable media comprising instructions that when executed by a computing system cause the computing system to perform operations, the operations comprising:

receiving, from a plurality of different mobile computing devices, a plurality of location sensor time series;

partitioning the plurality of location sensor time series into a plurality of localized segments, each localized segment of the plurality of localized segments corresponding to a time when a mobile device of the plurality of different mobile devices stayed within a given localized area;

characterizing each localized segment of the plurality of localized segments as belonging to one or more geographic region buckets of a plurality of different geographic region buckets;

identifying a plurality of clustering canopies, wherein identifying the plurality of clustering canopies comprises identifying, for each geographic region bucket of the plurality of different geographic region buckets, one or more clustering canopies;

determining a set of overlap scores, wherein determining the set of overlap scores comprises determining, for each group of localized segments of the plurality of localized segments that shares at least one clustering canopy of the plurality of clustering canopies an overlap score that correlates with an overlap among geographic regions covered by movement of one or more mobile computing devices of the plurality of different mobile computing devices associated with one or more localized segments of the plurality of localized segments in the group;

generating, based on the set of overlap scores, a data structure that provides a hierarchical clustering of one or more localized segments of the plurality of localized segments in each geographic region bucket of the plurality of different geographic region buckets; and

determining, based on the data structure, semantic place data for one or more localized segments of the plurality of localized segments.

18. The one or more non-transitory computer-readable media of claim 17, wherein the characterizing comprises:

determining a median estimated physical location of a user within a time slot of the localized segment; and

rounding the median estimated physical location to the one or more geographic region buckets.

19. The one or more non-transitory computer-readable media of claim 17, wherein each clustering canopy of the plurality of clustering canopies comprises a group of localized segments of the plurality of localized segments in a geographic region bucket of the plurality of different geographic region buckets that satisfy a potential geographic overlap characterization.

20. The one or more non-transitory computer-readable media of claim 19, wherein the potential geographic overlap characterization comprises the group of localized segments comprising data indicating that a given beacon identifier was observed.

21. The one or more non-transitory computer-readable media of claim 17, wherein the data structure comprises a forest data structure comprising leaves that correspond to the plurality of localized segments.

22. The one or more non-transitory computer-readable media of claim 17, wherein generating the data structure comprises utilizing a hierarchical agglomerative clustering algorithm to generate the data structure.

23. The one or more non-transitory computer-readable media of claim 17, the operations comprising, responsive to receiving, from a mobile computing device, a query comprising a location data report, predicting, based on the data structure, semantic place data for the mobile computing device.