Belief propagation for generalized matching

US9117235B2 · kind B2 · utility

Assignee

• The Trustees of Columbia University in the City of New York · US

Inventors

• Tony Jebara · New York, US
• Bert Huang · New York, US

Key dates

• Filing date: Jan 26, 2009
• Grant date: Aug 25, 2015
• Expiry date: Oct 3, 2031

Classification

• Technology area (CPC G): Physics
• CPC primary: G06Q30/08
• WIPO field: IT methods for management
• WIPO sector: Electrical engineering

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 desirabili…