Optimal Aggregation Algorithms for Middleware

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). There is some monotone aggregation function, or
combining rule, such as min or average, that combines the individual grades to obtain an overall grade. To determine objects that have the best overall grades, the naive algorithm must access every object in the database, to find its grade under each attribute. Fagin has given an algorithm ("Fagin’s Algorithm", or FA) that is much more efficient. For some distributions on grades, and for some monotone aggregation functions, FA is optimal in a high-probability sense. We give an elegant and remarkably simple algorithm ("the threshold algorithm", or TA) that is optimal in a much stronger sense than FA. We show that TA is essentially optimal, not just for some monotone aggregation functions, but for all of them, and not just in a high-probability sense, but over every database. Unlike FA, which requires large buffers (whose size may grow unboundedly as the database size grows), TA requires only a small, constant-size buffer.