In consumer applications some queries require ranking results based on some criterion.

Quality may be expressed with a variable degree of objectivity and subjectivity.

• Totally objective: quality is a deterministic function of some attribute values.
• Totally subjective: the best objects are the ones considered as such by a number of people.

Aggregation

Election approach

When having a set of voter, each proposing a different ranking, the final aggregation can be achieved in different ways.

• Borda proposal’s winner is the candidate with the lowest penalty
• Condorcet proposal’s winner is the candidate who defeats the most candidates in pairwise majority rule elections

Metric approach

The objective is to find a new ranking R (of k elements) whose total distance to the initial rankings R1, …, Rn is minimized.

• Kendall tau distance K(R1, R2) is defined as the number of exchanges in a bubble sort to convert R1 to R2
• Spearman’s foot-rule distance F(R1, R2) adds up the distance between the ranks of the same item in the two rankings

MedRank algorithm

An approximation of the foot-rule optimal aggregation can be found in the MedRank algorithm: use sorted accesses in each list, one element at a time, until there are k elements that occur in more than n/2 lists.

Algorithms with scores

The objective is to find a new ranking R (of k elements) when having rankings R1, …, Rn of partial scores.

B0 algorithm

The algorithm works only if the scoring function is the max function among all the attributes used for scoring.

Make k sorted accesses on each list and store objects and partial scores in a buffer. Then, for each object in the buffer, compute their max function over just the available partial scores in the buffer and return the k objects with maximum score.