Praise for threshold algorithm
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.
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.
The algorithmic setting where it is desired to find a top-k 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.
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.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. 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). He is a member of the US National Academy of Engineering and the American Academy of Arts and Sciences.