Systems and methods for generating a user location history

• US 9,467,815 B2
• Filed: 03/20/2015
• Issued: 10/11/2016
• Est. Priority Date: 03/20/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wyatt, Daniel Mark, Bourassa-Denis, Renaud, Fabrikant, Alexander, Khirwadkar, Tanmay Sanjay, Murugesan, Prathab, Pickard, Galen Emmanuel, Rosenstock, Jesse, Schonberger, Rob, Teytelman, Anna
• Primary Examiner(s): Garcia, Santiago
• Application Number:
  US14/663,494
• Publication Number:
  US 20150271645A1
• Time in Patent Office: 571 Days
• Field of Search: 455/456.2
• US Class Current: 1/1
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Systems and methods for generating a user location history are provided. One example method includes obtaining a plurality of location reports from one or more devices associated with the user. The method includes clustering the plurality of location reports to form a plurality of segments. The method includes identifying a plurality of location entities for each of the plurality of segments. The method includes determining, for each of the plurality of segments, one or more feature values associated with each of the location entities identified for such segment. The method includes determining, for each of the plurality of segments, a score for each of the plurality of location entities based at least in part on a scoring formula. The method includes selecting one of plurality of locations entities for each of the plurality of segments.

Claims

1. A method for generating a location history for a user, the method comprising:

obtaining, by one or more computing devices, a plurality of location reports from one or more devices associated with the user, wherein each of the plurality of location reports indicates an associated location and time;

clustering, by the one or more computing devices, the plurality of location reports to form a plurality of segments, wherein each of the plurality of segments includes one or more of the plurality of location reports, wherein clustering, by the one or more computing devices, the plurality of location reports to form the plurality of segments comprises;

determining, by the one or more computing devices, a score for each of a plurality of candidate segments, wherein each of the plurality of candidate segments includes one or more of the plurality of location reports, and

selecting, by the one or more computing devices, two or more of the plurality candidate segments to serve as the plurality of segments based at least in part on the scores respectively determined for the plurality of candidate segments;

identifying, by the one or more computing devices, a plurality of location entities for each of the plurality of segments, wherein the plurality of location entities for each of the plurality of segments comprise location entities that are located approximate to one or more of the locations associated with one or more of the location reports included in such segment;

determining, by the one or more computing devices for each of the plurality of segments, one or more feature values associated with each of the location entities identified for such segment, wherein the one or more feature values are respectively determined for one or more features describing information about the location entity being valued;

determining, by the one or more computing devices for each of the plurality of segments, a score for each of the plurality of location entities based at least in part on a scoring formula, wherein the scoring formula provides the score for each location entity based at least in part on a comparison of the one or more feature values associated with the location entity being scored versus the feature values associated with all other location entities identified for the segment of the location entity being scored;

selecting, by the one or more computing devices, one of the plurality of locations entities for each of the plurality of segments for inclusion in the location history based at least in part of the scores associated with the plurality of location entities; and

displaying, by the one or more computing devices, one or more of the selected location entities in a user interface.

2. The method of claim 1, wherein clustering, by the one or more computing devices, the plurality of location reports to form the plurality of segments comprises clustering, by the one or more computing devices, the plurality of location reports based at least in part on the plurality of locations respectively associated with the plurality of location reports.

3. The method of claim 1, wherein the score for each of the plurality of candidate segments is based at least in part on a distance from each location report included in such candidate segment to a mean location associated with such candidate segment.

4. The method of claim 1, wherein:

a starting time and an ending time are respectively associated with each of the plurality of segments, the starting time for each of the plurality of segments being the earliest time associated with any location report included in such segment, the ending time for each of the plurality of segments being the latest time associated with any location report included in such segment; and

the method further comprises discarding any of the plurality of segments for which the ending time is less than a threshold time later than the starting time.

5. The method of claim 1, wherein the one or more features comprise one or more distance features describing a distance between the location entity being valued and a segment location associated with the segment with respect to which the location entity was identified.

6. The method of claim 1, wherein the one or more features comprise one or more popularity features describing a popularity of the location entity being valued.

7. The method of claim 6, wherein the one or more popularity features comprise one or more of a number of social media mentions associated with the location entity being valued, a number of check-ins associated with the location entity being valued, a number of requests for directions to the location entity being valued, and a global popularity rank associated with the location entity being valued.

8. The method of claim 1, wherein the one or more features comprise a business hour overlap feature describing whether a set of business hours associated with the location entity being valued overlap with a segment time associated with the segment with respect to which the location entity being valued was identified.

9. The method of claim 1, wherein the one or more features comprise one or more personalization features describing previous interactions between the user and the location entity being valued.

10. The method of claim 9, wherein the one or more personalization features comprise one or more of a number of instances in which the user performed a map click with respect to the location entity being valued, a number of instances in which the user requested directions to the location entity being valued, a number of instances in which the user has checked-in to the location entity being valued, and a number of instances in which the user has performed a web search query with respect to the location entity being valued.

11. The method of claim 9, wherein the one or more personalization features further describe a temporal correlation between the previous interactions between the user and the location entity being valued and a segment time associated with the segment for which the location entity being valued was identified.

