Approximate counting of inversions in a data stream
Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar · 2002
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 [16, 2] 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 to within a factor of ffl. The best space bound we achieve for this problem is O(log n log log n) through a deterministic algorithm. In contrast, we derive an \\Omega\\Gamma n) lower bound for randomized exact computation for this problem; thus approximation is essential. For the more general problem of approximating the number of inversions between two permutations, we obtain a randomized O( p n log n)-space algorithm. For approximating the number of inversions in a general list, we give a randomized O( p n log 2 n)-space two-pass algorithm. In contrast, we derive \\Omega\\Gamma n) lower bounds for deterministic approximate computation for these problems; thus randomization is essential. All our algorithms use only O(log n) time per data item. Our result for approximating the number of inversions in a permutation is unique and surprising in the following aspect: all of the existing streaming algorithms require randomization in a crucial way, whereas our algorithms are deterministic! 1