Predicting or recommending a users future location based on crowd data

• US 8,589,330 B2
• Filed: 03/03/2010
• Issued: 11/19/2013
• Est. Priority Date: 03/25/2009
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Waldeck Technology, LLC (Concert Technology Corporation)
• Inventors: Petersen, Steven L., Amidon, Christopher M.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US12/716,314
• Publication Number:
  US 20120047102A1
• Time in Patent Office: 1,357 Days
• Field of Search: None
• US Class Current: 706/52
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A system and method for predicting a future location of a user are provided. In general, a prediction basis including crowd data describing crowds in which a user was included during a number of reoccurring time windows is generated. Each reoccurring time window may be, for example, a day of the week (i.e., Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, or Sunday), a portion of a day of the week (e.g., Monday Morning, Monday Afternoon, Monday Evening, Tuesday Evening, etc.), a day of the month (e.g., 1st day of the month), a day of the year (e.g., March 25th), or the like. The prediction basis of the user is then used to predict one or more future locations of the user.

Claims

1. A computer-implemented method comprising:

generating a prediction basis for a user comprising previous crowd data describing crowds in which the user was previously included during a plurality of reoccurring time windows; and

predicting one or more future locations of the user based on the prediction basis, wherein predicting the one or more future locations of the user based on the prediction basis comprises;

obtaining current crowd data describing a current crowd in which the user is currently included;

obtaining relevant crowd data from the prediction basis; and

determining whether the user is likely to move to one of the one or more future locations based on a comparison of the current crowd data and at least a subset of the relevant crowd data from the prediction basis.

2. The method of claim 1 wherein for each instance of each reoccurring time window of the plurality of time windows, the prediction basis of the user comprises crowd data describing a crowd in which the user was included during the instance of the reoccurring time window.

3. The method of claim 1 wherein the crowd data describing the crowds in which the user was previously included comprises a crowd size of each of the crowds.

4. The method of claim 1 wherein the crowd data describing the crowds in which the user was previously included comprises, for each crowd of the crowds, a degree of correlation between a user profile of the user and user profiles of other users in the crowd.

5. The method of claim 1 wherein the crowd data describing the crowds in which the user was previously included comprises, for each crowd of the crowds, a degree of correlation between user profiles of users in the crowd.

6. The method of claim 1 wherein the crowd data describing the crowds in which the user was previously included comprises one or more crowd characteristics of each of the crowds.

7. The method of claim 6 wherein the one or more crowd characteristics of each of the crowds comprises at least one of a group consisting of:

a best-case average Degree of Separation (DOS) for the crowd, a worst-case average DOS for the crowd, a degree of fragmentation of the crowd, a degree of bidirectionality of relationships of the crowd.

8. The method of claim 1 wherein generating the prediction basis for the user comprises:

detecting an instance of one of the plurality of reoccurring time windows;

obtaining crowd data for a crowd in which the user is located at a time at which the instance of the one of the plurality of reoccurring time windows is detected;

storing the crowd data as part of the prediction basis of the user; and

repeating the steps of detecting, obtaining, and storing for a plurality of instances of the plurality of reoccurring time windows.

9. The method of claim 1 wherein the relevant crowd data from the prediction basis is crowd data from the prediction basis for a one of the plurality of reoccurring time windows corresponding to a current time.

10. The method of claim 1 wherein the relevant crowd data from the prediction basis is crowd data from the prediction basis for a one of the plurality of reoccurring time windows immediately following a one of the plurality of reoccurring time windows corresponding to a current time.

11. The method of claim 1 wherein predicting the one or more future locations of the user based on the prediction basis further comprising, if the user is likely to move:

generating expected crowd criteria describing a type of a crowd in which the user is expected to be included based on the relevant crowd data from the prediction basis;

obtaining locations matching the expected crowd criteria; and

providing one or more of the locations matching the expected crowd criteria as the one or more future locations of the user.

12. The method of claim 11 wherein generating the expected crowd criteria describing the type of crowd in which the user is expected to be included comprises generating the expected crowd criteria based on all of the relevant crowd data from the prediction basis.

13. The method of claim 11 wherein the relevant crowd data comprises crowd data for a plurality of instances of one of the plurality of reoccurring time windows, and generating the expected crowd criteria describing the type of crowd in which the user is expected to be included comprises:

identifying one or more patterns in the crowd data for the plurality of instances of the one of the plurality of reoccurring time windows;

identifying an applicable pattern from the one or more patterns; and

generating the expected crowd criteria based on the crowd data for a subset of the plurality of instances of the one of the plurality of reoccurring time windows that are in the applicable pattern.

