Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation

Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis +3

We study the problem of estimating the value of sums of the form $S_p\triangleq \sum \left(\genfrac{}{}{0ex}{}{x_i}{p}\right)$ when one has the ability to sample $x_i\ge 0$ with probability proportional…