Determining semantic place names from location reports

• US 9,787,557 B2
• Filed: 04/28/2015
• Issued: 10/10/2017
• Est. Priority Date: 04/28/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Leblanc, Gabriel, Fraser, Robert Malcolm, Su, Min-yian, Rosenstock, Jesse, Mehta, Bhaskar, Khirwadkar, Tanmay Sanjay
• Primary Examiner(s): Mundur, Padma
• Application Number:
  US14/697,733
• Publication Number:
  US 20160323159A1
• Time in Patent Office: 896 Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Systems and methods for determining semantic place names from one or more location reports received from a user device are provided. High quality visits for a candidate semantic place location from a plurality of previously obtained location reports can be aggregated and used to generate a point cloud for the semantic place location. A high quality visit can correspond to a visit by a device that is determined to be associated with a candidate semantic place location with greater likelihood relative to a plurality of other candidate semantic place locations. Data associated with one or more point clouds can be accessed and used to support determinations of semantic place name for one or more location reports. In example embodiments, the semantic place name can be stored as part of a location history and/or provided for display in a user interface presented on a display device.

Claims

1. A computer-implemented method of determining a semantic place name visited by a user device, comprising:

receiving, by one or more processors, at least one location report associated with a user device;

accessing, by the one or more processors, data associated with one or more point clouds, each point cloud associated with a candidate semantic place location, each point cloud generated from previously obtained location reports aggregated for a plurality of different devices, each point cloud comprising a plurality of data points, each of the plurality of data points corresponding to a high quality visit by one of the plurality of different devices to the candidate semantic place location associated with the point cloud; and

identifying, by the one or more processors, the semantic place name visited by the user device based at least in part on a match between the location report and the one or more point clouds;

wherein each high quality visit is identified, by the one or more processors, as a visit by one of the plurality of different devices that is determined to be associated with the candidate semantic place location with greater than a threshold confidence score relative to a plurality of other candidate semantic place locations.

2. The computer-implemented method of claim 1, further comprising:

providing for display, by the one or more processors, the semantic place name in a user interface presented on a display device.

3. The computer-implemented method of claim 1, further comprising:

storing, by the one or more processors, the semantic place name as part of a location history for the user device.

4. The method of claim 1, wherein identifying, by the one or more processors, the semantic place name based at least in part on the location report associated with the user device and the one or more point clouds comprises:

accessing, by the one or more processors, a pattern extracted from the one or more point clouds, the pattern comprising a plurality geographic cells, each geographic cell providing a probability value of being located at each of one or more candidate semantic place names, the probability value being determined based at least in part on the one or more point clouds;

matching, by the one or more processors, the location report to one of the plurality of geographic cells; and

determining, by the one or more processors, the semantic place name based at least in part on the probability value associated with the geographic cell matched to the location report.

5. The method of claim 1, wherein each of the plurality of point clouds is generated based at least in part by performing operations, the operations comprising:

receiving, by the one or more processors, a location report from one of the plurality of devices;

determining, by the one or more processors, that the location report corresponds to a high quality visit;

identifying, by the one or more processors, the candidate semantic place location corresponding to the high quality visit; and

generating a data point for the point cloud associated with the candidate semantic place location based at least in part on the location report.

6. The method of claim 5, wherein the operation of determining, by the one or more processors, that the location report corresponds to a high quality visit comprises:

identifying, by the one or more processors, a plurality of candidate semantic place locations for the location report;

determining, by the one or more processors, a confidence score for each of the plurality of candidate semantic place locations for the location report, the confidence score indicative of the likelihood that the location report occurred during a visit to the candidate semantic place location; and

determining, by the one or more processors, that the location report corresponds to a high quality visit based at least in part on the confidence score for each of the plurality of candidate semantic place locations.

7. The method of claim 6, wherein the confidence score for each of the plurality of candidate semantic place locations is determined based at least in part on one or more signals indicative of semantic place location for the location report.

8. The method of claim 7, wherein the one or more signals indicative of semantic place location are based at least in part on one or more of a distance to the candidate semantic place location, search history, wireless network scans, social signals, or past location reports.

