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.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 3: Arne Andersson , Ola Petersson, Approximate indexed lists, Journal of Algorithms, v.29 n.2, p.256-276, Nov. 1998 [doi>10.1006/jagm.1998.0951]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: Alberto Caprara, Sorting Permutations by Reversals and Eulerian Cycle Decompositions, SIAM Journal on Discrete Mathematics, v.12 n.1, p.91-110, Jan. 1999 [doi>10.1137/S089548019731994X]
• 6: P. Diaconis. Group Representation in Probability and Statistics. IMS Lecture Series 11, IMS, 1988.
• 7: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. J. of the Royal Statistical Society, Series B, 39(2):262--268, 1977.
• 8: Paul F. Dietz, Optimal Algorithms for List Indexing and Subset Rank, Proceedings of the Workshop on Algorithms and Data Structures, p.39-46, August 17-19, 1989
• 9: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 10: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 11: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 12: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 13: Philippe Flajolet, Approximate counting: a detailed analysis, BIT, v.25 n.1, p.113-134, 1985 [doi>10.1007/BF01934993]
• 14: A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. A few good terms: Efficient streaming computation of wavelet decompositions. Manuscript, 2001.
• 15: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 16: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 17: Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
• 18: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 19: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 20: Christos Levcopoulos , Ola Petersson, Exploiting few inversions when sorting: sequential and parallel algorithms, Theoretical Computer Science, v.163 n.1-2, p.211-238, Aug. 30, 1996 [doi>10.1016/0304-3975(95)00256-1]
• 21: Robert Morris, Counting large numbers of events in small registers, Communications of the ACM, v.21 n.10, p.840-842, Oct. 1978 [doi>10.1145/359619.359627]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory