Gems of PODS
This year, PODS will feature the inaugural Gems of PODS event. The Gems of PODS event features topics and results in PODS that have been highly influential in the PODS community and beyond. There will be two Gems of PODS speakers this year and their talks will be held on Monday June 27, 1:30pm to 3:00pm.
Gems Talk 1
Optimal Score Aggregation Algorithms
Ronald Fagin (IBM Research - Almaden)
Abstract
Assume that there is a set of "voters" and a set of "candidates", where each voter assigns a numerical score to each candidate. There is a scoring function (such as the mean or the median), and a consensus ranking is obtained by applying the scoring function to each candidate's scores. The problem is to find the top k candidates, while minimizing the number of database accesses. The speaker will present an algorithm that is optimal in an extremely strong sense: not just in the worst case or the average case, but in every case! Even though the algorithm is only 10 lines long (!), the paper containing the algorithm won the 2014 Gödel Prize, the top prize for a paper in theoretical computer science.
Bio
Ronald Fagin is an IBM Fellow at IBM Research - Almaden. IBM Fellow is IBM's highest technical honor. There are currently around 90 active IBM Fellows (out of around 400,000 IBM employees worldwide), and there have been only around 250 IBM Fellows in the over 50-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 is a Fellow of IEEE, ACM, and AAAS (American Association for the Advancement of Science). He has co-authored four 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. 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.
Gems Talk 2
Hypertree Decompositions: Questions and Answers
Georg Gottlob (University of Oxford)
Abstract
In the database context, the hypertree decomposition method is used for query optimization, whereby conjunctive queries having a low hypertree width (i.e., a low degree of cyclicity) can be recognized and decomposed automatically, and efficiently evaluated. Queries having bounded hypertree width are also highly parallelizable. Hypertree decompositions were introduced at ACM PODS 1999. This talk reviews - in form of questions and answers - the main relevant concepts and algorithms and surveys selected related work including applications and test results. The talk is accompanied by a paper of the same title authored by Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello.
Bio
Georg Gottlob is a Professor of Informatics at Oxford University, a Fellow of St John's College, Oxford, and an Adjunct Professor at TU Wien. His interests include knowledge representation, database theory, query processing, web data extraction, and (hyper)graph decomposition techniques. Gottlob has received the Wittgenstein Award from the Austrian National Science Fund, is an ACM Fellow, an ECCAI Fellow, a Fellow of the Royal Society, and a member of the Austrian Academy of Sciences, the German National Academy of Sciences, and the Academia Europaea. He chaired the Program Committees of IJCAI 2003 and ACM PODS 2000 and is on the Editorial Boards of JACM and JCSS. He was a founder of Lixto, a web data extraction firm acquired in 2013 by McKinsey & Company, and has recently co-founded Wrapidity, a spin out of Oxford University based on fully automatized web data extraction technology developed in the context of his ERC Advanced Grant "DIADEM: Domain-centric Intelligent Automated Data Extraction Met hodology" (diadem.cs.ox.ac.uk).
