Difference between revisions of "Open Problems:92"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Streaming Algorithms for Approximating the Number of $H$-Subgraphs |source=warwick18 |who=He Sun }} Designing a streaming algorithm that approximately computes...")
 
m (Krzysztof Onak moved page Waiting:Streaming Algorithms for Approximating the Number of Subgraphs to Open Problems:92 without leaving a redirect)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Streaming Algorithms for Approximating the Number of $H$-Subgraphs
 
 
|source=warwick18
 
|source=warwick18
 
|who=He Sun
 
|who=He Sun

Latest revision as of 03:48, 20 August 2019

Suggested by He Sun
Source Warwick 2018
Short link https://sublinear.info/92

Designing a streaming algorithm that approximately computes the number of a subgraph is an intensively studied problem with applications in data mining and database theory. The space complexities of such algorithms are usually a function of $\#$H (the number of subgraph $H$), so an algorithm gives a good approximation of $\#H$ in sublinear space only if a reasonable lower bound of $\#H$ is known in advance, which is not realistic for some scenarios. It’s practically interesting to study the possibility of designing a multi-pass streaming algorithm which gives a guaranteed approximation of $\#H$ and does not assume the knowledge of a lower bound of $\#H$. Specifically, it is interesting to see, for any algorithm that gives an $\alpha$-approximation of $\#H$, the relationship needed among $\alpha$, the space complexity and the number of passes (not necessarily a constant) that the algorithm needs to read the input graph stream.