Combined directed graphs

• US 9,977,797 B2
• Filed: 09/28/2015
• Issued: 05/22/2018
• Est. Priority Date: 09/28/2015
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Jagota, Arun Kumar, Fuchs, Matthew
• Primary Examiner(s): Le, Debbie
• Application Number:
  US14/867,154
• Publication Number:
  US 20170091229A1
• Time in Patent Office: 967 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A combined directed graph is created having a corresponding node for each node in a first directed graph lacking a corresponding node in a second directed graph, each node in the second graph lacking a corresponding node in the first graph, and each node in the first graph having a corresponding node in the second graph. A corresponding directed arc is created in the combined directed graph for each arc in the first graph lacking a corresponding arc in the second directed graph, each arc in the second graph lacking a corresponding arc in the first graph, and each arc in the first graph having a corresponding arc in the second graph. A recommendation is output for a user to interact with a recommended object based on an object interaction and a conditional probability, in the combined graph, which corresponds to the recommended object and the object interaction.

Claims

1. A system for combining directed graphs, the system comprising:

one or more processors; and

a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to;

identify, by a database system, a first directed graph having nodes connected by directed arcs and a second directed graph having nodes connected by directed arcs, a directed arc from a first node in a directed graph to a second node in the directed graph represents a conditional probability that previous users who interacted with a first object corresponding to the first node in the directed graph also interacted with a second object corresponding to the second node in the directed graph;

create, by the database system, a combined directed graph having a corresponding node for;

i) each node in the first directed graph lacking a corresponding node in the second directed graph, ii) each node in the second directed graph lacking a corresponding node in the first directed graph, and iii) each node in the first directed graph having a corresponding node in the second directed graph;

create, by the database system, in the combined directed graph, a corresponding directed arc for;

i) each directed arc in the first directed graph lacking a corresponding directed arc in the second directed graph, ii) each directed arc in the second directed graph lacking a corresponding directed arc in the first directed graph, and iii) each directed arc in the first directed graph having a corresponding directed arc in the second directed graph; and

output, by the database system, a recommendation for a user to interact with a recommended object based on an object interaction and a conditional probability in the combined directed graph, the conditional probability corresponding to the recommended object and the object interaction.

2. The system of claim 1, wherein the first directed graph comprises proprietary data for a first tenant in a multi-tenant database and the second directed graph comprises proprietary data for a second tenant in the multi-tenant database.

3. The system of claim 1, wherein each node in the directed graph is associated with a corresponding node count identifying a number of user interaction sets that include a corresponding object.

4. The system of claim 1, wherein each node in the combined directed graph which corresponds to a node in the first directed graph which lacks a corresponding node in the second directed graph, is associated with a corresponding node count identifying a number of user interaction sets which include a corresponding object in the first directed graph.

5. The system of claim 1, wherein each node in the combined directed graph that corresponds to a node in the second directed graph which lacks a corresponding node in the first directed graph, is associated with a corresponding node count identifying a number of user interaction sets which include a corresponding object in the second directed graph.

6. The system of claim 1, wherein each node in the combined directed graph which corresponds to a node in the first directed graph which has a corresponding node in the second directed graph, is associated with a corresponding total node count identifying a number of user interaction sets which include a corresponding object in the first directed graph aggregated with a number of user interaction sets which include a corresponding object in the second directed graph.

7. The system of claim 1, wherein a node count and a conditional probability are weighted by at least one of a directed graph weight and a decreasing weight for objects in a user interaction set.

8. A computer program product comprising computer-readable program code to be executed by one or more processors when retrieved from a non-transitory computer-readable medium, the program code including instructions to:

identify, by a database system, a first directed graph having nodes connected by directed arcs and a second directed graph having nodes connected by directed arcs a directed arc from a first node in a directed graph to a second node in the directed graph represents a conditional probability that previous users who interacted with a first object corresponding to the first node in the directed graph also interacted with a second object corresponding to the second node in the directed graph;

create, by the database system, a combined directed graph having a corresponding node for;

i) each node in the first directed graph lacking a corresponding node in the second directed graph, ii) each node in the second directed graph lacking a corresponding node in the first directed graph, and iii) each node in the first directed graph having a corresponding node in the second directed graph;

create, by the database system, in the combined directed graph, a corresponding directed arc for;

i) each directed arc in the first directed graph lacking a corresponding directed arc in the second directed graph, ii) each directed arc in the second directed graph lacking a corresponding directed arc in the first directed graph, and iii) each directed arc in the first directed graph having a corresponding directed arc in the second directed graph; and

output, by the database system, a recommendation for a user to interact with a recommended object based on an object interaction and a conditional probability in the combined directed graph, the conditional probability corresponding to the recommended object and the object interaction.

9. The computer program product of claim 8, wherein the first directed graph comprises proprietary data for a first tenant in a multi-tenant database and the second directed graph comprises proprietary data for a second tenant in the multi-tenant database.

10. The computer program product of claim 8, wherein each node in the directed graph is associated with a corresponding node count identifying a number of user interaction sets that include a corresponding object.

11. The computer program product of claim 8, wherein each directed arc in the combined directed graph which corresponds to a directed arc in the first directed graph which lacks a corresponding directed arc in the second directed graph, represents a conditional probability that previous users who interacted with an object corresponding to a beginning node in the first directed graph where the directed arc begins also interacted with an object corresponding to an ending node in the first directed graph where the directed arc ends.

12. The computer program product of claim 8, wherein each directed arc in the combined directed graph which corresponds to a directed arc in the second directed graph which lacks a corresponding directed arc in the first directed graph, represents a conditional probability that previous users who interacted with an object corresponding to a beginning node in the second directed graph where the directed arc begins also interacted with an object corresponding to an ending node in the second directed graph where the directed arc ends.

13. The computer program product of claim 8, wherein each directed arc in the combined directed graph which corresponds to a directed arc in the first directed graph which has a corresponding directed arc in the second directed graph, represents a combined conditional probability that previous users who interacted with an object corresponding to a beginning node in the combined directed graph where the corresponding directed arc begins also interacted with an object corresponding to an ending node in the combined directed graph where the corresponding directed arc ends.

14. A method for combining directed graphs, the method comprising:

identifying, by a database system, a first directed graph having nodes connected by directed arcs and a second directed graph having nodes connected by directed arcs, a directed arc from a first node in a directed graph to a second node in the directed graph represents a conditional probability that previous users who interacted with a first object corresponding to the first node in the directed graph also interacted with a second object corresponding to the second node in the directed graph;

creating, by the database system, a combined directed graph having a corresponding node for;

i) each node in the first directed graph lacking a corresponding node in the second directed graph, ii) each node in the second directed graph lacking a corresponding node in the first directed graph, and iii) each node in the first directed graph having a corresponding node in the second directed graph;

creating, by the database system, in the combined directed graph, a corresponding directed arc for;

i) each directed arc in the first directed graph lacking a corresponding directed arc in the second directed graph, ii) each directed arc in the second directed graph lacking a corresponding directed arc in the first directed graph, and iii) each directed arc in the first directed graph having a corresponding directed arc in the second directed graph; and

outputting, by the database system, a recommendation for a user to interact with a recommended object based on an object interaction and a conditional probability in the combined directed graph, the conditional probability corresponding to the recommended object and the object interaction.

15. The method of claim 14, wherein the first directed graph comprises proprietary data for a first tenant in a multi-tenant database and the second directed graph comprises proprietary data for a second tenant in the multi-tenant database.

16. The method of claim 14, wherein each node in the directed graph is associated with a corresponding node count identifying a number of user interaction sets that include a corresponding object.

17. The method of claim 14, wherein each directed arc in the combined directed graph which corresponds to a directed arc in the first directed graph which has a corresponding directed arc in the second directed graph, represents a combined conditional probability that previous users who interacted with an object corresponding to a beginning node in the combined directed graph where the corresponding directed arc begins also interacted with an object corresponding to an ending node in the combined directed graph where the corresponding directed arc ends, wherein the combined conditional probability which represents the corresponding directed arc comprises an adjusted conditional probability divided by a combined node count, wherein the adjusted conditional probability comprises a first adjusted conditional probability aggregated with a second adjusted conditional probability.

18. The method of claim 17, wherein the first adjusted conditional probability comprises a conditional probability that previous users who interacted with an object corresponding to a beginning node in the first directed graph where a corresponding directed arc begins also interacted with an object corresponding to an ending node in the first directed graph where the corresponding directed arc ends multiplied by a corresponding node count identifying a number of user interaction sets which include the object corresponding to the beginning node in the first directed graph where the corresponding directed arc begins.

19. The method of claim 17, wherein the second adjusted conditional probability comprises a conditional probability that previous users who interacted with an object corresponding to a beginning node in the second directed graph where a corresponding directed arc begins also interacted with an object corresponding to an ending node in the second directed graph where the corresponding directed arc ends multiplied by a corresponding node count identifying a number of user interaction sets which include the object corresponding to the beginning node in the second directed graph where the corresponding directed arc begins.

20. The method of claim 17, wherein the combined node count comprises a number of user interaction sets which include the object corresponding to the beginning node in the first directed graph aggregated with a number of user interaction sets which include the object corresponding to the beginning node in the second directed graph.