CS 789 THEORY SEMINAR [home]

Speaker:  Ravi Kumar    
Affiliation: Computer Science, IBM Almaden Research
Date: Monday, February 25, 2002
Title: Approximating the number of inversions in a data stream

Abstract: 

Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model
is a natural setting to design efficient algorithms.

We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation. The best space bound we achieve for this problem is O(log n loglog n) through a deterministic algorithm. For the more general problem of approximating the number of inversions between two permutations, we obtain a randomized O(sqrt(n) log n)-space algorithm. For approximating the number of inversions in a general list, we give a randomized O(sqrt(n) log^2 n)-space two-pass algorithm.

Joint work with: Miklos Ajtai, T. S. Jayram, and D. Sivakumar