CS 789 THEORY SEMINAR [home]

Speaker:  David P. Williamson
Affiliation: IBM Almaden Research Center
Date: Monday, February 10, 2003
Title: Aggregation Algorithms and Some Applications

Abstract:

This talk will describe one of the current active areas of interest in the Theory department at IBM Almaden: algorithms that efficiently combine ordered sources of information into a single "top k" list. In score aggregation, given ordered lists containing the scores of attributes of the elements of a database, the goal is to efficiently  find the k highest scoring elements under a prespecified aggregation rule. the goal is to efficiently find the top k scoring In rank aggregation, the goal is to find a meaningful top k list of elements given the top k lists of several experts. In order to do the latter, we discuss notions of the distance between top k lists.

We then turn to describing some applications of score and rank aggregation. The first is a metasearch engine that computes its results via rank aggregation. The second is a set of experiments computing search engine distance via top k distance notions. The third is a practical and database-friendly algorithm for computing nearest neighbors while using only sublinear additional space.

The work described in the talk above was performed by Cynthia Dwork (now at Microsoft Research), Ronald Fagin, Ravi Kumar, Moni Naor (a visitor from the Weizmann Institute), and Dandapani Sivakumar.