BELIEF PROPAGATION FOR GENERALIZED MATCHING

• US 20110040619A1
• Filed: 01/26/2009
• Published: 02/17/2011
• Est. Priority Date: 01/25/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: Huang, Bert, Jebara, Tony
• Granted Patent: US 9,117,235 B2
• Time in Patent Office: Days
• US Class Current: 705/14.46
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/0613 Third-party assisted
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

Entities may be matched to enhance the efficiency of various commercial activities using various system and method embodiments of the disclosed subject matter. Belief propagation on a graph data structure defining a bipartite or unipartite matching opportunity is used to calculate a best matching. In embodiments, functions are implemented based upon the match, such as executing sales between matched buyers and sellers in an online auction system. In embodiments, messages with scalar values carry information about the relative value of possible matchings, initially provided as weights or values for the possible matchings. Weights may depend on, for example, bids or costs. Messages may be passed, for example over a network between processors respective to the nodes. Belief values reflecting a best matching can be continuously updated for each node responsively to the value information and received messages to rank the matches respective to each node, which progressively improve. This allows short or complete terminations conditions to determine the goodness of the matching. Differing numbers of matches respective to each member of the disjoint sets and distributions of the desirability of different numbers of matches can be integrated in the matchings in respective embodiments.

Claims

1. A method for selling auction items to bidders, comprising:

registering users for an auction service including receiving data identifying the users and storing the profile information relating in user profile data;

receiving auction item data indicating an auction item and receiving bid data corresponding to the auction item data responsively to the profile data;

receiving and storing quota data indicating a maximum number of respective auction items to be purchased by each user;

storing the auction item, bid, and quota data;

retrieving the auction item, bid, and quota data which together form bipartite graph data and storing, so as to provide access to a portion of the bipartite graph data corresponding to a subset of the bids in the bid data that correspond to one or more, but not all, auction items in the auction item data, by multiple connected processors;

executing on each of the processors a matching process that includes receiving messages from, and generating and sending messages to, the multiple connected processors to others of the multiple connected processors, until a termination condition is reached;

wherein at least some of the messages include scalars; and

in each processor, the generating including dividing ratios of functions of respective ones of the bids corresponding to a respective portion of the bipartite graph data by respective scalars received in the receiving.

2. The method of claim 1, wherein the functions are substantial equivalents of exponentials.

3-6. -6. (canceled)

7. A computer readable medium having software instructions stored thereon for matching an advertisement with a key term using belief propagation, the software instructions, when executed by a processor, cause the processor to perform operations comprising:

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

the passing messages including applying data signals to and receiving signals from a multiprocessor data input/output system;

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

selecting a predetermined number of advertiser nodes matching the selected key term node, the matching based on updated belief values of advertiser nodes neighboring the selected key term node; and

outputting the selected advertiser nodes.

8. The computer readable medium of claim 7, wherein the data content of each message is a single scalar value.

9. The computer readable medium of claim 8, wherein the single scalar value corresponds to a potential matching of the selected key term node with a respective one of its neighboring advertiser nodes.

10. The computer readable medium of claim 9, wherein the single scalar value includes a profit matrix value corresponding to a potential matching of the selected key term node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a profit matrix value corresponding to a potential matching between the respective neighbor node and the other node.

11. The computer readable medium of claim 7, wherein the software instructions are adapted for use on distributed processors.

12. A distributed processing system for matching advertisements with search terms using belief propagation, the system comprising:

a plurality of processors each corresponding to a node of a graph data structure having advertisement nodes and search term nodes where each advertisement node is a neighbor to at least one search term node;

a network coupling the plurality of processors and adapted to transfer messages between the processors;

wherein each processor is adapted to load and execute software instructions stored on a computer readable medium, the software instructions, when executed, cause the processor to perform operations including;

updating belief values corresponding to its respective neighbor nodes by passing messages between neighboring nodes until a termination condition is met, a data content of each message being based on profit matrix values and received messages, where a data content of each message is determined according to a message update process;

storing each updated belief value and each received message in an electronic storage associated with the respective processor;

selecting a predetermined number of matching neighbor nodes, the matching being determined based on updated belief values of neighbor nodes; and

outputting the selected matching neighbor nodes.

13. The distributed processing system of claim 12, wherein the data content of each message is a single scalar value.

14. The distributed processing system of claim 13, wherein the single scalar value corresponds to a potential matching of the selected search term node with a respective one of its neighboring advertiser nodes.

15. The distributed processing system of claim 14, wherein the single scalar value includes a profit matrix value corresponding to a potential matching of the selected search term node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a profit matrix value corresponding to a potential matching between the respective neighbor node and the other node.

16. The distributed processing system of claim 12, wherein each profit matrix value represents a profit amount associated with an edge between neighboring nodes.

17. The distributed processing system of claim 12, wherein the updating is performed iteratively until the termination condition is met.

18. The distributed processing system of claim 12, wherein the termination condition is a predetermined number of iterations of the updating.

19. The distributed processing system of claim 12, wherein the termination condition is defined as receiving no changed message values within a predetermined period of time.

20. The distributed processing system of claim 12, wherein the termination condition is a number of messages sent from each node.

21. The distributed processing system of claim 12, wherein the termination condition is an elapsing of a predetermined period of time.

22. The distributed processing system of claim 12, wherein the termination condition is defined as the earliest occurrence of one of receiving no changed message values within a first predetermined period of time and an elapsing of a second predetermined period of time

23. A computerized method for matching advertisements with search terms using belief propagation, the method comprising:

providing a bipartite graph data structure having a plurality of advertiser nodes and a plurality of search term nodes, where each advertiser node is connected to a corresponding search term node by an edge;

providing a profit matrix having a profit for each edge of the bipartite graph data structure;

updating, with a processor adapted to perform belief propagation generalized matching, a belief value corresponding to each advertiser node connected to a selected search term node by passing messages between adjacent nodes until a termination condition is met, each message being based on profit matrix values and received messages, where a data content of each message is determined according to a compressed message update process;

storing each updated belief value and each received message in an electronic storage associated with the corresponding advertiser node;

selecting a predetermined number of advertiser nodes matching each search term node of a group of search term nodes of interest, the matching being determined based on updated belief values of advertiser nodes adjacent to each search term node of interest; and

outputting the selected advertiser nodes matching each search term node of interest.

24. The method of claim 23, further comprising displaying advertisements associated with each of the selected advertiser nodes on a search results page corresponding to the search term node associated with the selected advertiser nodes.

25. The method of claim 23, further comprising storing at each advertiser node and at each search term node a portion of the profit matrix, where each portion is selected based on adjacent nodes of each respective advertiser node and each respective search term node.

26. The method of claim 23, wherein the compressed message update process generates a message that includes

27. The method of claim 23, wherein the updating and storing are performed using parallel processing.

28. The method of claim 23, wherein each profit represents a profit on placement of an advertisement by an advertiser associated with the advertisement.

29. The method of claim 23, wherein the updating is performed iteratively until the termination condition is met.

30. The method of claim 23, wherein the termination condition is a predetermined number of iterations of the updating.

31. The method of claim 23, wherein the termination condition is defined as a steady state of updated belief values during a predetermined period of time.

32-69. -69. (canceled)