Belief propagation for generalized matching

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.

1 - 69 . (canceled) 
     
     
         70 . A method for matching using belief propagation, comprising:
 receiving and storing first node data identifying a first set of nodes;   receiving and storing second node data identifying a second set of nodes;   receiving and storing quota data identifying a maximum number of nodes within the second set of nodes to be matched with for each node within the first set of nodes;   retrieving and storing the first node data, the second node data, and the quota data which together form bipartite graph data, so as to provide access to a portion of the bipartite graph data corresponding to a subset of the nodes in the first node data that correspond to one or more, but not all, second nodes in the second node 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.   
     
     
         71 . The method of  claim 70 , the matching process further comprising:
 calculating one or more intermediate values for each neighboring second node of a selected first node that is based on received messages;   sorting the one or more intermediate values;   selecting an intermediate value from the one or more intermediate values based on the quota data for the selected first node; and   calculating a new message based on the received messages, and the selected intermediate value.   
     
     
         72 . The method of  claim 70 ,
 wherein at least some of the messages include scalars; and   in each processor, the generating including dividing ratios of functions of a respective first node corresponding to a respective portion of the bipartite graph data by respective scalars received.   
     
     
         73 . The method of  claim 72 , wherein the data content of each message is a single scalar value. 
     
     
         74 . The method of  claim 73 , wherein the single scalar value corresponds to a potential matching of the selected first node with a respective one of its neighboring second nodes. 
     
     
         75 . The method of  claim 70 , wherein the functions are substantial equivalents of exponentials. 
     
     
         76 . The method of  claim 70 ,
 wherein the first set of nodes comprises auction buyers and their respective goods/services to be matched, and   wherein the second set of nodes comprises auction sellers and their respective goods/services to be matched.   
     
     
         77 . The method of  claim 70 , wherein the termination condition is a predetermined number of iterations of the generating and sending of the messages. 
     
     
         78 . The method of  claim 70 , wherein the termination condition is defined as receiving no changed message values within a predetermined period of time. 
     
     
         79 . The method of  claim 70 , wherein the termination condition is a number of messages sent from each node. 
     
     
         80 . The method of  claim 70 , wherein the termination condition is an elapsing of a predetermined period of time. 
     
     
         81 . A computer readable medium having software instructions stored thereon for matching using belief propagation, the software instructions, when executed by a processor, cause the processor to perform operations comprising:
 receiving and storing first node data identifying a first set of nodes;   receiving and storing second node data identifying a second set of nodes;   receiving and storing quota data identifying a maximum number of nodes within the second set of nodes to be matched with for each node within the first set of nodes;   retrieving and storing the first node data, the second node data, and the quota data which together form bipartite graph data, so as to provide access to a portion of the bipartite graph data corresponding to a subset of the nodes in the first node data that correspond to one or more, but not all, second nodes in the second node 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.   
     
     
         82 . The computer readable medium of  claim 81 , the matching process further comprising:
 calculating one or more intermediate values for each neighboring second node of a selected first node that is based on received messages;   sorting the one or more intermediate values;   selecting an intermediate value from the one or more intermediate values based on the quota data for the selected first node; and   calculating a new message based on the received messages, and the selected intermediate value.   
     
     
         83 . The computer readable medium of  claim 81 ,
 wherein the first set of nodes comprises auction buyers and their respective goods/services to be matched, and   wherein the second set of nodes comprises auction sellers and their respective goods/services to be matched.   
     
     
         84 . The computer readable medium of  claim 81 , wherein the termination condition is a predetermined number of iterations of the generating and sending of the messages. 
     
     
         85 . The computer readable medium of  claim 81 , wherein the termination condition is defined as receiving no changed message values within a predetermined period of time. 
     
     
         86 . A distributed processing system for matching using belief propagation, the system comprising:
 a plurality of processors each corresponding to a node of a graph data structure having a first set of nodes and a second set of nodes where each node from the first set of nodes is a neighbor to at least one node from the second set of nodes;   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:   receiving and storing first node data identifying the first set of nodes;   receiving and storing second node data identifying the second set of nodes;   receiving and storing quota data identifying a maximum number of nodes within the second set of nodes to be matched with for each node within the first set of nodes;   retrieving and storing the first node data, the second node data, and the quota data which together form bipartite graph data, so as to provide access to a portion of the bipartite graph data corresponding to a subset of the nodes in the first node data that correspond to one or more, but not all, second nodes in the second node data;   executing, on each of the processors, a matching process that includes receiving messages from, and generating and sending messages to, the plurality of processors to others of the plurality of processors, until a termination condition is reached.   
     
     
         87 . The system of  claim 86 , the matching process further comprising:
 calculating one or more intermediate values for each neighboring second node of a selected first node that is based on received messages;   sorting the one or more intermediate values;   selecting an intermediate value from the one or more intermediate values based on the quota data for the selected first node; and   calculating a new message based on the received messages, and the selected intermediate value.   
     
     
         88 . The system of  claim 86 ,
 wherein the first set of nodes comprises auction buyers and their respective goods/services to be matched, and   wherein the second set of nodes comprises auction sellers and their respective goods/services to be matched.   
     
     
         89 . The system of  claim 86 , wherein the termination condition is a predetermined number of iterations of the generating and sending of the messages.