The IEEE Computer Society has awarded its 2011 Technical Achievement Award to Ronald Fagin, Manager, Foundations of Computer Science at IBM Research - Almaden, "for pioneering contributions to the theory of rank and score aggregation."
What is "rank aggregation"?
Assume a set of "voters" and a set of "candidates." Each voter provides a list of the candidates, in order of preference. Rank aggregation is the problem of determining a consensus ordering (1st place, 2nd place, 3rd place, etc.), or sometimes simply 1st place. In case each voter provides not only an ordered list of his preferences for the candidates, but a numerical score for each candidate, then this problem is called "score aggregation". Again, the goal is to obtain a consensus ordering of the candidates.
Rank aggregation and score aggregation have many applications in numerous fields, including databases, economics, and information retrieval (where a search engine such as Google aims to provide the user with a “top k list,” say, the top 10 matches). As an example of rank aggregation, a potential home-buyer might have one ranking of a set of houses based on location, another ranking based on price, another ranking based on quality of construction, and so on. We can think of each of the houses as a candidate, and each criterion (such as location, price, and quality of construction) as a voter. Thus, there is one voter who focuses only on location, another voter who focuses only on price, and so on. In this case, rank aggregation would obtain an overall ranking of the houses that takes into account all of the criteria.
In a solely authored 1996 paper, Fagin introduced a new model for score aggregation, where there is a fixed scoring function, such as the median or the mean, and where the consensus ranking of the candidates is in order of their overall score, based on the scoring function; the goal is to obtain the top k winners. If the score of every candidate by every voter were known, it would in principle be straightforward to determine the top k winners by a simple computation. The challenge, as Fagin presented it, is to determine the top k winners while minimizing the number of database accesses. Fagin defined an algorithm (widely called "Fagin's Algorithm"), which he showed was optimal in a certain precise sense, and which greatly influenced future research on score aggregation.
In 2001, Fagin, with Amnon Lotem and Moni Naor, defined a new algorithm (the "Threshold Algorithm") for score aggregation, which he showed was optimal in an even stronger sense: not just in the worst case or the average case, but in every case! This paper won two important awards. First, it won the Best Paper Award at the prestigious ACM Symposium on Principles of Database Systems (a.k.a. PODS, which is the premier database theory conference), and has now been widely implemented. Second, this paper very recently won the PODS "Test-of Time" Award, for the paper from the 2001 PODS conference that is now judged, 10 years later, to have had the most impact.
Fagin has also explored other aspects of rank aggregation. For example, a 2003 paper by Fagin (with Ravi Kumar and D. Sivakumar) shows how to define a distance between top k lists, such as the distance between rankings by two different search engines, and is widely used in information retrieval settings.
Ronald Fagin is a member of the IBM Academy of Technology. 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 has published over 100 papers, and has co-authored a book on "Reasoning about Knowledge." He has served on more than 30 conference program committees, including serving as Program Committee Chair of four different conferences.
He received his B.A. in mathematics from Dartmouth College, and his Ph.D. in mathematics from the University of California at Berkeley.
Accomplishments include:
- Winner of the 2004 ACM SIGMOD Edgar F. Codd Innovations Award, a lifetime achievement award in databases, for "fundamental contributions to database theory"
- IEEE Fellow for "contributions to finite-model theory and to relational database theory"
- ACM Fellow for "creating the field of finite model theory and for fundamental research in relational database theory and in reasoning about knowledge"
- AAAS Fellow for "fundamental contributions to computational complexity theory, database theory, and the theory of multi-agent systems"
- Named Docteur Honoris Causa by the University of Paris
- Named "Highly Cited Researcher" by the Institute for Scientific Information
- Recipient of Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, and the 2010 International Conference on Database Theory
About IEEE: With nearly 85,000 members, the IEEE Computer Society is the world's leading organization of computing professionals. Founded in 1946, it is the largest of IEEE's 38 societies. The Computer Society is dedicated to advancing the theory and application of computing and information technology. The IEEE Computer Society Technical Achievement Award is given for outstanding and innovative contributions to the fields of computer and information science and engineering or computer technology, usually within the past 10, and not more than 15, years. Contributions must have significantly promoted technical progress in the field. The award will be presented at an awards dinner on May 25 in Albuquerque, New Mexico.
On March 14, 2011, 75 IBM engineers and scientists from San Jose and Silicon Valley went “back to school” and spent a day at Overfelt High School in San Jose to discuss the value of math and science and the importance a future career in engineering. This Celebration of Service event to give back to the community was a follow-on to a successful Black Technology Family event, held in October 2010 and sponsored by the Silicon Valley Black Employee Network. Impressed with IBM’s commitment to education and the student’s interest in technology, Overfelt High School Principal Vito Chiala asked IBM to return to the school to present to a broader student audience its message of the potential of technology to positively impact education and careers.
Throughout the day, IBMers talked to students about math, science, Deep QA system Watson, which just won the heralded Jeopardy! match, the value of a college education, and what it was like to be an engineer. At lunchtime, Laura Clayton McDonnell, Vice President, Public Sector West IMT, joined a group of 70 high achieving students enrolled in AP Calculus and AP U.S. History, to reinforce the message of making the right choice to continue their education and the habits that are necessary for success at school and work. With over 600 students in 15 classes hearing the message about education, thanks goes out to Lynn Guest, Energy Coordinator for San Jose and Silicon Valley Lab, for organizing the successful event and for all of the IBMers who gave their time to inspire our youth to go to college and pursue a career in math and science.
