Assume that each object in a database has m grades, or scores, one for each of m attributes. For example, an object can have a color grade, that tells how red it is, and a shape grade, that tells how round it is. For each attribute, there is a sorted list, which lists each object and its grade under that attribute, sorted by grade (highest grade first). Each object is assigned an overall grade, that is obtained by combining the attribute grades using a fixed monotone aggregation function (or combining rule), such as min or average. Our goal is to find the top k objects, while minimizing access to the lists. The problem arises in several contexts. In particular, the speaker originally considered it for the purpose of combining fuzzy information in a multimedia database system.
We define a very strong notion of optimality, which we call "instance optimality". An algorithm is instance optimal if, up to a constant factor, its performance is as good as every other (correct) algorithm, on every instance (in our case, on every database). We give an elegant and remarkably simple algorithm that is instance optimal for our problem (under some natural restrictions).
This research, which is joint with Amnon Lotem and Moni Naor, won the Best Paper Award for the 2001 ACM Symposium on Principles on Database Systems. The talk will be completely self-contained.
Ronald Fagin is manager of the Foundations of Computer Science group at the IBM Almaden Research Center in San Jose, California. He received his B.A. in mathematics from Dartmouth College and his Ph.D. in mathematics from the University of California at Berkeley. He has published over 100 papers, and has co-authored a book on "Reasoning about Knowledge". He has received six IBM Outstanding Innovation Awards, and an IBM key patent award. He was named a Fellow of the IEEE, a Fellow of ACM, and a "Highly Cited Researcher" by ISI (the Institute for Scientific Information). He was named Docteur Honoris Causa by the University of Paris. He is the winner of the 2004 ACM SIGMOD Edgar F. Codd Innovations Award for his "fundamental contributions to database theory".
Return to Santa Clara Valley Chapter IEEE Computer Society page.