Treffer: Streaming triangle counting: the impact of a degree oracle.

We give new results for the problem of approximating the number of triangles in graph streams, focusing on space-efficient algorithms that receive the input graph as a sequence of edges in arbitrary order. Our main contributions are: a) A two-pass algorithm that uses space. b) A one-pass algorithm that uses expected space and has access to a degree oracle. Our first result completes the picture for multi-pass triangle counting algorithms and it gives affirmative answer to an open question in Fichtenberger and Peng (PODS 2022) for the case of triangles where they asked if such a space bound is possible in two passes. It also matches the known lower bound of for the regime , thereby resolving the space complexity for this setting. Our second result establishes, for the first time, that access to a degree oracle can yield asymptotic improvements in the space complexity of one-pass algorithms. Specifically, for graphs with bounded arboricity b, our algorithm attains a space complexity of. Notably, in the absence of a degree oracle, existing lower bounds preclude the existence of one-pass, sublinear-space algorithms even for planar graphs. To complement this result, we show that any one-pass algorithm—even with degree oracle access—requires space, matching our upper bound for constant-arboricity graphs. In contrast, for dense graphs with and , we show that no sublinear space algorithm is possible even when allowed to query a degree oracle. [ABSTRACT FROM AUTHOR]

Copyright of Distributed & Parallel Databases is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)