Large-scale predictive modeling and analytics through regression queries in data management systems

We focus on in-DMS analytics with PMA using models and algorithms for the query types Q1 and Q2. The aim is to meet the following desiderata, providing answers to the following questions:Concerning desideratum D1 We study the regression problem—a fundamental inference task that has received tremendous attentions in data mining, data exploration, predictive modeling, machine and statistical learning during the past fifty years. In a regression problem, we are given a set of n observations of \((\mathbf {x}_{i},u_{i})\), where \(u_{i}\)’s are the dependent variables (outputs) and the \(\mathbf {x}_{i}\)’s are the independent variables (inputs); for instance, refer to the 3-dim. input–output points \((\mathbf {x}, u)\) with input \(\mathbf {x} = [x_{1},x_{2}]\) and output u shown in Fig. 2 in our Example 1.

We desire to model the relationship between inputs and outputs. The typical assumption is that there exists an unknown data function g that approximately models the underlying relationship and that the dependent observations are corrupted by random noise. Specifically, we assume that there exists a family of functions \(\mathcal {L}\) such that for some data function \(g \in \mathcal {L}\) it holds true the generative model:where \(\epsilon _{i}\)’s are independent and identically distributed (i.i.d.) random variables drawn from a distribution, e.g., Gaussian.

Let us now move a step further to provide more information about the modeled relationship function g in (1). The derivation of several local linear approximations, as opposed to a single linear approximation over the whole data space, can provide more accurate and significant insights. The key issue to note here is that a global (single) linear approximation of g interpolating among all items of the whole data space \(\mathbb {D}\) leaves, in general, much to be desired: The analysts presented with a single global linear approximation might have an inaccurate view due to missing ‘local’ statistical dependencies within unknown local data subspaces that comprise\(\mathbb {D}\). This will surely lead to prediction errors and approximation inaccuracies when issuing queries Q1 and Q2 to the DMS.

Concerning desiderata D2 and D3 Consider the notion of the mean squared error (MSE) [26] to measure the performance of an estimator. Given the n samples \((\mathbf {x}_{i},u_{i})\) and following the generative model in (1) having mean value \(\mathbb {E}[\epsilon _{i}] = 0\) and variance \(\mathbb {E}[\epsilon _{i}^{2}] = \sigma ^{2}\), our goal is to estimate a data function \(\hat{g}\) that is close to the true, unknown data function g with high probability over the noise terms \(\epsilon _{i}\). We measure the distance between our estimate \(\hat{g}\) and the unknown function g with the MSE:In the general case, the data function g is nonlinear and satisfies some well-defined structural constraints. This has been extensively studied in a variety of contexts [11, 17, 37]. In our desiderata D2 and D3, we focus on the case that the data function g is nonlinear but can be approximated by a piecewise linear function through an unknown number K of unknown pieces (line segments). We then provide the following definition of this type of data function:

The case where K is fixed (given) has received considerable attention in the research community [54]. The special case of piecewise polynomial functions (splines) has been also used in the context of inference including density estimation, histograms, and regression [39].

Let us now denote with \(\mathcal {L}_{K}\) the space of K-piecewise linear functions. While the ground truth may be close to a piecewise linear function, even in certain subspaces, generally we do not assume that it exactly follows a piecewise linear function (yet unknown). In this case, our goal is to recover a piecewise linear function that is competitive with the best piecewise linear approximation to the ground truth.

Formally, let us define the following problem, where we assume that the generative model in (1) representing the data function g is any arbitrary function. We define:to be the error of the best fit K-piecewise linear function to g and let \(g^{*}\) be any K-piecewise linear function that achieves this minimum. Then, the central goal of desiderata D2 and D3 is to discover \(g^{*}\), which achieves a MSE as close to OPT\(_{K}\) as possible, provided that we observe only queries and their answers and not having access to the input–output actual pairs \((\mathbf {x}_{i},u_{i})\).

In our context, however, the analysts explore the data space only by issuing queries over specific data subspaces, thus, observing only the answers of the analytics queries. Specifically, the analysts do not know before issuing a query how the data function behaves within an ad hoc defined data subspace \(\mathbb {D}(\mathbf {x}_{0},\theta )\). When a query Q2 is issued, it is not known whether the data function g behaves with the same linearity throughout the entire \(\mathbb {D}(\mathbf {x}_{0},\theta )\) or not, and within which subspaces, if any, g changes its trend and u and \(\mathbf {x}\) exhibit linear dependencies. Thus, the desiderata D2 and D3 focus on learning the boundaries of these local subspaces within \(\mathbb {D}(\mathbf {x}_{0},\theta )\) and within each local subspace, discovering the linear dependency (segment) between output u and input \(\mathbf {x}\). This would arm analysts and data scientists with much more accurate knowledge on how the data function \(g(\mathbf {x})\) behaves within a given data subspace \(\mathbb {D}(\mathbf {x}_{0},\theta )\). Hence, decisions on further data exploration w.r.t. complex model selection and/or validation can be taken by the analysts.

Concerning desideratum D4 Our motivation comes from the availability of the past issued and executed queries over large-scale datasets. In the words of [34]: ‘As data grows, it may be beneficial to consider faster inferential algorithms, because the increasing statistical strength of the data can compensate for the poor algorithmic quality’, it seems to be advantageous to sacrifice statistical prediction accuracy in order to achieve faster running times because we can then achieve the desired error guarantee faster [35].

Our motivation rests on learning and predicting how the data function g behaves differently in certain data subspaces, within a greater data subspace defined by past issued and executed queries. The state-of-the-art methods leave a lot to be desired in terms of efficiency and scalability. Our key insight and contribution in this direction lies in the development of statistical learning models which can deliver the above functionality for queries Q1 and Q2 in a way that is highly accurate and insensitive to the sizes of the underlying data spaces in number of data points, and thus scalable. The essence of the novel idea we put forward rests on exploiting previously executedqueries and their answers obtained from the DMS/PMA system to train a model and then use that model to:

In Fig. 4, we show the system context within which our rationale and contributions unfold. A DMS serves analytics queries from a large user community. Over the time, all users (data scientists, statisticians, analysts, applications) will have issued a large number of queries (\(\mathcal {Q} = \{\)Q\(_{1}\), Q\(_{2}\), ...,Q\(_{n}\}\)), and the system will have produced responses (e.g., \(y_{1}, y_{2}, \ldots , y_{n}\) for Q1 queries). Our key idea is to inject a novel statistical learning model and novel query processing algorithms in between users and the DMS that monitors queries and responses and learns to associate a query with its response. After training, say after the first \(m < n\) queries \(\mathcal {T} =\{\)Q\(_{1}, \ldots ,\)Q\(_{m}\}\) then, for any new/unseen query Q\(_{t}\) with \(m < t \le n\), i.e., Q\(_{t} \in \mathcal {V} = \mathcal {Q} \setminus \mathcal {T}= \{\)Q\(_{m+1}, \ldots ,\)Q\(_{n}\}\), our model approximates the data function g with an estimator function \(\hat{g}\) through a list \(\mathcal {S}\) of local linear regression coefficients (line segments) that best fits the actual and unknown function g given the query Q\(_{t}\)’s data subspace and predicts its response \(\hat{y}_{t}\)without accessing the DMS. The efficiency and scalability benefits of our approach are evident. Computing the exact answers to queries Q1 and Q2 can be very time-consuming, especially for large data subspaces. So if this model and algorithms can deliver highly accurate answers, query processing times will be dramatically reduced. Scalability is also ensured for two reasons. Firstly, in the data dimension, as query Q1 and Q2 executions (after training) do not involve data accesses, even dramatic increases in DB size do not impact query execution. Secondly, in the query-throughput dimension, avoiding DMS internal resource utilization (that would be required if all Q1 and Q2 queries were executed over the DMS data) saves resources that can be devoted to support larger numbers of queries at any given point in time. Viewed from another angle, our contributions aim to exploit all the work performed by the DMS engine when answering previous queries, in order to facilitate accurate answers to future queries efficiently and scalably.

The research challenge of this rationale is the problem of non-fixed designed segmented regression exploiting only queries and answers by not accessing the underlying data anymore. Specifically, the challenges are:It is worth noting that these cannot be achieved solely by accessing the data, as we need information on which are the users’ ad hoc defined subspaces of interest. It is possible to provide this information a priori for all possible data subspaces of interest to analysts, i.e., consider all possible center points \(\mathbf {x}_{0}\) and all possible radii \(\theta \) values. However, this is clearly impractical—this knowledge is obtained after the analysts have issued queries over the data, thus, reflecting their subspaces of interest and exploration.

