Abstract : Executing Join-Aggregate queries on Big Data can incur enormous computational costs. Hence, the Approximate Aggregate Query Processing Techniques (AQPTs) are an attractive choice to execute such join-aggregate queries, because they incur limited computational costs. The AQPTs utilize random sampling to approximately execute a given join aggregate query. However, the effectiveness of random sampling is highly correlated with the number of qualifying tuples of the given query. If the given query h