Rank and Score Aggregation       

Middleware and Datastores Accomplishment | 2003

IBM researcher: Ron Fagin

Where the work was done: IBM Almaden Research Center

What we accomplished: Paraphrasing the paper: "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. Each object is assigned an overall grade, that is obtained by combining the attribute grades using functions such as min or average. To determine the k objects with the highest overall grades, the naive algorithm must access every object in the database, to find its grade under each attribute. Fagin has given an algorithm that is much more efficient."

Related links: Optimal Aggregation Algorithms for Middleware (2003, Journal of Computer and System Sciences). In 2014, this paper won the Gödel Prize given by ACM’s Special Interest Group on Algorithms and Computation Theory [SIGACT].

Image credit: Slideplayer

BACK TO MIDDLEWARE and DATASTORES
BACK TO IBM RESEARCH ACCOMPLISHMENTS