N1005 IBM Research: Ron Fagin

<br /><div class="MsoNormal"><span style="font-family: Verdana; font-size: 13.0pt;">The American Academy of Arts and Sciences elected <a href="https://www.amacad.org/multimedia/pdfs/classlist2014.pdf">204 new members</a> across a number of categories, including eight computer scientists. One of these eight was IBM Fellow Ron Fagin, for his breakthrough work. Election to the American Academy is considered one of the nation’s highest honors since its founding during the American Revolution, when its first class included George Washington and Benjamin Franklin.</span></div><div class="MsoNormal"><br /></div><div class="MsoNormal"><span style="font-family: Verdana; font-size: 13.0pt;">“Former Secretary of Labor Robert Reich, a college friend of mine, was also elected this year for his work in public affairs. So, it was a thrill to get an email from Reich saying ‘Somehow I always knew we'd end up at the same induction ceremony, fifty years after we met’,” Ron said.</span></div><div class="MsoNormal"><br /></div><div class="MsoNormal"><span style="font-family: Verdana; font-size: 13.0pt;">The American Academy recognized Ron for the following accomplishments:</span><span style="font-family: Verdana; font-size: 13.0pt;"> </span></div><ul><li><span style="font-family: Verdana; font-size: 13.0pt;">Established the field of finite-model theory, connecting mathematical logic, complexity theory, and database theory, and elaborated Fagin's theorem and Fagin's zero-one law.</span><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;"> </span></li><li><span style="font-family: Verdana; font-size: 13.0pt;">Founding figure of relational database theory underlying the success of relational databases.</span></li><li><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;">Introduced fundamental concepts for database design, especially: fourth normal form, multivalued dependencies, and acyclic schemas, and invented an extendible-hashing algorithm used to find data quickly.</span></li><li><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;">Invented algorithms for querying and aggregating imprecise data, key capabilities for information retrieval systems.</span></li><li><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;">Created the foundations for data integration and transformation with his work on data exchange and tuple-generating dependencies, considered the most significant development in database theory over the last decade.</span></li><li><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;">Invented a highly scalable, widely used method for differential backup of files, and an algorithm for assigning encryption keys, techniques crucial to IBM products.</span></li><li><span style="font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="font-family: Verdana; font-size: 13.0pt;">Developed a logical foundation to reasoning about group knowledge and coauthored Reasoning about Knowledge (2d ed. 2003), now considered a classic on knowledge in multi-agent systems.</span></li></ul> <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMAsHCGi6OQLrfcI3BjX58nZYPjDeNP7HgZPiFlHp6b8iJV_qoMEO-QNXJl8HHKpd4iSOBbTWhUHkWCDLsl5RnOCKQj3yICseMz0qgvNC3pRxTD2Ssv_d-etOH86OYyJ71GMhVcGMdjGSo/s1600/ronfagin.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMAsHCGi6OQLrfcI3BjX58nZYPjDeNP7HgZPiFlHp6b8iJV_qoMEO-QNXJl8HHKpd4iSOBbTWhUHkWCDLsl5RnOCKQj3yICseMz0qgvNC3pRxTD2Ssv_d-etOH86OYyJ71GMhVcGMdjGSo/s1600/ronfagin.jpg" width="150" /></a></div><div class="MsoNormal"><i style="mso-bidi-font-style: normal;"><span style="font-family: Verdana;">Ron is an IBM Fellow, which is IBM's highest technical honor. There are currently 87 active IBM Fellows, and there have been only 257 IBM Fellows in the 51-year history of the program.<span style="mso-spacerun: yes;">  </span>Ron received his B.A. in mathematics from Dartmouth College and his Ph.D. in mathematics from the University of California at Berkeley. He has won an IBM Corporate Award, eight IBM Outstanding Innovation Awards, an IBM Outstanding Technical Achievement Award, and two IBM key patent awards. He is a Fellow of IEEE, ACM, and AAAS (American Association for the Advancement of Science). He has co-authored three papers that won Best Paper Awards and three papers that won Test-of-time Awards, all in major conferences. One of his papers won the <a href="http://ibmresearchnews.blogspot.com/2014/05/simple-threshold-algorithm-earns-godel.html">2014 Gödel Prize</a>. He was named Docteur Honoris Causa by the University of Paris, and a "Highly Cited Researcher" by ISI (the Institute for Scientific Information). He won the IEEE Technical Achievement Award, IEEE W. Wallace McDowell Award, and ACM SIGMOD Edgar F. Codd Innovations Award (a lifetime achievement award in databases). In addition to the American Academy of Arts and Sciences, this year he was also elected to the US National Academy of Engineering.</span></i></div><br /><br />   <br /><br />

IBM Fellow Ron Fagin elected to the American Academy of Arts and Sciences

The American Academy of Arts and Sciences elected 204 new members across a number of categories, including eight computer scientists. One o...

