DeepSampling: Selectivity Estimation with Predicted Error and Response Time

This paper focuses on the prediction model for the selectivity estimation problem but the proposed approach can be easily generalized to other problems such as K-means clustering or spatial partitioning. The goal is to find the relationship between accuracy and sample size and toward this goal we define two problems, accuracy prediction and sample size estimation which are both defined in this section. First, we will define the accuracy of an approximate answer in the selectivity estimation (SE) problem.

Based on this definition, we define the following two problems:

Problem 1 (Sampling Ratio Estimation): Given a dataset $D$, a query range $Q$, and a desired accuracy $\alpha$, predict the minimum value of sampling ratio $\sigma$ such that $acc(\pi,\Pi)\geq\alpha$.

Problem 2 (Accuracy Prediction): Given a dataset $D$, a query range $Q$, and a sampling ratio $\sigma$, predict the accuracy $\alpha$ such that $|acc(\pi,\Pi)-\alpha|$ is minimized.

Both problems are very important in approximate geospatial query processing. If we could address these problems, the existing spatial database systems could minimize the computation effort for sampling process while still achieving a desired accuracy for their answers. Figure 2 shows how DeepSampling enhances performance of existing approximate query processing systems. Instead of fixing a sampling ratio as Figure 2(a), an AQP engine can use Problem 1 to calculate a suggested minimal sampling size to achieve the used-desired accuracy as shown in Figure 2(b). Conversely, if the system has a fixed sampling ratio, it can apply Problem 2 to estimate the result accuracy as shown in Figure 2(c).

In general, we know that the accuracy ($\alpha$) of an approximate answer increases with the sampling ratio ($\sigma$). However, we show in this part that this relationship is more complex than that. Figure 3 shows examples of how these two quantities are related to each other. First, Figure 3(a) shows that this relationship highly depends on the dataset distribution. While for all distributions the sampling ratio and accuracy are highly correlated, the relationship is different for each dataset. For example, for the rotated diagonal dataset, the accuracy ranges from 96% to 99% for all sampling ratios while for the mixed distribution dataset, the accuracy ranges from 22% to 90%. Second, Figure 3(b) shows the relationship for different query sizes. This time, we see that the relationship highly depends on the query size as well.

These observations show how challenging the problem is. To build an accurate model, we need to take into account the input data distribution and the query size. For other problems, the query size could be replaced with other query parameters, e.g., the number of clusters for the K-means clustering problem, or the number of partitions for the spatial partitioning problem.

Figure 4 shows an overview of the proposed architecture of the DeepSampling model. This architecture is used to solve both problems described earlier, sampling ratio estimation and accuracy prediction. To avoid repetition, we write between (parentheses) the changes that need to be made for the accuracy prediction problem.

To build an accurate and portable model that accounts for the query size and the data distribution, the proposed model takes two sets of inputs, tabular data and data distribution.

The tabular input layer consists of data taken from the processing logs which includes the query size ($q$), the sampling ratio ($\sigma$), and the resulting accuracy ($\alpha$). If we need to apply this architecture for other problems, then the query size will be replaced with other query parameters, e.g., number of clusters. Also, the accuracy will be calculated differently. This data is passed to a multi-layer perceptron (MLP) model. MLP is a feedforward neural network with at least three layers of nodes: an input layer, a hidden layer and an output layer. We chose MLP for tabular input since it can be used to learn complex mathematical models by regression analysis (Cybenko, 1989).

The data distribution input layer catches the distribution of the input dataset. In this paper, we use a uniform histogram which is expected to accurately catch the dataset distribution if computed at a reasonable resolution. The histogram resolution is a system parameter that we study in the experiments section. Since this histogram is a $2$D matrix with spatial relationship between histogram bins, it is fed to a convolutional neural network (CNN) layer.

The concatenation layer combines the output of the MLP and CNN layers together and feed them to a fully connected (FC) layer. The final layer of FC is a single node with linear activation so that the model output is the predicted sampling ratio (or accuracy). The loss function of the final node provides a feedback on how accurate the predicted value is. Based on the problem definition in Section 3.1, we use mean absolute percentage error (MAPE) as the loss function which is the average absolute percentage error of actual value $A_{t}$ and forecast value $F_{t}$ for all training points $t\in[1,n]$ as shown in Equation 2. MAPE is commonly used in regression models since it is very intuitive interpretation for relative errors.

