Prediction engine

• US 9,303,997 B2
• Filed: 11/15/2013
• Issued: 04/05/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: McGavran, Christine B., Moore, Bradford A., Bolsinga, Gregory D., Dal Santo, Michael P., Marti, Lukas, Pylappan, Seejo K., van Os, Marcel
• Primary Examiner(s): Anwari, Maceeh
• Application Number:
  US14/081,895
• Publication Number:
  US 20140278051A1
• Time in Patent Office: 872 Days
• Field of Search: 701/400
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/362 received from an external device or application, e.g. PDA, mobile phone or calendar application
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Some embodiments of the invention provide a novel prediction engine that (1) can formulate predictions about current or future destinations and/or routes to such destinations for a user, and (2) can relay information to the user about these predictions. In some embodiments, this engine includes a machine-learning engine that facilitates the formulation of predicted future destinations and/or future routes to destinations based on stored, user-specific data. The user-specific data is different in different embodiments. In some embodiments, the stored, user-specific data includes data about any combination of the following: (1) previous destinations traveled to by the user, (2) previous routes taken by the user, (3) locations of calendared events in the user'"'"'s calendar, (4) locations of events for which the user has electronic tickets, and (5) addresses parsed from recent e-mails and/or messages sent to the user. In some embodiments, the prediction engine only relies on user-specific data stored on the device on which this engine executes. Alternatively, in other embodiments, it relies only on user-specific data stored outside of the device by external devices/servers. In still other embodiments, the prediction engine relies on user-specific data stored both by the device and by other devices/servers.

Claims

1. A mobile device comprising:

at least one processing unit;

a prediction engine for execution by the processing unit;

a storage for storing derived locations based on the mobile device'"'"'s previous location history; and

the prediction engine for;

calculating a first set of ranking scores based on a first set of criteria for a set of the derived locations;

calculating a second set of ranking scores for a set of addresses harvested from a set of applications of the mobile device based on a second different set of criteria; and

formulating a set of predicted destinations for the mobile device from the set of derived locations and the set of harvested addresses based on the first and second sets of ranking scores.

2. The mobile device of claim 1,

wherein the prediction engine calculates the first and second sets of ranking scores based on a current location of the mobile device.

3. The mobile device of claim 2,

wherein each derived location is a region;

wherein the prediction engine is further for identifying a current derived location, wherein the current location of the mobile device falls within the current derived location'"'"'s region;

wherein the ranking score for each particular derived location of the set of derived locations expresses an affinity score between the particular derived location and the current derived location.

4. The mobile device of claim 1,

wherein the set of predicted destinations comprises a plurality of predicted destinations ordered according to the first and second sets of ranking scores.

5. The mobile device of claim 1, wherein the prediction engine comprises:

a destination identifier for analyzing the previous location history of the mobile device to identify a plurality of derived locations and storing the identified plurality of derived locations in the storage; and

a destination selector for querying the storage to identify a set of derived locations that is associated with a current location of the mobile device.

6. The mobile device of claim 5, wherein the prediction engine further comprises:

a region identifier for analyzing the previous location history of the mobile device to identify regions, and specifying a derived location for each identified region;

wherein the destination identifier is further for specifying, for the identified region of each derived location, a set of one or more identified regions as associated regions to which to travel from the identified region of the derived location.

7. The mobile device of claim 6, wherein the region identifier comprises a machine-learning engine for analyzing the previous location history of the mobile device to identify the regions.

8. The mobile device of claim 6,

wherein for the identified region of each derived location, the region identifier stores in the storage a set of other regions to which the mobile device travels from the identified region;

wherein the destination selector is further for determining whether the current location of the mobile device falls within one of the identified regions;

wherein when the current location falls within one of the identified regions, the destination selector specifies as a predicted destination the derived locations for the set of other regions that is specified in the storage for the identified region that contains the current location.

9. The mobile device of claim 6,

wherein for each region, the destination identifier stores, in the storage, a set of parameters that relate to transition into the region during at least one time interval;

wherein when the current location does not fall within one of the identified regions, the destination selector selects a derived location based on a probability of transitioning into the region of the derived location at a current time.

10. The mobile device of claim 1, wherein the prediction engine is a destination predictor, wherein the mobile device further comprises a route predictor for predicting routes to the predicted destinations.

11. The mobile device of claim 1 further comprising a navigation module for presenting a turn-by-turn navigation presentation to a predicted destination in response to a selection of a predicted destination of the set of predicted destinations.

12. The mobile device of claim 1, wherein the first set of criteria comprises a frequency of travel to a derived location.

13. The mobile device of claim 1, wherein the first set of criteria comprises a time of day for travel to a derived location.

14. The mobile device of claim 1, wherein the first set of criteria comprises a confidence level for travel to a derived location.

15. The mobile device of claim 1, wherein calculating the second set of ranking scores comprises assigning a higher ranking score to an address harvested from a first application than to an address harvested from a second application.

16. The mobile device of claim 1, wherein calculating the second set of ranking scores for a particular address harvested from communications with a contact comprises assigning a ranking score to the particular harvested address based on an identity of the contact.

17. The mobile device of claim 1, wherein calculating the second set of ranking scores comprises assigning a ranking score for a harvested address based on interactions with a mapping application.

18. A non-transitory machine readable medium of a mobile device, the machine readable medium storing a program comprising sets of instructions for:

storing machine-generated addresses related to the mobile device'"'"'s previous locations;

storing addresses harvested from communications processed by the mobile device;

calculating a first set of ranking scores for the machine-generated addresses based on a first set of criteria;

calculating a second set of ranking scores for the addresses harvested from communications processed by the mobile device based on a second different set of criteria;

formulating predicted destinations for the mobile device based on the first and second sets of ranking scores for the stored machine-generated and harvested addresses; and

providing data about the predicted destinations.

19. The machine readable medium of claim 18, wherein the harvested addresses are addresses harvested from locations of calendared events in a calendar application executing on the mobile device.

20. The machine readable medium of claim 18, wherein the harvested addresses are addresses harvested from electronic messages processed by an electronic messaging application executing on the mobile device.

21. The machine readable medium of claim 20, wherein the electronic messaging application is at least one of an email program or a text messaging program.

22. The machine readable medium of claim 18, wherein the harvested addresses are addresses harvested from locations of events for which an electronic ticket application that executes on the mobile device has a ticket.

23. The machine readable medium of claim 18, wherein the program further comprises a set of instructions for receiving addresses from a set of other devices associated with the mobile device through a network and storing the received addresses in a storage.

24. The machine readable medium of claim 23, wherein the mobile device and the set of other devices are part of a group of devices that synchronize their content through a network-based synchronization system, wherein the received addresses comprise addresses harvested by at least one other device that is part of the group.

25. The machine readable medium of claim 24, wherein the received addresses further comprise machine-generated addresses of at least one other device that is part of the group.

26. A method for providing information about potential destinations that a device may travel, the method comprising:

storing past locations of the device;

calculating a first set of ranking scores for a set of machine-generated addresses based on the stored, past locations;

calculating a second set of ranking scores for a set of addresses harvested from a set of applications of the device based on a second different set of criteria; and

identifying a set of predicted destinations from the set of machine-generated addresses and the set of harvested addresses based on the first and second sets of ranking scores.

27. The method of claim 26,

wherein identifying the set of predicted destinations comprises predicting at least one future destination of the device based on the stored, past locations;

and

wherein the method further comprises providing an output based on the set of predicted destinations.