Paper Info
Title
Approximate counting of inversions in a data stream
Abstract
(MATH) 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 {14, 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. The best space bound we achieve is $O(\log n \log \log n)$ through a deterministic algorithm. In contrast, we derive an $\Omega(n)$ lower bound for randomized exact computation for this problem; thus approximation is essential.(MATH) We also consider two generalizations of this problem: (1) approximating the number of inversions between two permutations, for which we obtain a randomized $O(\sqrt{n} \log n)$-space algorithm, and (2) approximating the number of inversions in a general list, for which we obtain a randomized $O(\sqrt{n} \log^2 n)$-space two-pass algorithm. In contrast, we derive $\Omega(n)$-space lower bounds for deterministic approximate computation for these problems; thus both randomization and approximation are essential.All our algorithms use only O(log n) time per data item.
Year
DOI
Venue
2002
10.1145/509907.509964
STOC
Keywords
Field
DocType
best space,deterministic algorithm,space lower bound,data item,space two-pass algorithm,data stream model,space algorithm,approximate counting,efficient algorithm,log n,lower bound,streaming algorithm,zero knowledge
Discrete mathematics,Binary logarithm,Combinatorics,Streaming algorithm,Upper and lower bounds,Data stream,Generalization,Permutation,Deterministic algorithm,Mathematics,Computation
Conference
ISBN
Citations 
PageRank 
1-58113-495-9
26
2.46
References 
Authors
16
4
Name
Order
Citations
PageRank
Miklós Ajtai12621479.35
T. S. Jayram2137375.87
Ravi Kumar3139321642.48
D. Sivakumar43515389.02