<br /><div class="MsoNormal"><i style="mso-bidi-font-style: normal;">Editor’s note: this article is by IBM Fellow Ronald Fagin.</i></div><div class="MsoNormal"><br /></div><div class="MsoNormal">Lauded for its “elegant mathematical properties,” the threshold algorithm that I developed with two colleagues led to our writing a paper (<i style="mso-bidi-font-style: normal;"><a href="http://researcher.watson.ibm.com/researcher/files/us-fagin/jcss03.pdf">Optimal Aggregation Algorithms for Middleware</a></i>) that won the 2014 Gödel Prize, which is awarded jointly by the Association for Computing Machinery (ACM) Special Interest group on Algorithms and Computation, and the European Association for Theoretical Computer Science. The award is given annually for a breakthrough paper in theoretical computer science. Today, the algorithm is used in applications and systems that demand optimal results for gathering multi-sourced information. But its origin, and the paper’s, goes back to 1996. </div><div class="MsoNormal"><br /></div><div align="right"><table align="right" border="1" cellpadding="0" cellspacing="0" class="MsoTableGrid" style="border-collapse: collapse; border: none; margin-left: 6.75pt; margin-right: 6.75pt; mso-border-alt: solid white .5pt; mso-border-insideh: .5pt solid white; mso-border-insidev: .5pt solid white; mso-padding-alt: 0in 5.4pt 0in 5.4pt; mso-table-anchor-horizontal: column; mso-table-anchor-vertical: paragraph; mso-table-left: right; mso-table-lspace: 9.0pt; mso-table-overlap: never; mso-table-rspace: 9.0pt; mso-table-top: .05pt; mso-yfti-tbllook: 480;"> <tbody><tr style="mso-yfti-firstrow: yes; mso-yfti-irow: 0; mso-yfti-lastrow: yes;">  <td style="border: solid white 1.0pt; mso-border-alt: solid white .5pt; padding: 0in 5.4pt 0in 5.4pt; width: 2.5in;" valign="top" width="240"><div class="MsoNormal" style="mso-element-anchor-horizontal: column; mso-element-anchor-vertical: paragraph; mso-element-frame-hspace: 9.0pt; mso-element-left: right; mso-element-top: .05pt; mso-element-wrap: around; mso-element: frame; mso-height-rule: exactly;"><b style="mso-bidi-font-weight: normal;">Praise for threshold algorithm</b></div><div class="MsoNormal" style="mso-element-anchor-horizontal: column; mso-element-anchor-vertical: paragraph; mso-element-frame-hspace: 9.0pt; mso-element-left: right; mso-element-top: .05pt; mso-element-wrap: around; mso-element: frame; mso-height-rule: exactly;"><br /></div><div class="MsoNormal" style="mso-element-anchor-horizontal: column; mso-element-anchor-vertical: paragraph; mso-element-frame-hspace: 9.0pt; mso-element-left: right; mso-element-top: .05pt; mso-element-wrap: around; mso-element: frame; mso-height-rule: exactly;"><i style="mso-bidi-font-style: normal;">The paper provides a framework to design   and analyze algorithms where aggregation of information from multiple data   sources is needed, such as in information retrieval and machine learning. In   these situations, the threshold algorithm offers a very efficient method for   producing a single unified list of the ‘top k’ results from the combined data   sources. </i></div><div class="MsoNormal" style="mso-element-anchor-horizontal: column; mso-element-anchor-vertical: paragraph; mso-element-frame-hspace: 9.0pt; mso-element-left: right; mso-element-top: .05pt; mso-element-wrap: around; mso-element: frame; mso-height-rule: exactly;"><br /></div><div class="MsoNormal" style="mso-element-anchor-horizontal: column; mso-element-anchor-vertical: paragraph; mso-element-frame-hspace: 9.0pt; mso-element-left: right; mso-element-top: .05pt; mso-element-wrap: around; mso-element: frame; mso-height-rule: exactly;"><i style="mso-bidi-font-style: normal;">The threshold algorithm’s elegant   mathematical properties and simplicity are particularly suitable for use in   middleware, software that is often used to augment computer operating systems   that support complex, distributed applications. The authors also introduced   the notion of instance optimality, an extremely strong guarantee of   performance, and showed that the threshold algorithm is instance optimal. The   paper’s groundbreaking results have built a foundation for much follow-on   research.</i></div></td> </tr></tbody></table></div><div class="MsoNormal">In 1996, I wrote a paper about an efficient data aggregation algorithm (incidentally, referred to as “Fagin's algorithm”) that gathers information from multiple sources into a single top-<i style="mso-bidi-font-style: normal;">k</i>list (like gathering a “top 10” list within a given set of data). </div><div class="MsoNormal"><br /></div><div class="MsoNormal">In 2001, my colleagues, <a href="http://www.wisdom.weizmann.ac.il/~naor/">Moni Naor</a> and Amnon Lotem, and I developed a new, improved aggregation algorithm, which we called the threshold algorithm. It can be used when aggregation of information from multiple data sources is needed, to produce a top-<i style="mso-bidi-font-style: normal;">k</i> list. We showed that it is optimal in an extremely strong sense, in that no other algorithm can access less data than the threshold algorithm does and still obtain the correct answer.</div><div class="MsoNormal"><br /></div><div class="MsoNormal">Honestly, I was worried that the paper might be rejected because the algorithm was too simple. It took only 10 lines on a page to explain! But in our 2001 paper, we called it “remarkably simple” – sort of like turning a bug into a feature – and submitted the paper about it to the premier database theory conference, the ACM Symposium on Principles of Database Systems (<a href="http://www.sigmod.org/the-pods-pages">PODS</a>). The Occam’s razor approach worked. The paper was not only accepted, but won the Best Paper Award!<span style="mso-spacerun: yes;">  </span>It went on to win the Test-of-Time Award at PODS a decade later, and is now the <a href="http://www.acm.org/press-room/news-releases/2014/goedel-prize-14">Gödel Prize</a>’s first database paper, 13 years later (the Gödel Prize committee considers papers within a 14 year window).</div><div class="MsoNormal"><br /></div><span style="font-family: "Times New Roman"; font-size: 12.0pt; mso-ansi-language: EN-US; mso-bidi-language: AR-SA; mso-fareast-font-family: "MS Mincho"; mso-fareast-language: JA;">The algorithmic setting where it is desired to find a top-<i style="mso-bidi-font-style: normal;">k</i> list for information that is aggregated, while minimizing the number of database accesses, has proven to be an extremely useful one. The threshold algorithm (or a variation of it) has now been applied in a large number of settings, including databases (relational, multimedia, semi-structured, probabilistic, and spatial), semantic web, information retrieval, distributed sensor networks, and product design. In fact, according to Google Scholar, the paper has now been cited almost 1,500 times.</span><br /><span style="font-family: "Times New Roman"; font-size: 12.0pt; mso-ansi-language: EN-US; mso-bidi-language: AR-SA; mso-fareast-font-family: "MS Mincho"; mso-fareast-language: JA;"></span><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv4QG2uDYvN5Cxe7VS4ds-OGSLwbPR2cd7ttuPMQq7DRuRy-eX5y12c4wP7roH94VOHuYlcUynnFILnRqedRLdu-R7k3ju9EA8n-mEeUh5aj9kPLyMYjGdHuu9DqDnFk5Um7o4D6rd0W8X/s1600/ronfagin.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv4QG2uDYvN5Cxe7VS4ds-OGSLwbPR2cd7ttuPMQq7DRuRy-eX5y12c4wP7roH94VOHuYlcUynnFILnRqedRLdu-R7k3ju9EA8n-mEeUh5aj9kPLyMYjGdHuu9DqDnFk5Um7o4D6rd0W8X/s1600/ronfagin.jpg" width="150" /></a></div><span style="font-family: "Times New Roman"; font-size: 12.0pt; mso-ansi-language: EN-US; mso-bidi-language: AR-SA; mso-fareast-font-family: "MS Mincho"; mso-fareast-language: JA;"><i style="mso-bidi-font-style: normal;"><span style="font-family: "Times New Roman"; font-size: 12.0pt; mso-ansi-language: EN-US; mso-bidi-language: AR-SA; mso-fareast-font-family: "MS Mincho"; mso-fareast-language: JA;">Ron Fagin is an IBM Fellow, which is IBM's highest technical honor. There are currently 87 active IBM Fellows, and there have been only 257 IBM Fellows in the 51-year history of the program.<span style="mso-spacerun: yes;"></span>Ron received his B.A. in mathematics from Dartmouth College and his Ph.D. in mathematics from the University of California at Berkeley.<span style="mso-spacerun: yes;"> </span>He has won an IBM Corporate Award, eight IBM Outstanding Innovation Awards, an IBM Outstanding Technical Achievement Award, and two IBM key patent awards. He is a Fellow of IEEE, ACM, and AAAS (American Association for the Advancement of Science). He has co-authored three papers that won Best Paper Awards and three papers that won Test-of-time Awards, all in major conferences.<span style="mso-spacerun: yes;"> </span>He was named Docteur Honoris Causa by the University  of Paris, and a "Highly Cited Researcher" by ISI (the Institute for Scientific Information). He won the IEEE Technical Achievement Award, IEEE W. Wallace McDowell Award, and ACM SIGMOD Edgar F. Codd Innovations Award (a lifetime achievement award in databases).<span style="mso-spacerun: yes;"> </span>He is a member of the US National Academy of Engineering and the American  Academy of Arts and Sciences.</span></i> </span>

Almaden big data godel prize Ron Fagin “Simple” threshold algorithm earns Gödel Prize

Editor’s note: this article is by IBM Fellow Ronald Fagin. Lauded for its “elegant mathematical properties,” the threshold algorithm that I ...