We implement the proposed model in Figure 4 using Keras (Chollet et al., 2015). The source code, training data and models are available at (Vu and Eldawy, 2020).

Datasets: We use both synthetic and real datasets in our experiments. We generated a total of $144$ synthetic datasets using the open-source spatial data generator (Vu et al., 2019). The dataset distributions are listed in Table 1 and the detailed distribution parameters are included in the source code (Vu and Eldawy, 2020). We also used two real datasets: OSM-Nodes (Eldawy and Mokbel, 2019a) and OSM-Lakes (Eldawy and Mokbel, 2019b). The real datasets are only used for testing but never for training the model.

Parameters: In addition to the dataset distribution, we also vary the sampling ratio ($\sigma$), the query size ($q$), and the histogram size ($h$). The query size is the ratio between the area of the query rectangle and the area of the input minimum bounding rectangle (MBR). Our query workload consists of square queries centered at random locations in the input space. Table 1 summarizes all the parameters that we vary in our experiments. In total, our generated dataset contains $54,720$ data points.

Metrics: We use mean absolute percentage error (MAPE) to evaluate the accuracy of a prediction model. The lower the value of MAPE, the better the model is.

Baseline method: We compare the proposed model to a linear regression(LR) model which takes the tabular input and predict a numeric output. The reason behind this choice is that we want to see how the dataset distribution input makes a difference to the baseline which only takes query attributes into account.

In the first experiment, we build a model to predict the average query accuracy, given the sampling ratio, query size and dataset histogram of size $16\times 16$. In particular, we use the synthetic datasets with $54,720$ data points described in Section 4.1 to train and test our proposed model. To observe how training data distribution affects the test accuracy, we organized the training data into different combinations of $1$ to $7$ distributions in Table 1. For each combination, we take a split of $75\%$ data points for training process. We test all the trained models with $25\%$ of the synthetic data points. We also test on $2800$ data points that we collected from SE queries on real OSM-Nodes and OSM-Lakes dataset.

Figure 5(a) shows an interesting observation that the more data distributions we used for training process, the more accurate it is. This is expected since some simple distributions might not be able to capture important insights of test datasets. DeepSampling model is doing very well when we tested on both synthetic data and real data (MAPE is around $3\%$ and $16\%$). This shows the portability of the model. Even though the model was trained only on synthetic data, it still provided good results for the real dataset. In the future, we plan to add more synthetic data to make the model even more accurate with real data. On the other hand, the linear regression baseline, due to its simplicity and the lack of data distribution, did not achieve a good accuracy. For the test on real dataset, its prediction is even more than $100\%$ beyond the actual mean accuracy value.

In this experiment, we build a model based on DeepSampling to predict sampling ratio, given a desired query accuracy, query size and dataset histogram of size $16\times 16$. We use the same set of training and testing split as mentioned in Section 4.2.

Table 5(b) shows that DeepSampling is still doing better than the baseline when applied on both synthetic and real data. The errors are relatively higher than the accuracy prediction problem in Section 4.2. The reason is that the range of the accuracy in the training set is narrow as compared to the range of sampling ratio. For example, in Figure 3, the accuracy in some cases stays above 95% while the sampling ratio ranges from 0.1% to 20%. Nonetheless, the DeepSampling approach is consistently more accurate than the linear regression baseline. These results are consistent with existing work that found that the sampling ratio estimation problem is more difficult. For example, in BlinkDB (Agarwal et al., 2013) this problem is solved by simply choosing from a predefined set of points, sampling ratio and accuracy, and interpolating between them if needed.

To choose a good histogram size, this experiment studies the trade-off between the model accuracy and training time as we vary the histogram size as depicted in Figure 6. In this experiment, we vary the histogram resolution from $1\times 1$ (effectively no histogram) to $64\times 64$. Figure 6(a) shows the accuracy of the model when tested on both synthetic and real data as the histogram size increases. It is clear from this experiment that the histograms with higher resolutions carry more information that makes the model more accurate. However, the model stabilizes at $16\times 16$ where the histogram is accurate enough to catch the distributions in the training set.

Figure 6(b) shows the total time of the training phase, i.e., the time until the model stabilizes. As expected, the model takes more time to train as the histogram resolution increases due to the large input that goes through the CNN model. From this experiment, we choose to set the histogram size to $16\times 16$ which gives a good accuracy in a reasonable time.