12. The method of claim 1, further comprising:

providing, by the one or more computing devices, the location history for display in a user interface;

receiving, by the one or more computing devices, data associated with a user input received from the user via the user interface, wherein the user input requests one or more edits to the location history; and

revising, by the one or more computing devices, the location history based on the data associated with the user input such that the one or more edits requested by the user input are effectuated.

13. The method of claim 12, further comprising:

providing, by the one or more computing devices for at least one of the plurality of segments, one or more of the location entities that were not selected for inclusion in the location history for display in the user interface;

wherein the user input specifies one of the one or more of the location entities that were not selected for inclusion in the location history as a replacement for the location entity that was selected for inclusion in the location history; and

wherein revising, by the one or more computing devices, the location history based on the data associated with the user input comprises replacing in the location history, by the one or more computing devices, the location entity that was selected for inclusion in the location history with the location entity specified by the user input.

14. The method of claim 1, further comprising:

receiving, by the one or more computing devices, data describing a search query received from the user, wherein the search query references one or more location entities the user has visited;

identifying, by the one or more computing devices, one or more location entities included in the location history based at least in part on the search query; and

providing as results for the search query, by the one or more computing devices, the one or more location entities included in the location history and identified based at least in part on the search query.

15. A system comprising:

one or more computing devices; and

one or more non-transitory computer-readable media storing instruction that, when executed by the one or more computing devices, cause the one or more computing devices to perform operations, the operations comprising;

obtaining a plurality of location reports from one or more devices associated with the user, wherein each of the plurality of location reports indicates an associated location and time;

clustering the plurality of location reports to form a plurality of segments, wherein each of the plurality of segments includes one or more of the plurality of location reports, wherein clustering the plurality of location reports to form the plurality of segments comprises;

determining a score for each of a plurality of candidate segments, wherein each of the plurality of candidate segments includes one or more of the plurality of location reports, and

selecting two or more of the plurality candidate segments to serve as the plurality of segments based at least in part on the scores respectively determined for the plurality of candidate segments;

identifying a plurality of location entities for each of the plurality of segments, wherein the plurality of location entities for each of the plurality of segments comprise location entities that are located approximate to one or more of the locations associated with one or more of the location reports included in such segment;

determining, for each of the plurality of segments, one or more feature values associated with each of the location entities identified for such segment, wherein the one or more feature values are respectively determined for one or more features describing information about the location entity being valued;

determining, for each of the plurality of segments, a score for each of the plurality of location entities based at least in part on a scoring formula, wherein the scoring formula provides the score for each location entity based at least in part on a comparison of the one or more feature values associated with the location entity being scored versus the feature values associated with all other location entities identified for the segment of the location entity being scored;

selecting one of plurality of locations entities for each of the plurality of segments for inclusion in the location history based at least in part of the scores associated with the plurality of location entities; and

displaying, by the one or more computing devices, one or more of the selected location entities in a user interface.

16. The system of claim 15, wherein the one or more features describing information about the location entity being valued comprise one or more distance features describing a distance between the location entity being valued and a segment location associated with the segment with respect to which the location entity being valued was identified, a business hour overlap feature describing whether a set of business hours associated with the location entity being valued overlap with a segment time associated with the segment for which the location entity being valued was identified, one or more personalization features describing previous interactions between the user and the location entity being valued, or one or more popularity features describing a popularity of the location entity being valued.

17. The system of claim 15, wherein the operations further comprise editing the location history based on user input received via a user interface.

18. A computing system comprising:

one or more processors; and

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

obtaining a plurality of location reports respectively indicating a time and a location, the plurality of location reports being associated with one or more devices associated with a user;

clustering the plurality of location reports into a plurality of segments based at least in part on the locations respectively associated with the plurality of location reports, wherein clustering the plurality of location reports to form the plurality of segments comprises;

determining a score for each of a plurality of candidate segments, wherein each of the plurality of candidate segments includes one or more of the plurality of location reports, and

selecting two or more of the plurality candidate segments to serve as the plurality of segments based at least in part on the scores respectively determined for the plurality of candidate segments;

for each segment of the plurality of segments;

identifying a plurality of location entities that are approximate to the location of at least one of the location reports included in such segment;

determining, for each location entity identified for such segment, a plurality of feature values respectively associated with a plurality of features, wherein the plurality of features describe information associated with the location entity being valued;

determining, for each location entity identified for such segment, a score based at least in part on a scoring formula, wherein the scoring formula provides a score for each location entity based at least in part on a comparison of the plurality of feature values associated with the location entity being scored to the plurality of feature values respectively associated with all other location entities identified for such segment; and

displaying one or more of the location entities in a user interface.

19. The computing system of claim 18, wherein the operations further comprise, for each segment, selecting one of the plurality of location entities for inclusion in a location history associated with the user based at least in part on the plurality of scores respectively associated with the plurality of location entities.

20. The computing system of claim 18, wherein the plurality of features comprise one or more distance features describing a distance between the location entity being scored and a segment location associated with the segment with respect to which the location entity being scored was identified and one or more personalization features describing previous interactions between the user and the location entity being scored.