Semi-Streaming Algorithms for Annotated Graph Streams

Author Justin Thaler



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.59.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Justin Thaler

Cite AsGet BibTex

Justin Thaler. Semi-Streaming Algorithms for Annotated Graph Streams. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 59:1-59:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.59

Abstract

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require Omega(n^2) space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of graph problems - these algorithms use space O(n*polylog(n)). In the annotated data streaming model of Chakrabarti et al. [Chakrabarti/Cormode/Goyal/Thaler, ACM Trans. on Alg. 2014], a computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider, who not only performs the requested computation, but also proves that the answer is correct. We consider the notion of semi-streaming algorithms for annotated graph streams (semistreaming annotation schemes for short). These are protocols in which both the client's space usage and the length of the proof are O(n*polylog(n)). We give evidence that semi-streaming annotation schemes represent a more robust solution concept than does the standard semi-streaming model. On the positive side, we give semi-streaming annotation schemes for two dynamic graph problems that are intractable in the standard model: (exactly) counting triangles, and (exactly) computing maximum matchings. The former scheme answers a question of Cormode [Cormode, Problem 47]. On the negative side, we identify for the first time two natural graph problems (connectivity and bipartiteness in a certain edge update model) that can be solved in the standard semi-streaming model, but cannot be solved by annotation schemes of "sub-semi-streaming" cost. That is, these problems are as hard in the annotations model as they are in the standard model.
Keywords
  • graph streams
  • stream verification
  • annotated data streams
  • probabilistic proof systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In SODA, pages 459-467, 2012. URL: http://dl.acm.org/citation.cfm?id=2095156.
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In PODS, pages 5-14, 2012. URL: http://dx.doi.org/10.1145/2213556.2213560.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: http://dx.doi.org/10.1007/BF02523189.
  4. László Babai. Trading group theory for randomness. In STOC, pages 421-429, 1985. URL: http://dx.doi.org/10.1145/22145.22192.
  5. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623-632, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
  6. Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler. Annotations for sparse data streams. In SODA, pages 687-706, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.52.
  7. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Trans. Algorithms, 11(1):7:1-7:30, 2014. URL: http://dx.doi.org/10.1145/2636924.
  8. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable stream computation and arthur-merlin communication. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 217-243, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.217.
  9. Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz. Memory delegation. In CRYPTO, pages 151-168, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22792-9_9.
  10. Graham Cormode and Donatella Firmani. A unifying framework for l₀-sampling algorithms. Distributed and Parallel Databases, 32(3):315-335, 2014. URL: http://dx.doi.org/10.1007/s10619-013-7131-9.
  11. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In ITCS, pages 90-112, 2012. URL: http://dx.doi.org/10.1145/2090236.2090245.
  12. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. Algorithmica, 65(2):409-442, 2013. URL: http://dx.doi.org/10.1007/s00453-011-9598-y.
  13. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. PVLDB, 5(1):25-36, 2011. URL: http://www.vldb.org/pvldb/vol5/p025_grahamcormode_vldb2012.pdf.
  14. Ashish Goel, Michael Kapralov, and Ian Post. Single pass sparsification in the streaming model with edge deletions. CoRR, abs/1203.4900, 2012. URL: http://arxiv.org/abs/1203.4900.
  15. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC'08, pages 113-122, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1374376.1374396.
  16. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: http://dx.doi.org/10.1137/0218012.
  17. Michael T. Goodrich and Michael Mitzenmacher. Invertible bloom lookup tables. In Allerton, pages 792-799, 2011. URL: http://dx.doi.org/10.1109/Allerton.2011.6120248.
  18. Tom Gur and Ran Raz. Arthur-Merlin streaming complexity. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming: Part I, ICALP'13, Berlin, Heidelberg, 2013. Springer-Verlag. Google Scholar
  19. Hartmut Klauck and Ved Prakash. Streaming computations with a loquacious prover. In ITCS, pages 305-320, 2013. URL: http://dx.doi.org/10.1145/2422436.2422471.
  20. Hartmut Klauck and Ved Prakash. An improved interactive streaming algorithm for the distinct elements problem. In ICALP (1), pages 919-930, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_76.
  21. Troy Lee, Frédéric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle finding and associativity testing. In SODA, pages 1486-1502, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.107.
  22. List of open problems in sublinear algorithms: Problem 47. URL: http://sublinear.info/47.
  23. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39:859-868, October 1992. URL: http://dx.doi.org/10.1145/146585.146605.
  24. Andrew McGregor. Graph mining on streams. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, pages 1271-1275. Springer US, 2009. URL: http://dx.doi.org/10.1007/978-0-387-39940-9_184.
  25. Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Rec., 43(1):9-20, May 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  26. S. Muthukrishnan. Data Streams: Algorithms And Applications. Foundations and Trends in Theoretical Computer Science. Now Publishers Incorporated, 2005. Google Scholar
  27. Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. Streaming authenticated data structures. In EUROCRYPT, pages 353-370, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38348-9_22.
  28. A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6(14):1870-1881, September 2013. URL: http://dx.doi.org/10.14778/2556549.2556569.
  29. Adi Shamir. IP = PSPACE. J. ACM, 39:869-877, October 1992. URL: http://dx.doi.org/10.1145/146585.146609.
  30. Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In WWW, pages 607-614, 2011. URL: http://dx.doi.org/10.1145/1963405.1963491.
  31. Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In CRYPTO (2), pages 71-89, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40084-1_5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail