Advancements in data mining capabilities are transforming the competitive landscape across industries, but also creating additional complex data-centric matching and inference problems. Consequently, optimized matching and inference algorithms are required for sustained user engagement, as well as effective use of large and complex data sets. As data sets become larger and more complex, it will become increasingly important for solutions to data-matching problems to scale in terms of speed and memory usage. Optimal solutions to generalized matching or auction problems can be found using linear programming, but this approach is too slow for practical applications. Many companies use a fast variant of this approach that is capable of solving large scale problems with millions of users quickly, but this approach only guarantees a solution that is 65% as good (or as profitable) as the optimal solution. This technology describes an algorithm that reliably identifies solutions to large scale matching problems that are 100% optimal (most profitable), with outstanding performance in both computational efficiency and memory requirements.
This technology is an enhancement of the belief propagation (BP) algorithm, which is a method used to calculate probabilistic inference on graphical models and to solve inference and matching problems. Unlike other fast bid matching solvers where the trade-off between computational speed / memory usage and the quality of solutions limit the performance, this technology can obtain the most profitable or 100% optimal solutions to generalized matching problems without sacrificing computational speed and memory usage as it is based on BP algorithm. With this technology, optimal matching solutions for dense graphs with hundreds of millions of edges can be solved in a matter of hours on a standard PC.
Patent Pending (US 20140129320)
Tech Ventures Reference: IR M11-081, M08-054