The paper is organized as follows: Sect. 2 reports on the related work and provides our major contribution of this work. In Sect. 3, we formulate our problems and provide preliminaries, while Sect. 4 provides our novel statistical learning algorithms for large-scale predictive modeling. Section 5 introduces our proposed query-driven methodologies, corresponding algorithms and analyses, while in Sect. 6, we report on the piecewise linear approximation and query–answer prediction methods. The convergence analysis and the inherent computational complexity are elaborated in Sect. 7, and we provide a comprehensive performance evaluation and comparative assessment of our methodology in Sect. 8. Finally, Sect. 9 summarizes our work and discusses our future research agenda in the direction of query-driven predictive modeling.

Out-with DMS environments, statistical packages like MATLAB and R⁵ support fitting regression functions. However, their algorithms for doing so are inefficient and hardly scalable. Moreover, they lack support for relational and declarative Q1 and Q2 queries. So, if data are already in a DMS, they would need to be moved back and forth between external analytics environments and the DMS, resulting in considerable inconveniences and performance overheads, (if at all possible for big datasets). At any rate, modern DMSs should provide analysts with rich support for PMA.

An increasing number of major database vendors include in their products data mining and machine learning analytic tools. PostgreSQL, MySQL, MADLib (over PostgreSQL) [21] and commercial tools like Oracle Data Miner, IBM Intelligent Miner and Microsoft SQL Server Data Mining provide SQL-like interfaces for analysts to specify regression tasks. Academic efforts include MauveDB [23], which integrates regression models into a DMS, while similarly FunctionDB [50] allows analysts to directly pose regression queries against a DMS. Also, Bismarck [27] integrates and supports in-DMS analytics, while [48] integrates and supports least squares regression models over training datasets defined by arbitrary join queries on database tables. All such works that also support Q1 and Q2 queries can serve as the DMS within Fig. 4. However, in the big data era exact Q1, Q2 computations leave much to be desired in efficiency and scalability, as the system must first execute the selection, establishing the data subspaces per query, and then access all tuples in Q1, Q2.

Apart from the standard multivariate linear regression algorithm, i.e., adopting ordinary least squares (OLS) for function approximation [29], related literature contains more elaborate piecewise regression algorithms, e.g., [10, 12, 18, 28], which can actually detect the nonlinearity of a data function g and provide multiple local linear approximations. Given an ad hoc exploration query over n points in a d-dim. space, the standard OLS regression algorithm has asymptotic computational complexity of \(O(n^{2}d^{5})\) and \(O(nd^{2}+d^{3})\), respectively [32]. Therefore, OLS algorithms suffer from poor scalability and efficiency—especially as n is getting larger, and/or in high-dimensional spaces, as will be quantified in Sect. 8. Such methodologies are suffering such overheads for every query issued, which is highly undesirable. To address this, one may think to perform data-space analyses only once, seeking to derive all local linear regression models for the whole of the data space, and use the derived models for all queries. Indeed, a literature survey reveals several methods like [12, 42], which identify the nonlinearity of data function g and provide multiple local linear approximations. Unfortunately, these methods are very computationally expensive and thus do not scale with the size n of the data points. All these methods execute queries like query Q2, going through a series of stages: partitioning the entire data space into clusters, assigning each data point to one of these clusters, and fitting a linear regression function to each of the clusters. However, data clustering cannot automatically guarantee that the within-cluster nonlinearity of the data function g is captured by a local linear fit. Hence, all these methods are iterative, repeating the above stages until convergence to minimize the residuals estimation error of all approximated local linear regression functions. For instance, the method in [10] clusters and regresses the entire data space against K clusters with a complexity of \(O(K(n^{2}d + nd^{2}))\). Similarly, the incremental adaptive controller method [20] using self-organizing structures requires \(O(n^{2}dT)\) for training purposes. The same holds for the methods [12, 19, 20, 28] that combine iterative clustering and classification for piecewise regression requiring also \(O(n^{2}dT)\). Linear regression methods indicate their high costs when computing exact answers. As all these methods derive regression models over the whole data space, e.g., over trillions of points, the scalability and efficiency desiderata are missed, as Sect. 8 will showcase.

This paper significantly extends our previous work [8] for scalable regression queries in the dimensions of mathematical analyses, fundamental theorems and proofs for vector quantization and piecewise multivariate linear regression (Sects. 5 and 6), theoretical analyses and proofs of the PLR data approximation and prediction error bounds (Sect. 5), analysis of the model convergence, variants of partial and global convergence of PLR data approximation, query answer prediction (Sects. 7 and 7.2), comprehensive sensitivity analysis, and comparative assessment of the proposed methodology (Sect. 8).

Our approach accurately supports predicting the result of mean-value Q1 queries, approximating the underlying data function g based on (multiple) local linear models of regression Q2 queries, and predicting the output data values given unseen inputs by estimating the underlying data function. It does so while achieving high prediction accuracy and goodness of fit, after training without executing Q1 and Q2, thus, without accessing data. This ensures a highly efficient and scalable solution, which is independent of the data sizes, as Sect. 8 will show.

The contribution of this work lies in efficient and scalable models and algorithms to obtain highly accurate results for mean-value and linear regression queries and PLR-based data function approximation. This rests on learning the principal local linear approximations of data function g. Our approach is query-driven, where past issued queries are exploited to partition the queried data space into subspaces in such a way of minimizing the induced regression error and the model fitting/approximation error. In each data subspace, we incrementally approximate the data function g based on a novel PLR approximation methodology only via query–answer pairs. Given a query over a data subspace \(\mathbb {D}(\mathbf {x}_{0},\theta )\), we contribute how to:The research outcome of this work is:

Let \(\mathbf {x}= [x_{1}, \ldots , x_{d}] \in \mathbb {R}^{d}\) denote a multivariate random data input row vector, and \(u \in \mathbb {R}\) a univariate random output variable, with (unknown) joint probability distribution \(P(u,\mathbf {x})\). We notate \(g: \mathbb {R}^{d} \rightarrow \mathbb {R}\) with \(\mathbf {x} \mapsto u\) the unknown underlying data function from input \(\mathbf {x}\) to output \(u = g(\mathbf {x})\).

Consider a scalar \(\theta >0\), hereinafter referred to as radius, and a dataset \(\mathcal {B}\) consisting of n input–output pairs \((\mathbf {x}_{i},u_{i}) \in \mathcal {B}\).

A query \(\mathbf {q} = [\mathbf {x},\theta ]\) defines a data subspace \(\mathbb {D}(\mathbf {x},\theta )\) w.r.t. dataset \(\mathcal {B}\).

Formally, our challenges are:Consider the challenge CH1 and let us adopt the squared prediction error function \((y - f(\mathbf {x},\theta ))^{2}\) for penalizing errors in prediction of aggregate output y given a mean-value query \(\mathbf {q} = [\mathbf {x},\theta ]\). This leads to a criterion for choosing a query-PLR function f, which minimizes the Expected Prediction Error (EPE):for all possible query points \(\mathbf {x} \in \mathbb {R}^{d}\) and query radii \(\theta \in \mathbb {R}\). To calculate the expectation in (5), we approximate EPE by the MSE in (2) over a finite number of query–answer pairs \((y,[\mathbf {x},\theta ])\). Before finding the family of this function that minimizes the EPE in (5), we rest on the law of iterated expectations for the dependent variable y from query point \(\mathbf {x}\) and radius \(\theta \), i.e., \(\mathbb {E}[y] = \mathbb {E}[\mathbb {E}[y|\mathbf {x},\theta ]]\), where y breaks into two pieces, as follows:

For proof of Theorem 1, refer to [32]. According to Theorem 1, the aggregate output y can be decomposed into a conditional expectation function \(\mathbb {E}[y|\mathbf {x},\theta ]\), hereinafter referred to as query regression function, which is explained by \(\mathbf {x}\) and \(\theta \), and a left over (noisy component) which is orthogonal to (i.e., uncorrelated with) any function of \(\mathbf {x}\) and \(\theta \).

In our context, the query regression function is a good candidate for minimizing the EPE in (5) envisaged as a local representative value for answer y over the data subspace \(\mathbb {D}(\mathbf {x},\theta )\). Therefore, the conditional expectation function is the best predictor of answer y given \(\mathbb {D}(\mathbf {x},\theta )\):

For proof of Theorem 2, refer to [32].