14. The method of claim 11 wherein the expected crowd criteria comprises a particular combination of values for a plurality of crowd data components.

15. The method of claim 11 wherein the expected crowd criteria comprises a range of values for each of at least one of a plurality of crowd data components.

16. The method of claim 11 wherein the locations matching the expected crowd criteria comprise one or more Points of Interest (POIs) at which crowds that match the expected crowd criteria to at least a threshold degree are currently located.

17. The method of claim 11 wherein the locations matching the expected crowd criteria comprise one or more Points of Interest (POIs) at which crowds that match the expected crowd criteria to at least a threshold degree are expected to be located at a future time.

18. The method of claim 11 wherein the locations matching the expected crowd criteria comprise a location of a crowd that currently matches the expected crowd criteria to at least a threshold degree.

19. The method of claim 11 wherein the locations matching the expected crowd criteria comprise a location of a crowd that is expected to match the expected crowd criteria to at least a threshold degree at a future time.

20. The method of claim 1 wherein determining whether the user is likely to move comprises determining whether the user is likely to move based on a comparison of the current crowd data and all of the relevant crowd data from the prediction basis.

21. The method of claim 1 wherein the relevant crowd data comprises crowd data for a plurality of instances of one of the plurality of reoccurring time windows, and determining whether the user is likely to move comprises:

identifying one or more patterns in the crowd data for the plurality of instances of the one of the plurality of reoccurring time windows;

identifying an applicable pattern from the one or more patterns; and

determining whether the user is likely to move based on a comparison of the current crowd data and a subset of the plurality of instances of the one of the plurality of reoccurring time windows that are in the applicable pattern.

22. The method of claim 1 wherein determining whether the user is likely to move comprises determining that the user is likely to move if the current crowd data is different from the at least a subset of the relevant crowd data from the prediction basis by more than a predefined threshold degree.

23. The method of claim 1 wherein determining whether the user is likely to move comprises determining whether the user is likely to move based on a vector magnitude of a vector between a point representing the current crowd data in n-dimensional space and one or more points representing the at least a subset of the relevant crowd data from the prediction basis in the n-dimensional space.

24. The method of claim 23 wherein the one or more points representing the at least a subset of the relevant crowd data from the prediction basis in the n-dimensional space is a combined point representing a combination of the relevant crowd data from the prediction basis in the n-dimensional space.

25. The method of claim 1 wherein each of the plurality of reoccurring time windows is time window that repeats at one of a group consisting of:

daily, weekly, bi-weekly, monthly, and yearly.

26. The method of claim 1 wherein predicting the one or more future locations comprises ranking the one or more future locations.

27. The method of claim 1 further comprising:

sending the one or more future locations to a device associated with the user for confirmation; and

receiving a confirmation from the device of the user in which the one or more future locations have been ranked by at least one of a group consisting of;

the device and the user at the device.

28. The method of claim 27 wherein the one or more future locations are ranked automatically by the device based on a location history for the user stored by the device.

29. The method of claim 1 further comprising:

receiving a prediction request from a requestor; and

returning the one or more future locations of the user to the requestor in response to the prediction request.

30. The method of claim 1 further comprising providing the one or more future locations of the user as one or more recommended future locations for the user.

31. A server comprising:

a communication interface communicatively coupling the server to a network; and

a controller associated with the communication interface and adapted to;

generate a prediction basis for a user comprising previous crowd data describing crowds in which the user was previously included during a plurality of reoccurring time windows; and

predict one or more future locations of the user based on the prediction basis, wherein when predicting the one or more future locations of the user based on the prediction basis, the controller is adapted to;

obtain current crowd data describing a current crowd in which the user is currently included;

obtain relevant crowd data from the prediction basis; and

determine whether the user is likely to move to one of the one or more future locations based on a comparison of the current crowd data and at least a subset of the relevant crowd data from the prediction basis.

32. A non-transitory computer-readable medium storing software for instructing a controller of a computing device to:

generate a prediction basis for a user comprising previous crowd data describing crowds in which the user was previously included during a plurality of reoccurring time windows; and

predict one or more future locations of the user based on the prediction basis, wherein when predicting the one or more future locations of the user based on the prediction basis the software for instructing a controller further instructs the controller of the computing device to;

obtain current crowd data describing a current crowd in which the user is currently included;

obtain relevant crowd data from the prediction basis; and

determine whether the user is likely to move to one of the one or more future locations based on a comparison of the current crowd data and at least a subset of the relevant crowd data from the prediction basis.