Generating Probabilistic Transition Data

• US 20150302112A1
• Filed: 04/22/2014
• Published: 10/22/2015
• Est. Priority Date: 04/22/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alonso, Omar, Bannur, Sushma
• Granted Patent: US 11,074,293 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Systems and methods are presented for generating a transition graph from check-in data for determining probabilistic transitions of a user from an origin (location) to a destination. Check-in data for a plurality of users is obtained. The check-in data is organized and analyzed to determine a set of transition tuples for each of the plurality of users. These transition tuples are aggregated and used to generate a transition graph comprising a plurality of nodes and edges. Each node corresponds to a location and each edge indicates a transition from an origin node to a destination node and is associated with a likelihood of a user transitioning from the origin node to the destination node.

Claims

1. A computer-implemented method for generating a transition graph for determining probabilistic transitions, the method comprising each of the following as executed by a processor on a computing device:

obtaining check-in data of a plurality users, wherein each item of check-in data indicates the presence of a corresponding user at a location;

sorting the check-in data according the corresponding users;

determining a set of transition tuples for each of the plurality of users according to the sorted check-in data;

aggregating the transition tuples according to the origin of the transition tuples; and

generating a transition graph according to the aggregated transition tuples, wherein the transition graph comprises a plurality of nodes and edges, each node corresponding to a location and each edge indicating a transition from an origin node to a destination node and associated with a likelihood of a user transitioning from the origin node to the destination node.

2. The computer-implemented method of claim 1, wherein each item of check-in data includes a user identifier of the corresponding user.

3. The computer-implemented method of claim 2, wherein the user identifier differentiates the corresponding user from all other users without disclosing the identity of the corresponding user.

4. The computer-implemented method of claim 3, wherein each item of check-in data further indicates a date and time of the check-in of the corresponding user at the location.

5. The computer-implemented method of claim 1, wherein each transition tuple comprises information indicating an origin and a destination, each transition tuple indicating a transition from the origin to the destination by the corresponding user.

6. The computer-implemented method of claim 5, wherein determining a set of transition tuples for each of the plurality of users comprises, for each of the plurality of users:

chronologically ordering the check-in data corresponding to a user;

iteratively pairing a first check-in point with an immediately subsequent check-in point, as chronologically ordered, as a potential transition tuple, wherein the first check-in point is the origin of the potential transition tuple and the immediately subsequent check-in point is the destination of the potential transition tuple;

for each potential transition tuple, determining whether the potential transition tuple meets predetermined requirements; and

retaining those potential transition tuples that meet the predetermined requirements in the set of transition tuples for the corresponding user.

7. The computer-implemented method of claim 6, wherein determining whether the potential transition tuple meets predetermined requirements comprises determining whether the time between the check-in at the origin and the check-in at the destination is within a predetermined amount of time.

8. The computer-implemented method of claim 7, wherein determining whether the potential transition tuple meets predetermined requirements further comprises determining whether the distance between the origin and the destination is within a predetermined distance.

9. The computer-implemented method of claim 7, wherein determining whether the potential transition tuple meets predetermined requirements further comprises determining whether the origin and the destination are within the same geographic region.

10. A computer-readable medium bearing computer-executable instructions which, when executed on a computing system comprising at least a processor retrieved from the medium, carry out a method for generating a transition graph for determining probabilistic transitions, the method comprising:

obtaining check-in data of a plurality users, wherein each item of check-in data indicates the presence of a corresponding user at a location;

determining a set of transition tuples for each of the plurality of users according to the sorted check-in data;

aggregating the transition tuples according to the origin of the transition tuples;

generating a transition graph according to the aggregated transition tuples, wherein the transition graph comprises a plurality of nodes and edges, each node corresponding to a location and each edge indicating a transition from an origin node to a destination node and associated with a likelihood of a user transitioning from the origin node to the destination node;

receiving a request for a probabilistic transition for a user from an origin;

determining a probabilistic transition for the user from the origin to a destination and returning the transition to the user in response to the request.

11. The computer-readable medium of claim 10, wherein each transition tuple comprises information indicating an origin and a destination, each transition tuple indicating a transition from the origin to the destination by the corresponding user.

12. The computer-readable medium of claim 11, wherein determining a set of transition tuples for each of the plurality of users comprises, for each of the plurality of users:

chronologically ordering the check-in data corresponding to a user;

iteratively pairing a first check-in point with an immediately subsequent check-in point, as chronologically ordered, as a potential transition tuple, wherein the first check-in point is the origin of the potential transition tuple and the immediately subsequent check-in point is the destination of the potential transition tuple;

for each potential transition tuple, determining whether the potential transition tuple meets predetermined requirements; and

retaining those potential transition tuples that meet the predetermined requirements in the set of transition tuples for the corresponding user.

13. The computer-readable medium of claim 12, wherein determining whether the potential transition tuple meets predetermined requirements comprises determining whether the time between the check-in at the origin and the check-in at the destination is within a predetermined amount of time.

14. The computer-readable medium of claim 10, wherein each transition tuple comprises information indicating an origin and a destination, each transition tuple indicating a transition from the origin to the destination by the corresponding user.

15. The computer-readable medium of claim 10, wherein each item of check-in data indicates a date and time of the check-in of the corresponding user at the location, and further includes a user identifier of the corresponding user.

16. The computer-readable medium of claim 10, wherein determining the probabilistic transition for the user from the origin to a destination comprises:

applying a filtering to the transition graph based on the current context of the user; and

identifying a destination having the highest likelihood of transition from the origin as the probabilistic transition.

17. A computer system for generating a transition graph for determining probabilistic transitions, the computer system comprising a processor and a memory, wherein the processor executes instructions stored in the memory as part of or in conjunction with additional components, the additional components comprising:

a data access component configured to access check-in data for a plurality of users; and

a transition graph generator configure to;

determine a set of transition tuples for each of the plurality of users;

aggregating the transition tuples according to the origin of each of the transition tuples; and

generate a transition graph according to the aggregated transition tuples, wherein the transition graph comprises a plurality of nodes and edges, each node corresponding to a location and each edge indicating a transition from an origin node to a destination node and associated with a likelihood of a user transitioning from the origin node to the destination node.

18. The computer system of claim 17, wherein the transition graph generator is further configured to generate the transition graph according to the aggregated transition tuples by:

chronologically ordering the check-in data corresponding to a user;

iteratively pairing a first check-in point with an immediately subsequent check-in point, as chronologically ordered, as a potential transition tuple, wherein the first check-in point is the origin of the potential transition tuple and the immediately subsequent check-in point is the destination of the potential transition tuple;

for each potential transition tuple, determining whether the potential transition tuple meets predetermined requirements; and

retaining those potential transition tuples that meet the predetermined requirements in the set of transition tuples for the corresponding user.

19. The computer system of claim 18 further comprising an itinerary generator configured to determine a probabilistic transition for a user from an origin to a destination, and return the transition to the user in response to a request on behalf of the user.

20. The computer system of claim 19, wherein each item of check-in data indicates the presence of a corresponding user at a location and includes a user identifier of the corresponding user, wherein the user identifier differentiates the corresponding user from all other users without disclosing the identity of the corresponding user.