English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce Tiered Sampling, a novel technique for approximate countingsparse motifs in massive graphs whose edges are observed in a stream. Ourtechnique requires only a single pass on the data and uses a memory of fixedsize $M$, which can be magnitudes smaller than the number of edges.  Our methods addresses the challenging task of counting sparse motifs -sub-graph patterns that have low probability to appear in a sample of $M$ edgesin the graph, which is the maximum amount of data available to the algorithmsin each step. To obtain an unbiased and low variance estimate of the count wepartition the available memory to tiers (layers) of reservoir samples. Whilethe base layer is a standard reservoir sample of edges, other layers arereservoir samples of sub-structures of the desired motif. By storing morefrequent sub-structures of the motif, we increase the probability of detectingan occurrence of the sparse motif we are counting, thus decreasing the varianceand error of the estimate.  We demonstrate the advantage of our method in the specific applications ofcounting sparse 4 and 5-cliques in massive graphs. We present a completeanalytical analysis and extensive experimental results using both synthetic andreal-world data. Our results demonstrate the advantage of our method inobtaining high-quality approximations for the number of 4 and 5-cliques forlarge graphs using a very limited amount of memory, significantly outperformingthe single edge sample approach for counting sparse motifs in large scalegraphs.

Tiered Sampling: An Efficient Method for Approximate Counting Sparse Motifs in Massive Graph Streams