Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems

1. Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with a sorting primitive. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), IEEE Computer Society Press, Los Alamitos (2004)

   Google Scholar 

2. Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Computer and System Sciences 58(1), 137–147 (1999)

   Article  MATH  MathSciNet  Google Scholar 

3. Anderson, R., Miller, G.: A simple randomized parallel algorithm for list-ranking. Information Processing Letters 33(5), 269–273 (1990)

   Article  MATH  MathSciNet  Google Scholar 

4. Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Proceedings of the 21st ACM Symposium on Principles of Database Systems (PODS 2002), pp. 1–16. ACM Press, New York (2002)

   Google Scholar 

5. Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proc. 13th annual ACM-SIAM symposium on Discrete algorithms (SODA 2002), pp. 623–632. ACM Press, New York (2002)

   Google Scholar 

6. Blelloch, G., Maggs, B.: Parallel algorithms. In: The Computer Science and Engineering Handbook, pp. 277–315 (1997)

   Google Scholar 

7. Chiang, Y., Goodrich, M., Grove, E., Tamassia, R., Vemgroff, D., Vitter, J.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 139–149. ACM Press, New York (1995)

   Google Scholar 

8. Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: Proc. 17th Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2006), pp. 714–723. ACM Press, New York (2006)

   Chapter  Google Scholar 

9. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 207–216. Springer, Heidelberg (2004)

   Google Scholar 

10. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: Proceedings of the 16th ACM/SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 745–754 (2005)

    Google Scholar 

11. Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L ¹ difference algorithm for massive data streams. SIAM Journal on Computing 32(1), 131–151 (2002)

    Article  MATH  MathSciNet  Google Scholar 

12. Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: Proc. 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 389–398. ACM Press, New York (2002)

    Google Scholar 

13. Golab, L., Ozsu, M.: Data stream management issues: a survey. Technical report, School of Computer Science, University of Waterloo, TR CS-2003-08 (2003)

    Google Scholar 

14. Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: “External Memory algorithms”. DIMACS series in Discrete Mathematics and Theoretical Computer Science 50, 107–118 (1999)

    MathSciNet  Google Scholar 

15. Jájá, J.: An introduction to parallel algorithms. Addison-Wesley, Reading (1992)

    MATH  Google Scholar 

16. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambr. U. Press (1997)

    Google Scholar 

17. Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal of Computing 15(4), 1036–1053 (1986)

    Article  MATH  MathSciNet  Google Scholar 

18. Munro, I., Paterson, M.: Selection and sorting with limited storage. Theoretical Computer Science 12, 315–323 (1980)

    Article  MATH  MathSciNet  Google Scholar 

19. Muthukrishnan, S.: Data streams: algorithms and applications. Technical report (2003), Available at http://athos.rutgers.edu/~muthu/stream-1-1.ps

20. Reif, J.: Optimal parallel algorithms for integer sorting and graph connectivity. Technical Report TR 08-85, Aiken Comp. Lab, Harvard U., Cambridge (1985)

    Google Scholar 

21. Ruhl, M.: Efficient Algorithms for New Computational Models. PhD thesis, Massauchussets Institute of Technology (September 2003)

    Google Scholar 

22. Shiloach, Y., Vishkin, U.: An o(logn) Parallel Connectivity Algorithm. J. Algorithms 3(1), 57–67 (1982)

    Article  MATH  MathSciNet  Google Scholar 

23. Sullivan, M., Heybey, A.: Tribeca: A system for managing large databases of network traffic. In: Proceedings USENIX Annual Technical Conference (1998)

    Google Scholar 

24. Tarjan, R., Vishkin, U.: Finding biconnected components and computing tree functions in logarithmic parallel time. In: Proc. 25th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1984), pp. 12–20. IEEE Computer Society Press, Los Alamitos (1984)

    Google Scholar 

25. Ullman, J., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM Journal on Computing 20(1), 100–125 (1991)

    Article  MATH  MathSciNet  Google Scholar 

Download references