The solution to (5) is \(f(\mathbf {x},\theta ) = \mathbb {E}[y|\mathbf {x},\theta ]\), i.e., the conditional expectation of answer y over \(\mathbb {D}(\mathbf {x},\theta )\). However, the number of data points \(n_{\theta }(\mathbf {x})\) in \(\mathbb {D}(\mathbf {x},\theta )\) is finite; thus, such conditional expectation is approximated by averaging all data outputs \(u_{i}\)’s conditioning at \(\mathbf {x}_{i} \in \mathbb {D}(\mathbf {x},\theta )\). Moreover, the answer y of a query \(\mathbf {q}\) refers to the best regression estimator over \(\mathbb {D}(\mathbf {x},\theta )\). Each query center \(\mathbf {x} \in \mathbb {D}(\mathbf {x},\theta )\) and corresponding answer y provides information to locally learn the dependency between output u and input \(\mathbf {x}\), i.e., the data function g. In this context, similar queries w.r.t. \(L_{2}\) distance provide insight for data function g over overlapped data subspaces.

The query-PLR estimate function \(\hat{f}(\mathbf {x},\theta )\) from challenge CH1’s outcome is used for estimating the multiple local line segments (i.e., local linear regression coefficients intercept and slope) of the data-PLR estimate function \(\hat{g}\). This is achieved by a novel statistical learning methodology \(\mathcal {F}\), which learns from a continuous query–answer stream \(\{(\mathbf {q}_{1},y_{1}), \ldots , (\mathbf {q}_{t},y_{t})\}\) through the interactions between the users and the system. We can then formulate our problems are:

We first proceed with a solution of Problem 1 to approximate the query function f through a query-PLR function \(\hat{f}\). Then, we use the approximate \(\hat{f}\) to address Problem 2 to approximate the data function g by a data-PLR function \(\hat{g}\).

Concerning Problem 1 and Theorem 2, we approximate \(f(\mathbf {x},\theta ) = \mathbb {E}[y|\mathbf {x},\theta ]\) that minimizes (5). However, the answer y in (4) involves the average of the outputs \(g(\mathbf {x}_{i}) = u_{i}\), \(i \in [n_{\theta }(\mathbf {x})]\). Hence, \(f(\mathbf {x},\theta )\) is a non-trivial compound function of \(g(\mathbf {x})\) for an arbitrary radius \(\theta \) and \(L_{p}\) norm expressed by definition as:where \(n_{\theta }(\mathbf {x})\) varies depending on the location of the query point \(\mathbf {x}\) in the input data space \(\mathbb {R}^{d}\) and the query radius \(\theta \). Moreover, the nonlinearity of function g over certain subspaces is further propagated to f by definition of the aggregate answer y in (4). Hence, we must identify those data subspaces where data function g behaves almost linearly, which should be reflected in the function f approximation by \(\hat{f}\). This will provide the key insight on approximating both functions f and g through a PLR family functions by learning the unknown finite set of local linear functions. We call those local linear functions as local linear mappings (LLMs) and derive the corresponding: query-space LLMs and data-space LLMs for the query function f and data function g, respectively.

In Problem 1, we approximate the query function \(f(\mathbf {x},\theta )\) with a set of query-space LLMs (or query-LLMs), each of which is constrained to a local region of the query space \(\mathbb {Q}\), defined by similar queries w.r.t. \(L_{2}\) distance. Similar queries are those queries with similar centers \(\mathbf {x}\) and similar radii \(\theta \). Our general idea for those query-space LLMs is the quantization of the query space \(\mathbb {Q}\) into a finite number of query subspaces \(\mathbb {Q}_{k}\) such that the query function f can be linearly approximated by a query-LLM \(f_{k}, k = 1 \ldots , K\), that is the k-th PLR segment. Those query subspaces may be rather large in areas of the query vectorial space \(\mathbb {Q}\) where the query function f indeed behaves approximately linear and must be smaller where this is not the case. The total number K of such query subspaces depends on the desired approximation (goodness of fit) and the query–answer prediction accuracy, and may be limited by the available issued queries since over-fitting might occur.

Fundamentally, we incrementally quantize the query space \(\mathbb {Q}\) over a series of issued queries through quantization vectors, hereinafter referred to as query prototypes, in \(\mathbb {Q}\). Then, we associate each query subspace \(\mathbb {Q}_{k}\) with a query-LLM \(f_{k}\) in the query–answer space, where the query function f behaves approximately linear.

In Problem 2, principally each query subspace \(\mathbb {Q}_{k}\) is associated with a data subspace \(\mathbb {D}_{k}\), i.e., for a query \(\mathbf {q} \in \mathbb {Q}_{k} \subset \mathbb {R}^{d+1}\), its corresponding query point \(\mathbf {x} \in \mathbb {D}_{k} \subset \mathbb {R}^{d}\). This implies that the input vector \(\mathbf {x}\) (of the query \(\mathbf {q}\)) is constrained to be drawn only from the k-th data subspace \(\mathbb {D}_{k}\). Based on that association, we use the query-LLM \(f_{k}\) to estimate the data-LLM \(g_{k}\), i.e., estimate the local intercept and slope of the data function g over the k-th data subspace \(\mathbb {D}_{k}\).

A query-LLM \(f_{k} : \mathbb {Q}_{k} \rightarrow \mathbb {R}\), \(k \in [K]\), approximates the dependency between aggregate answer y and query \(\mathbf {q}\) over the query subspace \(\mathbb {Q}_{k}\) defined by similar queries under \(L_{2}\) distance. For modeling a query-LLM, we adopt the multivariate first-order Taylor expansion of the scalar-valued function \(f(\mathbf {q}) = f(\mathbf {x},\theta ) = f(x_{1}, \ldots , x_{d},\theta )\) for a query \(\mathbf {q}\)near a query vector \(\mathbf {q}_{0} = [\mathbf {x}_{0},\theta _{0}]\), that is:where \(\nabla f(\mathbf {q}_{0})\) is the gradient of query function f at query vector \(\mathbf {q}_{0}\), i.e., the \(1 \times (d+1)\) matrix of partial derivatives \(\frac{\partial f}{\partial x_{i}}, i \in [d]\) and \(\frac{\partial f}{\partial \theta _{k}}\).

As it will be analyzed and elaborated later, the query vector \(\mathbf {q}_{0} = [\mathbf {x}_{0},\theta _{0}]\) and the gradient of query function f at \(\mathbf {q}_{0}\) are not randomly selected. Instead, the proposed methodology \(\mathcal {F}\) attempts to find that query vector \(\mathbf {q}_{0}\) and that gradient vector of query function f at \(\mathbf {q}_{0}\), which satisfies the following optimization properties:As it will be proved later by Theorems 7, 8, and 9, we require a query-LLM \(f_{k}\) to derive from a specific Taylor’s approximation around the local expectation query\(\mathbb {E}[\mathbf {q}] = [\mathbb {E}[\mathbf {x}],\mathbb {E}[\theta ]]\) of queries \(\mathbf {q} \in \mathbb {Q}_{k}\):Specifically, the coefficients of the query-LLM \(f_{k}\) which satisfies the optimization properties OP1, OP2, and OP3, are:Based on these constructs that satisfy OP1, OP2, and OP3, the query-LLM \(f_{k}\) is rewritten as:Up to now, our challenge is for each query-LLM \(f_{k}\) to estimate the parameter \(\alpha _{k} = (y_{k},\mathbf {b}_{k},\mathbf {w}_{k})\) in light of minimizing the EPE as stated in OP1 by the following constrained optimization problem:

However, we need to further optimize \(\alpha _{k}\) to satisfy also the optimization properties OP2 and OP3.

Our statistical learning methodology \(\mathcal {F}\) departs from the optimization problem in (15) to additionally support the optimization properties OP2 and OP3. Our methodology is formally based on a joint optimization problem of optimal quantization and regression. This is achieved by incrementally identifying within-subspaces linearities in the query space and then estimating therein the query-LLM coefficients such that we preserve the optimization properties OP1, OP2, and OP3.

Our algorithm predicts the aggregate output value y given an unseen query \(\mathbf {q} = [\mathbf {x},\theta ]\) over a data subspace \(\mathbb {D}(\mathbf {x},\theta )\). The query function f between query \(\mathbf {q}\) and answer y over the query space \(\mathbb {Q}\) is approximated by K query-LLM functions (hyperplanes) over each query subspace \(\mathbb {Q}_{k}\); see Fig. 8(lower). Given a query \(\mathbf {q}\), we derive the overlapping prototypes set \(\mathcal {W}(\mathbf {q})\). For those query prototypes \(\mathbf {w}_{k} \in \mathcal {W}(\mathbf {q})\), we access the local coefficients \((y_{k}, \mathbf {b}_{k}, \mathbf {w}_{k})\) of query-LLM \(f_{k}\). Then, we pass \(\mathbf {q} = [\mathbf {x},\theta ]\) as input to each function \(f_{k}\) to predict the aggregate output \(\hat{y}\) through a weighted average based on the normalized degrees of overlapping \(\tilde{\delta }(\mathbf {q},\mathbf {w}_{k})\):The aggregate output prediction \(\hat{y}\) derives from the weighted \(\mathcal {W}(\mathbf {q})\)-nearest neighbors regression:withIn the case where \(\mathcal {W}(\mathbf {q}) \equiv \emptyset \), we extrapolate the similarity of the query \(\mathbf {q}\) with the closest query prototype to associate the answer with the estimation \(\hat{y}\) derived only from the query-LLM function \(f_{j}(\mathbf {q},\theta )\) with the query prototype \(\mathbf {w}_{j}\) being closest to the query \(\mathbf {q}\). Through this projection, i.e., \(j = \arg \min _{k \in [K]}||\mathbf {q}-\mathbf {w}_{k}||_{2}\), we get the local slope and intercept of the local mapping of query \(\mathbf {q}\) onto the aggregate answer y.

The prediction of the query answer depends entirely on the query similarity and the \(\mathcal {W}\) neighborhood. The mean-value prediction algorithm is shown in Algorithm 2. Figure 8(lower) shows how accurately the \(K=7\) query-LLM functions (as green covering surfaces/planes over query function f) approximate the linear parts of the query function \(f(\mathbf {x},\theta )\) over a 2D query space \(\mathbb {Q}\) defined by the queries \((x,\theta )\).

The algorithm returns a list of the local data-LLM functions \(g_{k}\) of the underlying data function g over data subspace \(\mathbb {D}(\mathbf {x},\theta )\), given an unseen query \(\mathbf {q} = [\mathbf {x},\theta ]\) (see Example 4). An unexplored data subspace \(\mathbb {D}\) defined by an unseen query might:In Cases 1 and 2, the algorithm returns the derived data-LLMs of the data function g interpolating over the overlapping data subspaces, using the corresponding query-LLMs, as proved in Theorem 3. In Case 3, the best possible linear approximation of the data function g is returned through the extrapolation of the data subspace \(\mathbb {D}_{k}\) whose query prototype \(\mathbf {w}_{k}\) is closest to the query \(\mathbf {q}\). For Cases 1 and 2, we exploit the neighborhood \(\mathcal {W}(\mathbf {q})\) of the query \(\mathbf {q} = [\mathbf {x},\theta ]\). For Case 3, we select the data-LLM function, which corresponds to the query-LLM function with the closest query prototype \(\mathbf {w}_{j}\) to query \(\mathbf {q}\) since, in this case, \(\mathcal {W}(\mathbf {q}) \equiv \emptyset \).

The PLR approximation of the data function \(g(\mathbf {x})\) over the data subspace \(\mathbb {D}(\mathbf {x},\theta )\) involves both the radius \(\theta \) and the query center \(\mathbf {x}\) using their similarity with radius \(\theta _{k}\) and the point \(\mathbf {x}_{k}\), respectively, from the \(\mathcal {W}(\mathbf {q})\). For the Cases 1 and 2, the set of the data-LLMs for a PLR approximation of data function \(g(\mathbf {x})\) is provided directly from those query-LLMs \(f_{k}\), whose query prototype \(\mathbf {w}_{k} \in \mathcal {W}(\mathbf {q})\). That is, for \(\mathbf {x} \in \mathbb {D}_{k}(\mathbf {x}_{k},\theta _{k})\), we obtain:\(\forall \mathbf {w}_{k} \in \mathcal {W}(\mathbf {q})\), where the u intercept in \(\mathbb {D}_{k}\) is: \(y_{k} -\mathbf {b}_{X,k}\mathbf {x}_{k}^{\top }\) and the u slope in \(\mathbb {D}_{k}\) is: \(\mathbf {b}_{X,k}\).

For the Case 3, the PLR approximation of the data function \(g(\mathbf {x})\) derives by extrapolating the linearity trend of \(u = g(\mathbf {x}) = f_{j}(\mathbf {x},\theta _{j}): j = \arg \min _{k} ||\mathbf {q} - \mathbf {w}_{k}||_{2}\) over the data subspace, with u intercept: \(y_{j} -\mathbf {b}_{X,j}\mathbf {x}_{j}^{\top }\) and the u slope: \(\mathbf {b}_{X,j}\).

The PLR approximation of the data function is shown in Algorithm 3, which returns the set of the data-LLM functions \(\mathcal {S}\) defined over the data subspace \(\mathbb {D}(\mathbf {x},\theta )\) for a given unseen query \(\mathbf {q} = [\mathbf {x},\theta ]\). Note that depending on the query radius \(\theta \) and the overlapping neighborhood set \(\mathcal {W}(\mathbf {q})\), we obtain: \(1 \le |\mathcal {S}| \le K\), where \(| \mathcal {S}|\) is the cardinality of the set \(\mathcal {S}\).

In this section we show that our stochastic joint optimization algorithm is asymptotically stable. Concerning the objective function \(\mathcal {J}\) in (21), the query prototypes \(\mathbf {w}_{k} = [\mathbf {x}_{k},\theta _{k}]\) converge to the centroids (mean vectors) of the query subspaces \(\mathbb {Q}_{k}\). This convergence reflects the partition capability of our proposed AVQ algorithm into the prototypes of the query subspaces. The query subspaces naturally represent the (hyper)spheres of the data subspaces that the analysts are interested in accessed by their query centers \(\mathbf {x}_{k}\) and radii \(\theta _{k}\), \(\forall k\).

Concerning the objective function \(\mathcal {H}\) in (22), the approximation coefficients slope and intercept in Theorem 3 converge, too. This convergence refers to the linear regression coefficients that would have been derived should we were able to a fit linear regression function over each data subspace \(\mathbb {D}_{k}\), given that we had access to the data.

Theorem 7 refers to the convergence of a query prototype \(\mathbf {w}_{k}\) to the local expectation query \(\mathbb {E}[\mathbf {q}|\mathbb {Q}_{k}] = \mathbb {E}[\mathbf {q}|v(\mathbf {q}) = k]\) given our AVQ algorithm.

We provide two convergence theorems for the coefficients \(y_{k}\) and \(\mathbf {b}_{k}\) of the query-LLM \(f_{k}\). Firstly, we focus on the aggregate answer prediction \(y = y_{k} + \mathbf {b}_{k}(\mathbf {q}-\mathbf {w}_{k})^{\top }\). Given that the query prototype \(\mathbf {w}_{k}\) has converged, i.e., \(\mathbf {w}_{k} = \mathbb {E}[\mathbf {q}|\mathbb {Q}_{k}]\) from Theorem 7, then the expected aggregate value \(\mathbb {E}[y|\mathbb {Q}_{k}]\) converges to the \(y_{k}\) coefficient of the query-LLM \(f_{k}\). This also reflects our assignments of the statistical mapping \(\mathcal {F}\) of the local expectation query \(\mathbf {w}_{k}\) to the mean of the query-LLM \(f_{k}\), i.e., \(f_{k}(\mathbb {E}[\mathbf {x}_{k}|\mathbb {Q}_{k}],\mathbb {E}[\theta _{k}|\mathbb {Q}_{k}]) = \mathbb {E}[y|\mathbb {Q}_{k}]\). This refers to the local associative convergence of coefficient \(y_{k}\) given a query \(\mathbf {q} \in \mathbb {Q}_{k}\). In other words, the convergence of the query subspace enforces also convergence in the output domain.

Finally, we provide a convergence theorem for \(\mathbf {b}_{k}\) as the slope of the linear regression of \(\mathbf {q}-\mathbf {w}_{k}\) onto \(y-y_{k}\).

The entire statistical learning model runs in two phases: the training phase and the prediction phase. In the training phase, the query-LLM prototypes \((\mathbf {w}_{k},\mathbf {b}_{k}, y_{k})\), \(k \in [K]\), are updated upon the observation of a query–answer pair \((\mathbf {q},y)\) until their convergence w.r.t. the global stopping criterion in (24). In the prediction phase, the model proceeds with the mean-value prediction of the aggregate answer \(\hat{y}\), the PLR data approximation of the data function g and the output data value prediction \(\hat{u}\), without execution of any incoming query after convergence at \(t^{*}\). The major requirement for the model to transit from the training to the prediction phase is the triggering of the global stopping criterion at \(t^{*}\) w.r.t. a fixed \(\gamma >0\) convergence threshold.

Let us now provide an insight of this global criterion. The model convergence means that on average for all the trained query-LLM prototypes their improvement w.r.t. a new incoming query–answer pair is not as much significant as it was at the early stage of the training phase. The rate of updating such prototypes, which is reflected by the difference vector norms of \((\mathbf {w}_{k,t},\mathbf {b}_{k,t}, y_{k,t})\) and \((\mathbf {w}_{k,t-1},\mathbf {b}_{k,t-1}, y_{k,t-1})\) at observation t and \(t-1\), respectively, is decreasing as the number of query–answer pairs increases, i.e., \(t \rightarrow \infty \); refer also to convergence analysis in Sect. 7.

