Recent Patents in Signal Processing (January 2013) - Graph-based Algorithms

Happy New Year! For our January 2013 issue, we focus on recent patents in Graph-based Algorithms. The selection below contains patents issued in the recent past in various applications which are either based on the graphs or use graphs in novel ways. These include using graphs to classify telephone calls, constructing programming language elements, clustering similar images, improving error correcting code graphs, detecting object movement in videos, etc.

US 8,326,847, "Graph search system and method for querying loosely integrated data", by A. Balmin, H. Hwang, M. Pirahesh and B. Reinwald, filed 22 March 2008, issued 4 December 2012, assigned to International Business Machines Corporation (Armonk, NY).

US 8,325,900, "Telephone call classification utilizing a social network graph", by J. -M. Trivi and M. Nelissen, filed 26 September 2011, issued 4 December 2012, assigned to Google Inc. (Mountain View, CA).

US 8,321,424, "Bipartite graph reinforcement modeling to annotate web images", by M. Li, W. -Y. Ma, Z. Li, and X. Rui filed 30 August 2007, issued 27 November 2012, assigned to Microsoft Corporation (Redmond, WA).

US 8,296,744, "Tree-based directed graph programming structures for a declarative programming language", by D. Langworthy, J. Hamby, B. Lovering and D. Box, filed 3 October 2008, issued 23 October 2012, assigned to Microsoft Corporation (Redmond, WA).

US 8,243,988, "Clustering images using an image region graph", by U. Buddemeier, filed 31 July 2008, issued 14 August 2012, assigned to Google Inc. (Mountain View, CA).

US 8,310,484, "Efficient processing of operator graphs representing three-dimensional character animation", by J. Couture-Gagnon, P. Zion, I. Stewart, R. Beirouti, D. LaFlamme and M. Beaudry, filed 26 July 2007, issued 13 November 2012, assigned to AUTODESK, Inc. (San Rafael, CA).

US 8,200,609, "Construction of decision logic with graphs", by S. Crawford, M. Steele, P. Kumar, S. Tolmanov, M. Thorsen and C. Erikson, filed 29 August 2008, issued 12 June 2012, assigned to Fair Isaac Corporation (Minneapolis, MN).

US 8,149,278, "System and method for modeling movement of objects using probabilistic graphs obtained from surveillance data", by C. Wren, Y. Ivanov, A. Sorokin and I. Banga, filed 5 February 2007, issued 3 April 2012, assigned to Mitsubishi Electric Research Laboratories, Inc. (Cambridge, MA).

US 8,259,868, "Conditionally cycle-free generalized tanner graphs based decoding", by T. Halford and K. Chugg, filed 25 September 2008, issued 4 September 2012, assigned to University of Southern California (Los Angeles, CA).

If you have an interesting patent to share when we next feature patents related to graphs and graph theory, or if you are especially interested in a signal processing research field that you would want to be highlighted in this section, please send email to Shantanu Rane (rane AT merl DOT com).