9. The method of claim 6, wherein the operation of determining, by the one or more processors, that the location report corresponds to a high quality visit comprises determining, by the one or more processors, that the location report corresponds to a high quality visit when the confidence score for one of the plurality of candidate semantic place locations is greater than a threshold confidence score to the plurality of other candidate semantic place locations.

10. 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;

obtaining a first location report associated with a first device;

determining that the first location report corresponds to a high quality visit for a candidate semantic place location;

generating a data point for a point cloud associated with the candidate semantic place location based at least in part on first location report; and

associating the data point with the point cloud for the candidate semantic place location in the one or more memory devices;

wherein the first location report is determined to correspond to a high quality visit when the first location report is determined to be associated with the candidate semantic place location greater than a threshold confidence score relative to a plurality of other candidate semantic place locations;

wherein determining that the first location report corresponds to a high quality visit for a candidate semantic place location further comprises;

identifying a plurality of candidate semantic place locations for the first location report;

determining a confidence score for each of the plurality of candidate semantic place locations for the first location report, the confidence score indicative of the likelihood that the first location report occurred during a visit to the candidate semantic place location; and

determining that the first location report corresponds to a high quality visit based at least in part on the confidence score for each of the plurality of candidate semantic place locations.

11. The computing system of claim 10, wherein the confidence score for each of the plurality of candidate semantic place locations is determined based at least in part on one or more signals indicative of semantic place location for the first location report, the one or more signals being based at least in part on a distance to the candidate semantic place location.

12. The computing system of claim 10, wherein the operation of determining that the first location report corresponds to a high quality visit comprises determining that the first location report corresponds to a high quality visit when the confidence score for one of the plurality of candidate semantic place locations is greater than a threshold confidence score relative to the plurality of other candidate semantic place locations.

13. The computing system of claim 10, wherein the operations further comprise:

receiving a second location report associated with a second device;

accessing the point cloud stored in the one or more memory devices; and

identifying a semantic place name visited by the second device based at least in part on the second location report and the point cloud.

14. The computing system of claim 13, wherein the semantic place name visited by the second device is identified based at least in part on a match between the second location report and the point cloud.

15. The computing system of claim 13, wherein the operation of identifying a semantic place name visited by the second device based at least in part on the second location report and the point cloud comprises:

accessing a pattern determined based at least in part on the point cloud, the pattern comprising a plurality of geographic cells, each geographic cell providing a probability value of being located at each of one or more semantic place names, the probability value being determined based at least in part on the one or more point clouds;

matching the second location report to one of the plurality of geographic cells; and

determining the semantic place name based at least in part on the probability value associated with the geographic cell matched to the second location report.

16. One or more tangible, non-transitory computer-readable media storing computer-readable instructions that when executed by one or more processors cause the one or more processors to perform operations, the operations comprising:

receiving a location report associated with a user device;

accessing data associated with one or more point clouds, each point cloud associated with a semantic place location, each point cloud generated from previously obtained location reports aggregated for a plurality of different devices, each point cloud comprising a plurality of data points, each of the plurality of data points corresponding to a high quality visit by one of the plurality of different devices to the semantic place location associated with the point cloud; and

identifying the semantic place name visited by the user device based at least in part on a match between the location report and the one or more point clouds;

wherein each high quality visit is identified, by the one or more processors, as a visit by one of the plurality of different devices that is determined to be associated with a candidate semantic place location with greater than a threshold confidence score relative to a plurality of other candidate semantic place locations.

17. The one or more tangible, non-transitory computer-readable media of claim 16, wherein the operation of identifying the semantic place name based at least in part on the location report associated with the user device and the one or more point clouds comprises:

accessing a pattern extracted from the one or more point clouds, the pattern comprising a plurality of geographic cells, each geographic cell providing a probability value of being located at each of one or more candidate semantic place names, the probability value being determined based at least in part on the one or more point clouds;

matching the location report to one of the plurality of geographic cells; and

determining the semantic place name based at least in part on the probability value associated with the geographic cell matched to the location report.