In a real world setting, however, we cannot obtain an infinite number of training pairs to ensure convergence. Instead, we are sequentially provided a finite number of training pairs \((\mathbf {q}_{t},y_{t})\) from a finite training set \(\mathcal {T}\). We obtain model convergence given that there are enough pairs in the set \(\mathcal {T}\) such that the criterion in (24) is satisfied. More interestingly, we have observed that some of the query-LLM prototypes, say \(L < K\) converge with less training query–answer pairs than all provides pairs \(|\mathcal {T}|\). Specifically, for those L prototypes, which represent certain data subspaces \(\mathbb {D}_{\ell }\) and query subspaces \(\mathbb {Q}_{\ell }\), \(\ell =1, \ldots , L\), it holds true that the convergence criterion \(\max \{\varGamma _{\ell }^{\mathcal {J}},\varGamma _{\ell }^{\mathcal {H}}\}_{t} \le \gamma \) for \(t < t^{*}\), where \(t^{*}\) corresponds to the last observed training pair where the entire model has globally converged, given a fixed \(\gamma \) convergence threshold. In this case, we introduce the concept of partial convergence if there is at least a subset of query-LLM prototypes, which have already converged w.r.t. \(\gamma \) at an earlier stage than the entire model (entire set of parameters). Interestingly, those \(\ell \) query-LLM prototypes transit from their training phase to the prediction phase. The partial convergence on those data subspaces is due to the fact that there were relatively more queries issued to those data subspaces compared to some other data subspaces up to the t-th observation with \(t < t^{*}\). Moreover, by construction of our model, only a relatively small subset of query-LLM prototypes are required for mean-value prediction and PLR data approximations (refer to the overlapping set \(\mathcal {W}\) in Sect. 6). Hence, based on the flexibility of the partial convergence, we can proceed with prediction and data approximation to certain incoming queries issued onto those data subspaces, where their corresponding query-LLM prototypes have partially converged, while the entire model is still on a training phase, i.e., it has not yet globally converged.

The advantage of this methodology is that we deliver predicted answers to the analysts’ queries without imposing the execution delay for those queries. Evidently, we obtain the flexibility to either proceed with the query execution after the prediction for refining more the converged data subspace or not. In both options, the analysts ‘do not need to wait’ for the system to execute firstly the query and then being delivered the answers. This motivated us to introduce a progressive predictive analytics or intermediate phase, where some parts of the model can, after their local convergence, provide predicted answers to the analysts without waiting for the entire model to converge.

The research challenge in supporting the progressive analytics phase is when some of the involved query-LLM parameters are not yet converged with some other query-LLM parameter, which have locally converged. Specifically, assume that at the t-th observation (with \(t < t^{*}\)) there are L query-LLM prototypes that have converged and the query \(\mathbf {q}_{t} = (\mathbf {x}_{t},\theta _{t})\) is arriving to the system (note: \(L < K\) at observation t). The overlapping set \(\mathcal {W}(\mathbf {q}_{t})\) consists of \(\ell \le L\) query prototypes \(\mathbf {w}_{i}\), \(i = 1, \ldots , \ell \), which have converged and \(\kappa < K-L\) query prototypes \(\mathbf {w}_{j}\), \(j = 1, \ldots , \kappa \), which have not yet converged, i.e., \(\mathcal {W}(\mathbf {q}_{t}) = \{\mathbf {w}_{i}\} \cup \{\mathbf {w}_{j}\}\). In this case, the mean-value prediction and the PLR data approximation over the data subspace \(\mathbb {D}(\mathbf {x}_{t},\theta _{t})\) involves \(\ell +\kappa \) prototypes such that:with \(\ell = |\mathcal {C}(\mathbf {q}_{t})|\) and \(\kappa = |\mathcal {U}(\mathbf {q}_{t})|\). We adopt a convergence voting/consensus scheme for supporting this intermediate phase between training and prediction phase in light of delivering either predicted answers or actual answers to the analysts.Algorithm 4 shows the partial convergence methodology of the model transition from the training phase to the intermediate phase, and then to the prediction phase.

Our progressive predictive analytics methodology allows the combined mode of operation, whereby the training and prediction phases overlap. In this combined mode, the model runs its training and prediction algorithms based on the consensual threshold r. Let us define \(t_{\top }\) the first observation at which the consensual ratio \(\frac{\ell }{\ell + \kappa }\) exceeds threshold r, i.e.,For any observation \(t < t_{\top }\) the model is in a single training phase, while for any observation \(t_{\top } \le t < t^{*}\) the model is in the intermediate phase, i.e., prediction and/or training phase depending on the consensual ratio at the t-th observation (Cases A and/or B). At \(t > t^{*}\) the model transits to the single prediction phase. Figure 9 illustrates the activation of the training, intermediate and prediction phases over the observation time axis and the landmarks \(t_{\top }\) and \(t^{*}\). The landmark \(t_{\top }\) denotes the minimum number of training pairs the model requires to deliver to the analysts predicted and/or actual answers w.r.t. Cases A and B, while only predicted answers are delivered after \(t^{*}\) training pairs.

In this section we report on the computational complexity of our model during the training and prediction phases. In the global convergence mode, the model ‘waits’ for the triggering of the criterion in (24) to transit from the training to the prediction phase. Under SGD over the objective minimization functions \(\mathcal {J}\) and \(\mathcal {H}\), with the hyperbolic learning schedule in (7), our model requires \(O(1/\gamma )\) [15] number of training pairs to reach the convergence threshold \(\gamma \). This means that the residual difference between the objective function value \(\mathcal {J}^{t^{*}}\) after \(t^{*}\) pairs and the optimal value \(\mathcal {J}^{*}\), i.e., with the optimal query-LLM parameters, asymptotically decreases exponentially, also known as linear convergence [25]. In this mode, there is a clear separation between the training and prediction phases, while the upper bound of the expected excess difference \(\mathbb {E}[\mathcal {J}^{t}-\mathcal {J}^{*}]\) after t training pairs is \(O\left( \sqrt{\frac{\log t}{t}}\right) \) [52], given a hyperbolic learning schedule in (7).

In the prediction phase, which is the operational mode of our model, given a mean-value query Q1 and a linear regression query Q2, we require O(dK) to calculate the neighborhood \(\mathcal {W}\) set and deliver the query-LLM functions, respectively, i.e., independent on the data size, thus, achieving scalability. We also require O(dK) space to store the query prototypes and the query-LLM coefficients. The derivation of the data-LLMs is then O(1) given than we have identified the query-LLMs for a given linear regression query.

The proposed methodology deals with two major statistical learning components: prediction of the aggregate answer and data output, and data function approximation over data subspaces. For evaluating the performance of our model in light of these components, we should assess the model predictability and goodness of fit, respectively.

Predictability refers to the capability of a model to predict an output given an unseen input, i.e., such input–output pair is not provided during the model’s training phase. Measures of prediction focus on the differences between values predicted and values actually observed. Goodness of fit describes how well a model fits a set of observations, which were provided in the model’s training phase. It provides an understating on how well the selected independent variables (input) explain the variability in the dependent (output) variable. Measures of goodness of fit summarize the discrepancy between actual/observed values during training and the values approximated under the model in question.

We compare our statistical methodology against its ground truth counterparts: the multivariate linear regression model over data subspaces, hereafter referred to as REG, and the piecewise linear model (PLR) over data subspaces, both of which have full access to the data. Note that the PLR data approximation is the optimal multiple linear modeling over data subspaces we can obtain because it is constructed by accessing the data. Hence, we demonstrate how effectively our data-LLMs approximate the ground truth data function g and the optimal PLR data approximation. Specifically, we compare against the REG model using DMS PostgreSQL and the MATLAB and the PLR model using the ARESLab (MATLAB) toolbox⁷ for building PLR models based on the multivariate adaptive regression splines method in [44]. We show that our model is scalable and efficient and as (or even more than) accurate than the REG model, w.r.t. predictability and goodness of fit, and close to the accuracy obtained by the optimal PLR model. Our model is dramatically more scalable and efficient as, unlike REG and PLR models, it does not need access to data, yielding up to six orders of magnitude faster query execution.

