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 study ranked enumeration for Conjunctive Queries (CQs) where the answersare ordered by a given ranking function (e.g., an ORDER BY clause in SQL). Wedevelop "any-k" algorithms, which, without knowing the number k of desiredanswers, push down the ranking into joins by carefully ordering the computationof intermediate tuples and avoiding materialization of join answers until theyare needed. For this to be possible, the ranking function needs to obey aparticular type of monotonicity. Supported ranking functions include the commonsum-of-weights, where answers are compared by the sum of input-tuple weights,as well as any commutative selective dioid. Our results extend a well-knownunranked-enumeration dichotomy, which states that only free-connex CQs aretractable (under certain hardness hypotheses and for CQs without self-joins).For this class of queries and with n denoting the size of the input, the datacomplexity of our ranked enumeration approach for the time to the kth CQ answeris O(n+klogk), which is only a logarithmic factor slower than the O(n+k)unranked-enumeration guarantee. A core insight of our work is that rankedenumeration for CQs is closely related to Dynamic Programming and thefundamental task of path enumeration in a weighted DAG. We uncover a previouslyunknown tradeoff: one any-k algorithm has lower complexity when the number ofreturned answers is small, the other when their number is large. This tradeoffis eliminated under a stricter monotonicity property that we define and exploitfor a novel algorithm that asymptotically dominates all previously knownalternatives, including Eppstein's algorithm for sum-of-weights pathenumeration. We empirically demonstrate the findings of our theoreticalanalysis in an experimental study that highlights the superiority of ourapproach over the join-then-rank approach that existing database systemsfollow.

Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries