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
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.
The company operates while ieee research paper using strictest safety measures techniques that is included in pursuing rigid guidelines in connection with dealing with from the papers.
ReplyDelete