We train our model with the training set \(\mathcal {T}\) and then evaluate and compare it with the ground truths REG (ProstgreSQL and MATLAB) and PLR (MATLAB) with the testing set \(\mathcal {V}\) examining the statistical significance in accuracy with respect to paired-sample two-tailed Student t test with significance level 0.05. Note, the \(\mathcal {T}\) and \(\mathcal {V}\) sets contain explicitly different queries as discussed in Sect. 8.2.2. The granularity of quantization for our model is tuned by the percentage coefficient \(a \in [0.05, 1]\), involved in vigilance parameter \(\rho = a(d^{1/2}+1)\) (see Sect. 5 and Remark 7). Specifically, a value of quantization coefficient \(a=1\) corresponds to the generation of only one prototype, i.e., \(K=1\) (that is, coarse quantization), while any value of coefficient \(a <1\) (that is, fine grained quantization) corresponds to a variable number of prototypes \(K>1\) depending on the underlying (unknown) data distribution. The default value for the quantization percentage coefficient is \(a=0.25\) in our experiments. The model is adapting its parameters/prototypes in a stochastic manner every time a new query–answer pair \((\mathbf {q},y) \in \mathcal {T}\) is present. We set model convergence threshold \(\gamma = 0.01\) in Algorithm 1 to transit from the training phase to the prediction phase. Moreover, the hyperbolic learning rate schedule for the t-th training pair is: \(\eta _{t} = (1+t)^{-1}\) [14] for the stochastic training of the prototypes as query–answer pairs \((\mathbf {q},y)\) are retrieved (one at a time) from the training set \(\mathcal {T}\). Notably, to fairly compare against the optimal PLR data approximation, we set its maximum numbers of the automatically discovered linear models (in the forward building phase of the PLR algorithm) equal to K and the generalized cross-validation penalty per PLR knot to 3 as suggested in [44]. The proposed statistical methodology requires training and prediction phases. We also introduce the intermediate phase in Sect. 7.2, which is controlled by the consensual threshold \(r = 0.7\) of the partially converged query prototypes involved in queries. That is the model starts providing predictions in the intermediate phase when 70% of the query prototypes have converged. We examine firstly the global convergence of the training phase of our model and, then, study the variant of partial convergence w.r.t. the landmarks \(t_{\top }\) and \(t^{*}\) and the impact on the required number of training pairs and accuracy. Table 1 shows the experimental parameters and their range/default values.

Figure 13 examines the termination criterion of the training Algorithm 1 \(\varGamma = \max (\varGamma ^{\mathcal {J}}, \varGamma ^{\mathcal {H}})\) against the number of training pairs \((\mathbf {q},y)\) in training set \(\mathcal {T}\) for \(d \in \{2,5\}\) over R1 and R2 datasets with quantization coefficient \(a = 0.25\); similar results are obtained from R3 dataset. The training phase terminates at the first instance \(t^{*}\) when \(\varGamma \le \gamma \), which is obtained for \(|\mathcal {T}| \approx 5300\) training pairs. The total average training time, which includes both Q1 execution time and model updates time, is (0.41, 0.36, 2.38) h for R1, R3, and R2 datasets, respectively. This should not be perceived as overhead of our approach, as 99.62% of the training time is devoted to executing the queries over the DMS/statistical system, which we cannot avoid that anyway even in the typical case as shown in Fig. 4. Any traditional approach would thus also pay 99.62% of this cost. This only affects how early our approach switches to using the trained model versus executing the queries against the system. Our experiments show that excellent quality results can be produced using a reasonable number of past executed queries for training purposes. Obviously, this can be tuned by setting different model convergence threshold \(\gamma \) values. We set \(\gamma = 0.01\), where \(\varGamma \) is (stochastically) trapped around 0.0046, with deviation 0.0023 in R1 and 0.0012 in R3. In R2, the \(\varGamma \) is strictly less than \(\gamma \) for \(|\mathcal {T}| > 5300\).

Figure 14 shows the relation between the percentage of the number of the training pairs \(|\mathcal {T}|\)% used for a specific percentage of query prototypes to partially converge given the intermediate phase for \(d \in \{2,5\}\) over R1 dataset with quantization coefficient \(a = 0.25\). Specifically, we observe that with only 35% of the training pairs, i.e., with almost 1800 query–answer pairs (landmark \(t_{\top } \approx 1800\)), we obtain a model convergence of the 70–80% of the query-LLM prototypes. This indicates that the entire model has partially converged to a great portion w.r.t. number of query-LLM prototypes requiring a relatively small number of training pairs. In this case, the intermediate phase is deemed of high importance for delivering predictions to the analysts while the model is still being in a ‘quasi-training’ mode. The model converges with a high rate as more training pairs from the training set \(\mathcal {T}\) are observed after the convergence of the 70% of the query-LLM prototypes. This suggests to set the consensual threshold for the intermediate phase \(r = 0.7\). However, during this phase, the delivered predictions to the analysts have to be assessed w.r.t. prediction accuracy, as will be discussed in Sect. 8.4.

Figure 15(upper) shows the evolution of the joint objective functions \(\mathcal {J}\) and \(\mathcal {H}\) and Fig. 15(lower) shows the evolution of the individual norm difference of each query prototype from the current average, i.e., the individual convergence criterion, against the percentage of training pairs. We observe that after 37% of training pairs of the training set \(\mathcal {T}\), all the prototypes start to transit from their training phase to the prediction phase, while minimizing their deviations from the average convergence trend of the model. This indicates the flexibility of our model in being in the prediction phase thus proceeding with prediction for those data subspaces where the corresponding query prototypes have already converged and, in the same time, being in the training phase for those query prototypes which have not yet converged, thus, keeping in a learning mode. After the global convergence, i.e., when the consensual ratio reaches the unity, the model transits entirely in the prediction phase thus achieving significantly fast query execution without accessing the data. This signifies the scalability of our query-driven approach.

Figures 16 and 18(upper) show the RMSE e of the predicted answer y (A1 metric) against the resolution of quantization (coefficient) a over R1, R2, and R3 datasets, respectively, for Q1 queries using the generated testing set \(\mathcal {V}\) (see Sect. 8.2.2). For different quantization coefficient a values, our model identifies subspaces where the function \(f(\mathbf {x},\theta )\) behaves almost linearly, thus, the query-LLM functions approximate such regions with high accuracy. Interestingly, by quantizing the query space by adopting a small coefficient a value, i.e., fine-grained resolution of the query space, then high accuracy is achieved (low RMSE e values) with obvious nonlinear dependencies among dimensions. This is due to the fact that with small coefficient a values, we focus on very specific query subspaces where linear approximations suffice to approximate the query function f. This expects to result in a high number of prototypes K in order to build many query-LLM functions to capture all the possible nonlinearities of the query function f as will be discussed below.

Figure 23(lower) shows the number of query prototypes formated during the query space quantization. Indicatively, we obtain \(K = 450\) prototypes for quantization coefficient \(a=0.25\). This indicates that only 450 prototypes are required to accurately predict the aggregate answer y for data dimension \(d=5\), that is, it is required 450 query-LLM functions to capture the curvature of the query function f over the query subspaces. As the quantization coefficient \(a \rightarrow 1\), then we quantize the query function f into fewer query-LLMs approximations, thus, yielding higher RMSE values as expected due to coarse approximation of the function f.

Figures 17 and 18(lower) show the robustness of the our model w.r.t. predictability with various testing file sizes \(|\mathcal {V}|\) for R1, R2, and R3 datasets, respectively. Once the LLM model has converged, it provides a low and constant prediction error in terms of RMSE for different data dimensions d, indicating the robustness of the training and convergence phase of the proposed model. This means that the model after transiting into the prediction phase can accurately predict the aggregate answer y via the identified and optimized query-LLM functions thus no query processing and data access is needed at that phase.

To assess the efficiency and scalability for the mean-value prediction query Q1, Fig. 24(upper) shows in log scale the average Q1 execution time over the dataset R2 for LLM (with quantization coefficient \(a=0.25\)) corresponding to \(K=92\) and \(K=450\) query prototypes for dimensions \(d \in {2,5}\), respectively. Our method requires just 0.18 ms per query over massive data spaces in its prediction phase, offering up to five orders of magnitude speedup (0.18 ms vs up to \(10^{5}\) ms/query). This is expected, since the LLM-based model predicts the Q1’s outputs and does not execute the query over the data during prediction achieving high prediction accuracy.

We now examine the impact of the model partial convergence on the predictability, i.e., when the model is in the intermediate phase between the training and the prediction phases. Figure 19 (upper) shows the partial RMSE \(\tilde{e}\) of the predicted aggregate answer y (A1 metric) during the intermediate phase of the model and the achieved RMSE e during the prediction phase against the percentage of training pairs for consensual threshold \(r = 0.7\) over dimension \(d \in \{2, 5\}\) for the dataset R1. Similar results are obtained from R2 and R3 datasets. Specifically, the partial RMSE \(\tilde{e}\) is obtained only from the converged query prototypes during the intermediate phase as described in Case A.I in Sect. 7.2 for \(r=0.7\). That is, from those query prototypes whose any additional training pair \((\mathbf {q},y)\) does not significantly move the query prototypes in the query space. We observe the predictability capability of our model w.r.t. number of training pairs such that with almost 35% for \(d=2\) (and 45% for \(d=5\)) of the observed training pairs, the model achieves a RMSE value close to the RMSE value obtained in the fully prediction phase, i.e., after observing 100% of the observed training pairs from \(\mathcal {T}\). This indicates the flexibility of our model to proceed with accurate predictions even being in the intermediate phase, where some of the query prototypes are still in a training mode until the model entirely converges.

