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

Despite decades of research on approximate query processing (AQP), ourunderstanding of sample-based joins has remained limited and, to some extent,even superficial. The common belief in the community is that joining randomsamples is futile. This belief is largely based on an early result showing thatthe join of two uniform samples is not an independent sample of the originaljoin, and that it leads to quadratically fewer output tuples. However,unfortunately, this result has little applicability to the key questionspractitioners face. For example, the success metric is often the finalapproximation's accuracy, rather than output cardinality. Moreover, there aremany non-uniform sampling strategies that one can employ. Is sampling for joinsstill futile in all of these settings? If not, what is the best samplingstrategy in each case? To the best of our knowledge, there is no formal studyanswering these questions.  This paper aims to improve our understanding of sample-based joins and offera guideline for practitioners building and using real-world AQP systems. Westudy limitations of offline samples in approximating join queries: given anoffline sampling budget, how well can one approximate the join of two tables?We answer this question for two success metrics: output size and estimatorvariance. We show that maximizing output size is easy, while there is aninformation-theoretical lower bound on the lowest variance achievable by anysampling strategy. We then define a hybrid sampling scheme that captures allcombinations of stratified, universe, and Bernoulli sampling, and show thatthis scheme with our optimal parameters achieves the theoretical lower boundwithin a constant factor. Since computing these optimal parameters requiresshuffling statistics across the network, we also propose a decentralizedvariant where each node acts autonomously using minimal statistics.

Joins on Samples: A Theoretical Guide for Practitioners