The idea of rank aggregation is most easily introduced with an example: Suppose we query many search engines, receiving many lists of rankings for web sites. How do we produce a single list from these multiple rankings?
This question becomes somewhat more complicated when we allow ties in the ranking-- a concern particularly for databases when the range of possible attributes is small. We examine several reasonable metrics for comparing two rankings with ties, and prove that the values given by these metrics are within a constant factor of each other. These distance measures are natural generalizations of measures used in the rankings-without-ties case.
We also examine the problem of rank aggregation, advocating the median rank as a good aggregator. We have results not just for producing rankings with ties, but for rankings without ties and for "top k lists" (outputting only the 10 most highly ranked items, for instance).
Joint work with Ron Fagin, Ravi Kumar, Mohammad Mahdian, and D. Sivakumar.