More interestingly, Fig. 19(lower) shows the efficiency of our model in achieving high prediction accuracy even during the intermediate phase describe above. The model being in the intermediate phase can provide RMSE values close to that at the end of the training phase by having 70% of the prototypes converged after observing 37% of the training pairs from the training set \(\mathcal {T}\). This demonstrates the fast convergence of the model and its immediate application for delivering predictions to the analysts and real-time predictive analytics applications while not yet being fully converged.

We evaluate the Q2 queries by using our query-/data-LLMs model against the REG and PLR models and show the statistical significance of the derived accuracy metrics. The explanation over the linear/nonlinear behaviors of data function g is interpreted by the variance explanation and model fitting metrics fraction of the variance unexplained FVU and coefficient of determination CoD against the quantization resolution coefficient a and the model prototypes K. Figures 20 and 21(upper) show the sum of squared residuals SSR between the actual answers and the predicted answers for the data-LLMs and REG model with \(d \in \{2,5, 6\}\) over the datasets R1, R2, and R3 with \(p < 0.05\).

Figures 22(upper) and 21(lower) show that the fraction of the variance unexplained of the function approximation FVU < 1 for our model, while for the REG model we obtain FVU > 1, \(p < 0.05\). This indicates the capability of our model to capture the nonlinearities of the underlying data function g over all the data subspaces, compared with the REG model provided in the modern DMS. Specifically, as the query space quantization is getting coarse, that is a low resolution with \(a \rightarrow 1\), our model approaches the fraction of unexplained variances FVU of the model fitting as that of the REG model, i.e., resulting to a few number of data-LLM functions. This is because, we enforce our model to generate fewer data-LLM functions, thus, cannot effectively capture the nonlinearities of the data function g over all possible data subspaces. Indicatively, we obtain only one data-LLM when \(a = 1\), i.e., only a global linear model approximates the data function g. As expected, the optimal PLR model achieves the lowest FVU by capturing the nonlinearity of the data function g with multiple linear basis functions. For quantization coefficient \(a < 1\), we achieve a low FVU and our model captures effectively the nonlinearity of data function g by autonomously deriving multiple data-LLMs, which is very close to the actual PLR approximation for quantization coefficient \(a < 0.1\) with \(p<0.05\). As the Rosenbrock function g is nonlinear, our model attempts to analyze it into data-LLMs and provide a fine-grained explanation on the behavior of the data function g. This cannot be achieved by the in-DMS model REG, since the Rosenbrock function cannot be expressed by a ‘global’ line within the entire data space \(\mathbb {D}(\mathbf {x},\theta )\). The PLR model shows statistically superior FVU performance (\(p < 0.05\)), while being dramatically inefficient compared to our model, as shown in Fig. 24(lower). On the other hand, our model conditionally quantizes the data function g into data-LLMs, thus, providing the list \(\mathcal {S}\) of local lines that significantly better explain the data subspace, without accessing the data and then providing high accurate model fitting.

In Fig. 22(lower) and in Fig. 21(lower) the data function g in R1 and R3 datasets does not behave linearly in all the random data subspaces. This is evidenced by the FVU metric of the REG model, which is relatively close to/over 1 for \(d=2\), \(d=5\), and \(d=6\) with \(p<0.05\). This information is unknown a priori to analysts, hence the results using the REG model would be fraught with approximation errors indicating ‘bad’ model fitting. It is worth noting that, the average number of data-LLM functions that are returned to the analysts for all the issued testing queries in the testing set \(\mathcal {V}\) is \(|\mathcal {S}| = 4.62\) per query with variance 3.88. This denotes the nonlinearity behavior of data function g and the fine-grained and accurate explanation of the function g within a specific data subspace \(\mathbb {D}(\mathbf {x},\theta )\) per query \(\mathbf {q} = [\mathbf {x},\theta ]\). Here, the PLR model achieves the lowest FVU value, i.e., best model fitting as expected (\(p<0.05\)), but note that this is also achieved by our data-LLM functions with a quantization coefficient \(a < 0.1\).

Figure 23(upper) shows the coefficient of determination CoD \(R^{2}\) for the LLM, REG, and PLR models over the R1 dataset (similar results are obtained for datasets R2 and R3) having a significance level of 5%. A positive value of \(R^{2}\) close to 1 depicts that a linear approximation is a good fit for the unknown data function g. While, a value of \(R^{2}\) close to 0, and especially, a negative value of \(R^{2}\) indicates a significantly bad fit signaling inaccuracies in function approximation. In our case, with \(K>60\) query prototypes, our model achieves high and positive \(R^{2}\) indicating that our model better explains the random queried data subspaces \(\mathbb {D}(\mathbf {x},\theta )\) compared with the obtained explanation of the current in-DMS REG model over exactly the same data subspaces and \(p<0.05\). The REG model achieves low \(R^{2}\) values, including negative ones, thus it is inappropriate for predictions and function approximation. This indicates that the underlying data function g highly exhibits nonlinearities, which are not known to the analysts a-priori. By adopting our model, the analysts progressively learn the underlying data function g and also via the derived data-LLM functions capture the hidden nonlinearities over the queried data subspaces. Such subspaces could never be known to the analysts unless exhaustive data access and exploration takes place. This capability is only provided by our model. Notably, as the quantization coefficient \(a \rightarrow 1\), our model increases significantly the coefficient of variation \(R^{2}\) value indicating a better capture of the specificities of the underlying data function g, thus, providing more accurate linear models. Again, the data-access exhaustive PLR model achieves the highest CoD values, however at the cost of high insufficiency; see Fig. 24(lower). Regardless, note that our model can catch the PLR’s CoD value by simply increasing K, i.e., the granularity of query space quantization.

Figures 24(lower) and 26(lower) show the Q2 execution time over the dataset R2 and R3, respectively, for data-LLM (\(a=0.25\), i.e., \(K=(92,450)\) for \(d=(2,5)\)) through Algorithm 3, the REG model from PostgreSQL (\(d=2\)) (REG-DBMS), the REG model from MATLAB (\(d=5\)) (REG-MATLAB), and the optimal PLR against dataset size. The derived results are statistically significant with \(p<0.05\). Our model is highly scalable (note the flat curves) in both datasets and highly efficient, achieving 0.56 ms/query and 0.78 ms/query (even for massive datasets)–up to six orders of magnitude better than the REG and PLR models for R2 and R3 datasets, respectively. The full picture is then that our model provides ultimate scalability by being independent of the size of the dataset) and many orders of magnitude higher efficiency, while it ensures great goodness of fit (CoD,FVU), similar to that of PLR.

The PLR model with data sampling techniques could also be considered as an effective efficiency-accuracy trade-off. Figure 24, however, shows the efficiency limitations of such an approach. The PLR model, even over a very small random sample of size \(10^6\) = 0.01% of the \(10^{10}\) dataset, is shown to be \(>3\) orders of magnitude less efficient than our model. Also, recall that PLR here is implemented over MATLAB, with all data in memory, hiding the performance costs of a full in-DBMS implementation for the selection operator (computing the data subspace); the sampling of the data space; and the PLR algorithm (whose performance is shown in Fig. 24). All of this is in stark contrast to the O(1) cost of our model. Finally, note that, to our knowledge, PLR is not currently implemented within DMSs, regardless of its cost.

We compare our data-LLM functions against the in-RDBMS REG and PLR models for providing accurate data output predictions w.r.t. the A2 metric, i.e., the data prediction performance with statistical level of significance 5%. We use our data-LLM functions for providing data output u predictions over unseen data subspaces \(\mathbb {D}(\mathbf {x},\theta )\) using (31) and (29) for prediction. Figures 25 and 26(upper) show the RMSE v for the LLM, REG, and PLR models over the R1, R2, and R3 datasets against the testing set size \(|\mathcal {V}|\).

