Systems and methods for route prediction

• US 9,921,072 B2
• Filed: 11/08/2013
• Issued: 03/20/2018
• Est. Priority Date: 11/09/2012
• Status: Active Grant

• Current Assignee: Visa International Service Association (Visa, Inc.)
• Original Assignee: Visa International Service Association (Visa, Inc.)
• Inventors: Spears, Joseph, Carlson, Mark, Stan, Patrick
• Primary Examiner(s): LANG, MICHAEL DEAN
• Application Number:
  US14/075,518
• Publication Number:
  US 20140136104A1
• Time in Patent Office: 1,593 Days
• Field of Search: 701521
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

Predicting the future location of a user based on predicting the route that the user might take is disclosed. The routes used by the user in the past are indexed to generate a dictionary of routes which can be further augmented with contextual data. The prior routes are encoded within the dictionary such that each term representing a respective one of the prior routes comprises a collection of unique identifiers wherein each of the unique identifiers represents a segment of the respective one of the prior routes. Techniques of text prediction, term frequency for dictionary scores and other language processing techniques are used to predict the further route of the user.

Claims

1. A computer-implemented method, comprising:

storing, in a computing apparatus, a route dictionary containing a plurality of route words identifying a plurality of routes previously traversed by a user, wherein each respective route word in the route dictionary includes an ordered sequence of symbols, each of the symbols identifying a predetermined vertex in the plurality of routes previously traversed by a user;

storing, in the computing apparatus, term frequency data of the route words of the user based on frequencies with which the user has traversed respective routes represented by the route words;

communicating, by the computing apparatus with a user device, to identify one or more vertices of a route currently being traversed by the user based on GPS data from the user device;

generating, by the computing apparatus, a partial route word from a starting sequence of symbols representing the one or more vertices respectively;

while the user is currently traversing the route, predicting, using a text prediction technique for predicting from a given partial word a complete word in a dictionary according to term frequency, a particular route word in the route dictionary containing the partial route word;

identifying, by the computing apparatus, a remaining sequence of symbols that follows the starting sequence of symbols in the particular route word;

predicting, by the computing apparatus, a remaining portion of the route that is currently being traversed by the user as being identified by a set of vertices corresponding to the remaining sequence of symbols in the particular route word;

identifying, by the computing apparatus, a message based on the remaining portion of the route; and

transmitting, by the computing apparatus to the user device, the message before the user completes the predicted, remaining portion of the route.

2. The method of claim 1, further comprising:

monitoring, by the computing apparatus, routes traversed by the user;

updating, by the computing apparatus, term frequencies of route words in the dictionary corresponding to the routes being monitored.

3. The method of claim 1, further comprising:

accessing, by the computing apparatus, context data associated with the user;

wherein the remaining portion of the route is predicted based further on the context data.

4. The method of claim 1, further comprising:

monitoring, by the computing apparatus, routes traversed by the user;

updating, by the computing apparatus, the route dictionary to include route words corresponding to the routes being monitored and having been traversed by the user.

5. A computing apparatus having at least one microprocessor and memory storing instructions configured to instruct the at least one microprocessor to perform operations, the computing apparatus comprising:

a location information receiver configured to receive, from a user device,

route data identifying routes previously traversed by a user device of a user associated with a consumer account, and

one or more vertices of a portion of a route currently being traversed by the user based on GPS data;

a route dictionary builder configured to organize the route data into a route dictionary, wherein;

the route dictionary includes a plurality of route words identifying a plurality of routes previously traversed by the user,

each respective route word in the route dictionary includes an ordered sequence of symbols,

each of symbols in the plurality of route words identifying a predetermined vertex in the plurality of routes previously traversed by a user; and

the computer apparatus stores term frequency data of the route words of the user based on frequencies with which the user has traversed respective routes represented by the route words;

a route predictor configured to;

generate a partial route word from a starting sequence of symbols representing the one or more vertices respectively of a portion of the route currently being traversed by the user;

predict, using a text prediction technique for predicting from a given partial word a complete word in a dictionary according to term frequency, a particular route word in the route dictionary containing the partial route word,

identify a remaining sequence of symbols that follows the starting sequence of symbols in the particular route word, and

predict a remaining portion of the route that is currently being traversed by the user as being identified by a set of vertices corresponding to the remaining sequence of symbols in the particular route word; and

a route information transmitter configured to;

identify data based on the remaining portion of the route predicted to be identified by the set of vertices corresponding to the remaining sequence of symbols in the particular route word, and

transmit, to the user device, the data before the user completes the predicted, remaining portion of the route.

6. The computing apparatus of claim 5, wherein the route dictionary further comprises context information associated with each of the prior routes traversed by the user.

7. The computing apparatus of claim 5, wherein the route dictionary further comprises a count associated with each of the prior routes, the count representing frequency of traversal of the user along each of the routes.

8. The computing apparatus of claim 5, wherein the computing apparatus further comprises instructions for:

updating a count of at least one of the routes when the user traverses along the at least one route;

adding a new route to the route dictionary when it is determined that a route traversed by a user is not encoded in the route dictionary; and

initializing a count of the new route to one upon adding the new route to the route dictionary.

9. A non-transitory computer storage medium storing instructions configured to instruct a computing apparatus to perform a method, the method comprising:

storing, in a computing apparatus, a route dictionary containing a plurality of route words identifying a plurality of routes previously traversed by a user, wherein each respective route word in the route dictionary includes an ordered sequence of symbols, each of the symbols identifying a predetermined vertex in the plurality of routes previously traversed by a user;

storing, in the computing apparatus, term frequency data of the route words of the user based on frequencies with which the user has traversed respective routes represented by the route words;

communicating, by the computing apparatus with a user device, to identify one or more vertices of a route currently being traversed by the user based on GPS data from the user device;

generating, by the computing apparatus, a partial route word from a starting sequence of symbols representing the one or more vertices respectively;

while the user is currently traversing the route, predicting, using a text prediction technique for predicting from a given partial word a complete word in a dictionary according to term frequency, a particular route word in the route dictionary containing the partial route word;

identifying, by the computing apparatus, a remaining sequence of symbols that follows the starting sequence of symbols in the particular route word;

predict, by the computing apparatus, a remaining portion of the route that is currently being traversed by the user as being identified by a set of vertices corresponding to the remaining sequence of symbols in the particular route word;

identifying, by the computing apparatus, a message based on the remaining portion of the route; and

transmitting, by the computing apparatus to the user device, the message before the user completes the predicted, remaining portion of the route.