# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 4 Materials and Methods
### Mp-Ega
#### 4.2.1 Using Balls into Bins Model to Determine Number of Partitions  
We can partition the data into \(P\) partitions, ensuring that each partition fits within the GPU memory, which reduces the problem to that discussed in the previous section. However, determining the optimal number of partitions is critical. Too many partitions result in smaller partition sizes, leading to insufficient GPU utilization. Additionally, an excessive number of partitions increases the number of GPU kernel invocations, which raises the fixed costs associated with these invocations. Conversely, too few partitions lead to larger partition sizes, potentially exceeding the GPU memory limits. Although we cannot guarantee that each partition will fit within GPU memory, it is acceptable for only a very small portion of partitions to exceed this limit. Intuitively, increasing the number of partitions reduces the probability of any single partition exceeding GPU memory. We can analyze this problem using the \"balls into bins\" model, where we consider the group of key-value pairs as balls and the partitions as bins. Given the limited GPU memory, the number of groups in each partition is also constrained. Let \(k\) represent the maximum number of groups allowed in each partition. Our goal is to ensure that the number of balls (key-value pairs) in each bin (partition) remains below \(k\). While we cannot guarantee that the number of balls in some bins will not exceed \(k\), we aim to keep the probability of this occurrence very low. Intuitively, as we increase the number of bins, the probability of any single bin exceeding \(k\) diminishes. The question then arises: how many bins are sufficient? We have established the following theorem to address this question. **Theorem 1**. : _Consider \(n\) balls randomly distributed across \(m\) bins. \(k\) is a positive integer greater than \(1\). \(p\) is a real number greater than \(0\) and less than \(1\). Let \(m_{0}=e^{\frac{k\ln\frac{\mathrm{Pr}}{k}-\ln p}{k-1}}\). If \(m\geq\lceil m_{0}\rceil\), then we have_  
\[\Pr[\text{all bins have at most $k$}{-}1\text{ balls}]\geq 1-p.\]  
Proof. : First, let us define some events as follows: \(A_{i}\): \"bin \(i\) has at least \(k\) balls\", \(B_{ij}\): \"the \(j^{th}\) subset whose size is \(k\) of \(n\) balls falls into the \(i\)th bin\", \(C\): \"at least one bin has at least \(k\) balls\", \(D\): \"all bins have at most \(k{-}1\) balls\". Suppose \(n\) balls have \(s\) subsets whose size are \(k\); it is obvious that \(s=( \begin{subarray}{c}n\\ k\end{subarray} )\). We can conclude that \(A_{i}\subset\bigcup_{j\in\{1,2,\dots,( \begin{subarray}{c}n\\ k\end{subarray} )\}}B_{ij}\), so we have \(\Pr[A_{i}]\leq\sum_{j=1}^{( \begin{subarray}{c}n\\ k\end{subarray} )}\Pr[B_{ij}]=\frac{( \begin{subarray}{c}n\\ k\end{subarray} )}{m^{k}}\). Since \(C\subset\bigcup_{i=1}^{m}A_{i}\), we have  
\[\Pr[C]\leq\Pr\Bigl{[}\bigcup_{i=1}^{m}A_{i}\Bigr{]}\leq\sum_{i=1}^{m}\Pr[A_ {i}]=m\frac{( \begin{subarray}{c}n\\ k\end{subarray} )}{m^{k}} \tag{1}\]  
Since we desire that \(\Pr[D]\geq 1-p\) and we have \(\Pr[D]=1-\Pr[C]\), it is equivalent to prove  
\[\Pr[C]\leq p \tag{2}\]  
From (1) and (2), we know that if we can prove that  
\[m\frac{\binom{n}{k}}{m^{k}}\leq p \tag{3}\]  
then we could prove (2). From [PERSON]'s approximation, we have  
\[k!\geq\left(\frac{k}{e}\right)^{k} \tag{4}\]  
Then we have  
\[\binom{n}{k}=\frac{n(n-1)\ldots(n-k+1)}{k!}\leq\frac{n^{k}}{k!}\leq\left(\frac{ne }{k}\right)^{k} \tag{5}\]  
From (3) and (5), we know that we should prove  
\[\left(\frac{ne}{k}\right)^{k}\leq pm^{k-1} \tag{6}\]  
Taking the logarithm of both sides of inequality (6), we obtain  
\[k\ln\frac{en}{k}\leq\ln p+(k-1)\ln m \tag{7}\]  
Suppose \(f(m)=(k-1)\ln m+\ln p-k\ln\frac{en}{k}\), then inequality (6) is equivalent to \(f(m)\geq 0\).