The LLM model can successfully predict the data output u by being statistically robust in terms of number of testing pairs \(|\mathcal {V}|\) (\(p<0.05\)) and assume comparable or, even, lower prediction error than the REG model. This denotes that our model, by fusing different data-LLM functions which better capture the characteristics of the underlying data function g, provides better data output u prediction than a ‘global’ REG model over random queried data subspaces \(\mathbb {D}\). Evidently, the PLR model achieves the lowest RMSE value by actually accessing the data and captures the actual nonlinearity of the data function g through linear models. However, this is achieved with relatively high computational complexity, higher than the REG model including polynomially data-access process [44]. Note, the data output prediction times for the LLM, REG, and PLR models in this experiment are the same presented in Fig. 24: The LLM model executes our Algorithm 2 by replacing \(\theta =\theta _{k}\) in (30), \(\forall \mathbf {w}_{k} \in \mathcal {W}(\mathbf {q})\), the REG model creates the linear approximation over the data space \(\mathbb {D}\), and the PLR adaptively finds the best linear models for data fitting in each prediction request.

Overall, the proposed LLM model through the training, intermediate and prediction phases achieves statistically significant scalability and accuracy performance compared with the in-RDBMS REG model and the data-access intensive PLR model (\(p<0.05\)). The scalability of the proposed model in the predictive analytics era is achieved by predicting the query answers and delivering to analysts the statistical behavior of the underlying data function without accessing the raw data and without processing/executing the analytics queries, as opposed to the data-driven REG and PLR models in the literature,

In this section we examine the impact of the query radius \(\theta \) on the predictive and scalability performance of our query-driven approach. Consider that the query function f is approximated by some function \(\hat{f}\). Then, the expected prediction error (EPE) in (5) for a random query \(\mathbf {q}\) with actual aggregate answer y is decomposed as:The first term is the squared bias, i.e., the difference between the true function f and the expected value of the estimate \(\mathbb {E}[\hat{f}]\), where the expectation averages the randomness in the dataset. This term will most likely increase with radius \(\theta \), which implies an increase in the number of input data points \(n_{\theta }(\mathbf {x})\) from the dataset \(\mathcal {B}\). The second term is a variance that decreases as the query radius \(\theta \) increases. The third term is the irreducible error, i.e., the noise in the true relationship that cannot fundamentally be reduced by any model with variance \(\sigma ^{2} = \mathrm{Var}(\epsilon )\). The \(\theta \) value controls the influence that each neighbor query point has on the aggregate answer prediction. As radius \(\theta \) varies there is a bias-variance trade-off. An increase in radius \(\theta \) results in smoother aggregate answer prediction but increasing the bias. On the other hand, the variance goes to zero since, for instance, with a high radius \(\theta \), the prediction \(\hat{f}(\mathbf {x},\theta ) \approx \mathbb {E}[y]\), i.e., unconditioned to the query \(\mathbf {q}\). Imagine queries whose radii include all data points \(\mathbf {x}_{i}\) in the entire data space. In that case, we obtain a constant aggregate answer for each issued query, i.e., the aggregate answer \(y = 1/n\sum _{i=1}^{n}u_{i}\), which is the average of all data outputs \(u_{i}\) thus, no need to predict the aggregate answer y. By selecting a radius \(\theta \) such that \(n_{\theta }(\mathbf {x}) \approx n\), then the aggregate answer prediction is a relatively smooth function of query \(\mathbf {q}\), but has little to do with the actual positions of the data vectors \(\mathbf {x}_{i}\)’s over the data space. Evidently, the variance contribution to the expected error is then small. On the other hand, the prediction to a particular query \(\mathbf {q}\) is systematically biased toward the population response, regardless of any evidence for local variation in the data subspace \(\mathbb {D}(\mathbf {x},\theta )\). The other extreme is to select a radius \(\theta \) such that \(n_{\theta }(\mathbf {x}) = 1\) for all queries. We can expect less bias and, in this case, it goes to zero if \(n \rightarrow \infty \) [32]. Finally, Given the true model and infinite data, we should be able to reduce both the bias and variance terms to 0. That is, as the number of input data points n and \(n_{\theta }(\mathbf {x}) \rightarrow \infty \) such that \(\frac{n_{\theta }(\mathbf {x})}{n} \rightarrow 0\), then \(\hat{f}(\mathbf {x},\theta ) \rightarrow \mathbb {E}[y|\mathbf {x},\theta ]\). However, in real world with approximate models and finite data, the radius \(\theta \) plays the trade-off between minimizing the bias and minimizing the variance.

We experiment with different mean values \(\mu _{\theta }\) of the radius \(\theta \sim \mathcal {N}(\mu _{\theta },\sigma ^{2}_{\theta })\) having a fixed variance \(\sigma ^{2}_{\theta }\) to examine the impact on the model training, quality of aggregate answer prediction, and PLR approximation of the underlying data function g. We examine the number of training pairs, \(|\mathcal {T}|\), where our method requires to reach the convergence threshold \(\gamma = 0.01\). We also examine the impact of radius \(\theta \) on the RMSE and CoD metrics. Hence, three factors (\(|\mathcal {T}|\), RMSE, and CoD) are influenced by the radius \(\theta \). We experiment with mean radius \(\mu _{\theta } \in \{0.01, \ldots , 0.99\}\) over the R1 dataset (similar results are obtained in R2 and R3 datasets). Consider the queries with high radius \(\theta \) drawn from Gaussian \(\mathcal {N}(\mu _{\theta },\sigma ^{2}_{\theta })\) with high mean radius \(\mu _{\theta }\). Then, radius \(\theta \) nearly covers the entire input data range and aggregate answer y is close to the average value of output u for all queries, i.e., \(n_{\theta }\) contains all \(\mathbf {x}\) input data points. In this case, all query prototypes \(\mathbf {w}_{k}\) correspond to constant query-LLM functions \(f_{k}(\mathbf {x},\theta ) \approx y_{k} = y\), where aggregate answer \(y = \mathbb {E}[u]\) unconditioned to \(\mathbf {x}\) and radius \(\theta \). Hence, the training and convergence of all LLMs is trivial since there is no any specificity to be extracted from each query-LLM function \(f_{k}\). Our method converges with a low number of training pairs \(|\mathcal {T}|\) as shown in Fig. 27(lower). On the other hand, a small \(\theta \) value refers to learning ‘meticulously’ all the specificities for all LLMs. In this case, our method requires a relatively high number of training query–answer pairs \(|\mathcal {T}|\) to converge; see Fig. 27(lower).

In terms of accuracy, the higher the radius \(\theta \) is, the lower the RMSE e becomes. With high radius \(\theta \), all query-LLM functions refer to constant functions with the extreme case where \(f_{k} \approx \mathbb {E}[u], \forall k\) as discussed above, thus, the RMSE \(e = \sqrt{\frac{1}{M}\sum (y_{i} - \hat{y}_{i})^{2}} \rightarrow 0\) with \(y_{i} \approx \mathbb {E}[u]\) due to the fact that \(n_{\theta }\) contains all input data and, thus, \(\hat{y}_{i} \approx \mathbb {E}[u]\) (see Fig. 27(upper) with \(|\mathcal {T}|= 5359\) training pairs required for convergence w.r.t. \(\gamma = 0.01\)). However, this comes at the expense of a low CoD \(R^{2}\) since the data function g is approximated ‘solely’ by a constant approximate function \(g(\mathbf {x}) \approx \mathbb {E}[u]\) (see Fig. 27(lower)). When radius \(\theta \) is small, we attempt to estimate the query function f over \((\mathbf {x},\theta )\) and, thus, approximate the data function \(g(\mathbf {x})\). This, however, requires many training query–answer pairs \(|\mathcal {T}|\); see Fig. 27(lower). Overall, there is a trade-off in the number of training pairs \(|\mathcal {T}|\) with approximation and accuracy capability. To obtain quality approximation, the CoD metric should be strictly greater than zero. This is achieved by setting the mean radius value \(\mu _{\theta } < (0.4, 0.5)\) for \(d \in (5,2)\). Then, we can compensate the RMSE and training time (number of training pairs \(|\mathcal {T}|\)) as shown in Figs. 27 and 28. In addition, there is a trade-off between training effort and predictability. As shown in Figs. 27, 28 and as explained above, a low \(\mu _{\theta }\) value results to a high RMSE and training effort in terms of \(|\mathcal {T}|\) size. By combining those trade-offs, for a reasonable training effort, to achieve low RMSE and high goodness of fit, i.e., a high positive CoD value, we set mean radius value \(\mu _{\theta } = 0.1\), which corresponds to \(\sim \) 20% of the data range for \(\sigma ^{2}_{\theta } = 0.01\). Finally, Fig. 29 shows the impact (trajectory) of the mean radius \(\mu _{\theta }\) on the training set size \(|\mathcal {T}|\), the prediction accuracy w.r.t RMSE e, and the goodness of fit w.r.t CoD \(R^{2}\) metric for \(d \in (2,5)\) for R1; we obtain similar results for R2 and R3 datasets.