Krzysztof Onak: Krzysztof Onak moved page Waiting:Streaming Algorithms for Approximating the Number of Subgraphs to Open Problems:92 without leaving a redirect

2019-08-20T03:48:33Z

Krzysztof Onak moved page Waiting:Streaming Algorithms for Approximating the Number of Subgraphs to Open Problems:92 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-20T03:48:15Z

Updating the header

Ccanonne: 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..."

2019-08-07T21:57:17Z

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..."

New page

{{Header
|title=Streaming Algorithms for Approximating the Number of $H$-Subgraphs
|source=warwick18
|who=He Sun
}}
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.

← Older revision	Revision as of 03:48, 20 August 2019
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=warwick18
 |who=He Sun

Open Problems:92 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Streaming Algorithms for Approximating the Number of Subgraphs to Open Problems:92 without leaving a redirect

Krzysztof Onak: Updating the header

Ccanonne: 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..."