Document Open Access Logo

Space-Query Tradeoffs in Range Subgraph Counting and Listing

Authors Shiyuan Deng, Shangqi Lu, Yufei Tao

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.6.pdf
  • Filesize: 0.8 MB
  • 25 pages

Document Identifiers

Author Details

Shiyuan Deng
  • The Chinese University of Hong Kong, China
Shangqi Lu
  • The Chinese University of Hong Kong, China
Yufei Tao
  • The Chinese University of Hong Kong, China

Funding

Supported in part by GRF Projects 14207820, 14203421, and 14222822 from HKRGC.

Cite As Get BibTex

Shiyuan Deng, Shangqi Lu, and Yufei Tao. Space-Query Tradeoffs in Range Subgraph Counting and Listing. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICDT.2023.6

Abstract

This paper initializes the study of range subgraph counting and range subgraph listing, both of which are motivated by the significant demands in practice to perform graph analytics on subgraphs pertinent to only selected, as opposed to all, vertices. In the first problem, there is an undirected graph G where each vertex carries a real-valued attribute. Given an interval q and a pattern Q, a query counts the number of occurrences of Q in the subgraph of G induced by the vertices whose attributes fall in q. The second problem has the same setup except that a query needs to enumerate (rather than count) those occurrences with a small delay. In both problems, our goal is to understand the tradeoff between space usage and query cost, or more specifically: (i) given a target on query efficiency, how much pre-computed information about G must we store? (ii) Or conversely, given a budget on space usage, what is the best query time we can hope for? We establish a suite of upper- and lower-bound results on such tradeoffs for various query patterns.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Subgraph Pattern Counting
  • Subgraph Pattern Listing
  • Conjunctive Queries

Metrics

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

Related Versions

References

  1. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539, 2021. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  4. Albert Atserias, Martin Grohe, and Daniel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737-1767, 2013. Google Scholar
  5. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic, pages 208-222, 2007. Google Scholar
  6. Michael J Bannister, Christopher DuBois, David Eppstein, and Padhraic Smyth. Windows into relational events: Data structures for contiguous subsequences of edges. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 856-864, 2013. Google Scholar
  7. Jon Louis Bentley. Decomposable searching problems. Information Processing Letters (IPL), 8(5):244-251, 1979. Google Scholar
  8. Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2315-2332, 2021. Google Scholar
  9. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 303-318, 2017. Google Scholar
  10. Andreas Bjorklund, Petteri Kaski, and Lukasz Kowalik. Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Transactions on Algorithms, 13(4):48:1-48:26, 2017. Google Scholar
  11. Andreas Bjorklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 223-234, 2014. Google Scholar
  12. Nofar Carmeli and Markus Kroll. On the enumeration complexity of unions of conjunctive queries. ACM Transactions on Database Systems (TODS), 46(2):5:1-5:41, 2021. Google Scholar
  13. Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 393-409, 2020. Google Scholar
  14. Farah Chanchary and Anil Maheshwari. Time windowed data structures for graphs. J. Graph Algorithms Appl., 23(2):191-226, 2019. Google Scholar
  15. Farah Chanchary, Anil Maheshwari, and Michiel Smid. Querying relational event graphs using colored range searching data structures. Discrete Applied Mathematics, 286:51-61, 2020. Google Scholar
  16. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal of Computing, 17(3):427-462, 1988. Google Scholar
  17. N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal of Computing, 14(1):210-223, 1985. Google Scholar
  18. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 210-223, 2017. Google Scholar
  19. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Google Scholar
  20. Shaleen Deep and Paraschos Koutris. Compressed representations of conjunctive query results. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 307-322, 2018. Google Scholar
  21. Arnaud Durand. Fine-grained complexity analysis of queries: From decision to counting and enumeration. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 331-346, 2020. Google Scholar
  22. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log., 8(4):21, 2007. Google Scholar
  23. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 121-131, 2014. Google Scholar
  24. David Eppstein. Arboricity and bipartite subgraph listing algorithms. Information Processing Letters (IPL), 51(4):207-211, 1994. Google Scholar
  25. David Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl., 3(3):1-27, 1999. Google Scholar
  26. David Eppstein, Maarten Loffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In International Symposium on Algorithms and Computation (ISAAC), volume 6506, pages 403-414, 2010. Google Scholar
  27. Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Detecting and counting small pattern graphs. SIAM J. Discret. Math., 29(3):1322-1339, 2015. Google Scholar
  28. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. Journal of Computer and System Sciences (JCSS), 78(3):698-706, 2012. Google Scholar
  29. Ehud Friedgut. Hypergraphs, entropy, and inequalities. Am. Math. Mon., 111(9):749-760, 2004. Google Scholar
  30. Pierre-Louis Giscard, Nils M. Kriege, and Richard C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 81(7):2716-2737, 2019. Google Scholar
  31. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Algorithms and Data Structures Workshop (WADS), pages 421-436. Springer, 2017. Google Scholar
  32. Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the hardness of set disjointness and set intersection with bounded universe. In International Symposium on Algorithms and Computation (ISAAC), pages 7:1-7:22, 2019. Google Scholar
  33. Chinh T. Hoang, Marcin Kaminski, Joe Sawada, and R. Sritharan. Finding and listing induced paths and cycles. Discrete Applied Mathematics, 161(4-5):633-641, 2013. Google Scholar
  34. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in static and dynamic evaluation of hierarchical queries. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 375-392, 2020. Google Scholar
  35. Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 297-308, 2013. Google Scholar
  36. Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst-case and beyond. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 213-228, 2015. Google Scholar
  37. Ton Kloks, Dieter Kratsch, and Haiko Müller. Finding and counting small induced subgraphs efficiently. Information Processing Letters (IPL), 74(3-4):115-121, 2000. Google Scholar
  38. Jaroslav Nesetril and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  39. Hung Q. Ngo, Ely Porat, Christopher Re, and Atri Rudra. Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):16:1-16:40, 2018. Google Scholar
  40. Hung Q. Ngo, Christopher Re, and Atri Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec., 42(4):5-16, 2013. Google Scholar
  41. Dan Olteanu and Jakub Zavodny. Size bounds for factorised representations of query results. ACM Transactions on Database Systems (TODS), 40(1):2:1-2:44, 2015. Google Scholar
  42. Saladi Rahul. Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in ℝ³. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 200-211, 2015. Google Scholar
  43. Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 151-163, 2018. Google Scholar
  44. Luc Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD Rec., 44(1):10-17, 2015. Google Scholar
  45. Luc Segoufin and Alexandre Vigny. Constant delay enumeration for FO queries over databases with local bounded expansion. In Proceedings of International Conference on Database Theory (ICDT), volume 68, pages 20:1-20:16, 2017. Google Scholar
  46. Yufei Tao. Algorithmic techniques for independent query sampling. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), 2022. Google Scholar
  47. Yufei Tao and Ke Yi. Intersection joins under updates. Journal of Computer and System Sciences (JCSS), 124:41-64, 2022. Google Scholar
  48. Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of International Conference on Database Theory (ICDT), pages 96-106, 2014. Google Scholar
  49. Duncan J. Watts and Steven H. Strogatz. Collective dynamics of `small-world' networks. Nature, 393:440-442, 1998. Google Scholar
  50. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal of Computing, 42(3):831-854, 2013. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact