Machine optimization devices, methods, and systems

• US 9,223,900 B2
• Filed: 11/26/2013
• Issued: 12/29/2015
• Est. Priority Date: 12/12/2008
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony, Huang, Bert
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/090,062
• Publication Number:
  US 20140122506A1
• Time in Patent Office: 763 Days
• Field of Search: 707/798, 707/803, 707/999.002, 707/999.102, 709/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

A method, system, computer program product and computer readable media for matching using degree distribution information are disclosed. An embodiment of the method can include performing b-matching on a graph data structure expanded using degree distribution information in order to identify neighbors of a selected input node. The b-matching can be performed using belief propagation. The belief propagation method is adapted to use a compressed message update rule and to be suitable for use with distributed processing systems. An embodiment can also include enhancing a matching result by applying degree distribution information to a first matching result to generate a second matching result. Embodiments for online advertisement/search term matching, product recommendation, dating service and social network matching, auction buyer/seller matching and resource allocation, among other, are disclosed.

Claims

1. A non-transitory computer-readable medium having software instructions stored thereon for matching items with other items comprising:

receiving a first graph data structure having nodes representing items, a first weight matrix having weight values each associated with an edge in the first graph data structure connecting two items, and degree distribution data having degree distribution data for each node in the first graph data structure;

generating a second graph data structure including nodes representing the first graph data structure and a plurality of dummy nodes;

generating a second weight matrix including values representing the first weigh matrix and having additional values associated with the plurality of dummy nodes, the additional values being determined based on the degree distribution data;

determining a constraint value for the nodes of the second graph data structure that represent the nodes of the first graph data structure;

performing a maximum weight b-matching operation on the second graph data structure and the second weight matrix to produce a result matrix wherein b is greater than 1; and

extracting a portion of the result matrix that corresponds to the nodes of the first graph data structure and providing that portion as output.

2. The non-transitory computer-readable medium of claim 1, wherein performing the maximum weight b-matching operation includes performing a max flow operation on the second graph data structure and second weight matrix.

3. The non-transitory computer-readable medium of claim 1, wherein performing the maximum weight b-matching operation includes performing a belief propagation operation among nodes of the second graph data structure.

4. The non-transitory computer-readable medium of claim 3, wherein the belief propagation operation includes:

updating a belief value corresponding to each neighboring node of a selected node in the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on values of the second weight matrix and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected node.

5. The non-transitory computer-readable medium of claim 1, wherein the items include male and female members in a dating application.

6. The non-transitory computer-readable medium of claim 1, wherein the items include movies.

7. The non-transitory computer-readable medium of claim 1, wherein the items include books.

8. The non-transitory computer-readable medium of claim 1, wherein the items include sound records.

9. A computerized method for matching items with other items, the method comprising:

receiving, by one or more processors, a first graph data structure having nodes representing items, a first weight matrix having weight values each associated with an edge in the first graph data structure connecting two items, and degree distribution data having degree distribution data for each node in the first graph data structure;

generating, by the one or more processors, a second graph data structure including nodes representing the first graph data structure and a plurality of dummy nodes;

generating, by the one or more processors, a second weight matrix including values representing the first weigh matrix and having additional values associated with the plurality of dummy nodes, the additional values being determined based on the degree distribution data;

determining, by the one or more processors, a constraint value for the nodes of the second graph data structure that represent the nodes of the first graph data structure;

performing, by the one or more processors, a maximum weight b-matching operation on the second graph data structure and the second weight matrix to produce a result matrix wherein b is greater than 1; and

extracting, by the one or more processors, a portion of the result matrix that corresponds to the nodes of the first graph data structure and providing that portion as output.

10. The computerized method of claim 9, wherein performing the maximum weight b-matching operation includes performing a max flow operation on the second graph data structure and second weight matrix.

11. The computerized method of claim 9, wherein performing the maximum weight b-matching operation includes performing a belief propagation operation among nodes of the second graph data structure.

12. The computerized method of claim 11, wherein the belief propagation operation includes:

updating a belief value corresponding to each neighboring node of a selected node in the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on values of the second weight matrix and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected node.

13. The computerized method of claim 9, wherein the items include male and female members in a dating application.

14. The computerized method of claim 9, wherein the items include movies.

15. A system for matching items with other items comprising:

a storage configured to store software instructions for performing a method of matching items with other items using degree distribution, a first graph data structure having nodes representing items, a first weight matrix having weight values each associated with an edge in the first graph data structure connecting two items, and degree distribution data having degree distribution data for each node in the first graph data structure;

a hardware processor coupled to the storage and configured to execute the software instructions and perform operations including;

generating a second graph data structure including nodes representing the first graph data structure and a plurality of dummy nodes;

generating a second weight matrix including values representing the first weigh matrix and having additional values associated with the plurality of dummy nodes, the additional values being determined based on the degree distribution data;

determining a constraint value for the nodes of the second graph data structure that represent the nodes of the first graph data structure;

performing a maximum weight b-matching operation on the second graph data structure and the second weight matrix to produce a result matrix wherein b is greater than 1;

extracting a portion of the result matrix that corresponds to the nodes of the first graph data structure and providing that portion as output.

16. The system of claim 15, wherein performing the maximum weight b-matching operation includes performing a max flow operation on the second graph data structure and second weight matrix.

17. The system of claim 15, wherein performing the maximum weight b-matching operation includes performing a belief propagation operation among nodes of the second graph data structure.

18. The system of claim 17, wherein the belief propagation operation includes:

updating a belief value corresponding to each neighboring node of a selected node in the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on values of the second weight matrix and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected node.

19. The system of claim 15, wherein the items include male and female members in a dating application.

20. The system of claim 15, wherein the items include movies.