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/

Zendy Plus

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

Zendy Tools

Zendy Open

Given a join with an acyclic set of degree constraints, we show how to draw auniformly random sample from the join result in $O(\mathit{polymat}/ \max \{1,\mathrm{OUT} \})$ expected time after a preprocessing of $O(\mathrm{IN})$expected time, where $\mathrm{IN}$, $\mathrm{OUT}$, and $\mathit{polymat}$ arethe join's input size, output size, and polymatroid bound, respectively. Thiscompares favorably with the state of the art (Deng et al.\ and Kim et al., bothin PODS'23), which states that a uniformly random sample can be drawn in$\tilde{O}(\mathrm{AGM} / \max \{1, \mathrm{OUT}\})$ expected time after apreprocessing phase of $\tilde{O}(\mathrm{IN})$ expected time, where$\mathrm{AGM}$ is the join's AGM bound.  We then utilize our techniques to tackle {\em directed subgraph sampling}.Let $G = (V, E)$ be a directed data graph where each vertex has an out-degreeat most $\lambda$, and let $P$ be a directed pattern graph with $O(1)$vertices. The objective is to uniformly sample an occurrence of $P$ in $G$. Theproblem can be modeled as join sampling with input size $\mathrm{IN} =\Theta(|E|)$ but, whenever $P$ contains cycles, the converted join has {\emcyclic} degree constraints. We show that it is always possible to throw awaycertain degree constraints such that (i) the remaining constraints are acyclicand (ii) the new join has asymptotically the same polymatroid bound$\mathit{polymat}$ as the old one. Combining this finding with our new joinsampling solution yields an algorithm to sample from the original (cyclic) join(thereby yielding a uniformly random occurrence of $P$) in $O(\mathit{polymat}/\max \{1, \mathrm{OUT}\})$ expected time after $O(|E|)$ expected-timepreprocessing. We also prove similar results for {\em undirected subgraphsampling} and demonstrate how our techniques can be significantly simplified inthat scenario.

Join Sampling under Acyclic Degree Constraints and (Cyclic) Subgraph Sampling