Ronald Fagin, Phokion G. Kolaitis, et al.
SIGMOD/PODS/ 2004
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. In this overview, we discuss and compare algorithms for determining the top k objects, that is, k objects with the highest overall grades.
Ronald Fagin, Phokion G. Kolaitis, et al.
SIGMOD/PODS/ 2004
Catriel Beeri, Ronald Fagin, et al.
STOC 1981
Ronald Fagin, Phokion G. Kolaitis, et al.
SIGMOD/PODS 2003
Ronald Fagin, Ravi Kumar, et al.
SODA 1998