text:
\section{Appendix Overview}

In the appendix we provide a model that theoretically proves the capacity of linear dependencies in the Soft-FD model through the approximation of new sequences and stochastic analysis. Then, we include proofs for the theorems in Section~\ref{sec:theoretical_analysis} using the suggested theoretical model. We also include a comparison between our soft-FD index and Grid search.

\section{The Center-Sequence Model (CSM)}
\label{s7_3}
In this section, we compute the space cost of linear dependencies and the capacity of the soft-FD to efficiently model complex functional dependencies in data. We focus on linear soft-FD models and determine 1) what is the capacity of a linear model for modeling soft FDs with a specific maximum error (margin), and 2) if a single linear model cannot handle the data efficiently, how many segments are needed to model the soft FDs across the entire range of the primary attribute (i.e., across $X_{range}$ in Figure~\ref{fig:theory_softfd_scan_areas}). Following the theoretical supports of the effect of the learned index, we were also inspired to make a theoretical evaluation of the capacity and the performance of the Soft-FD model. Earlier studies \cite{fotso2019grasp,guo2010improved} suggest a method of constructing a new sequence by mean values or centers is widely used in the approximation of the original data set, since the two have the same statistical properties but the new sequence ignores some noise. Therefore, combined with the similar stochastic analysis method used in \cite{ferragina2020learned}, we aim to construct a new sequence to give a  theoretical support for the effectiveness of the Soft-FD model.

We first model the dataset as a sequence of intervals using the proposed \textit{Center-Sequence Model} (CSM). Then, we perform stochastic analysis on the CSM-based representation of data to estimate the expected number of keys covered by a linear segment and  the number of segments needed to cover a sequence of n multidimensional records.

\subsection{Representing Data with CSM}
Now we suggest the Center-Sequence Model, which represents the data as a sequence containing intervals where the data points are expected to be in the centre of each interval.
The new representation approximates the original data, such that the data and its interval-based representation have similar statistical characteristics.
The CSM model is inspired by a recent study~\cite{ferragina2020learned} on learned index structures which proposed using time series approximation and stochastic analysis to compute the upper and lower limits to estimate the capacity and the cost of using the piece-wise linear approximation (PLA) to fit the data points to a model in PLA-compatible learned index structure such as the PGM-index~\cite{ferragina2020pgm}.
The CSM representation makes it more straightforward to exploit stochastic analysis methods that we use for estimating the space cost of the soft-FD index and the effectiveness of linear and spline Soft-FD models.
In fact, approximating data using sequences (or sub-sequences, in case of linear spline soft-FD indexes) is very common in related work \cite{fotso2019grasp,ferragina2020learned}. Based on a stochastic analysis we can give a very good estimation of the effectiveness of linear correlations and help us simplify our model.

\subsection{Constructing new sequences to approximate the original data sequences}

We  explain how the interval representation is built from the  original data. We consider the two-dimensional case and assume that the data set is relatively large and contains N points. We split the B-box along the X-axis into n parts (n smaller parallelograms) using intervals of the same length $dx$. When $dx$ converges to 0, $n$ converges to $\infty$, hence we have smaller boxes where each box is expected to contain several original points.

\begin{figure}
\centering
\includegraphics[width=0.99\linewidth]{figures-part1/Picture2.pdf}
\caption{Segmentation of the B-box using the CSM model}
\label{fig_1}
\end{figure}

Let us denote the $k^{\text{th}}$ interval as $[t_k, t_{k+1}]$, as shown in Figure~\ref{fig_1}. Within these $n$ separated parts of B-box, if we connect the centroids of these sequences to form an equally spaced sequence, the new sequence will be ${ \{ [(t_i+t_{i+1}) /2, y_{i}], i \in [1,N]\} }$, where $y_i$ is the mean value of all points in the $i^{\text{th}}$ segment along the Y axis. Let us denote the number of points located in the $k^{\text{th}}$ part as $n_i$, and the Y values of these original data points as $Y_{original}$.

\begin{equation}
    y_i =\frac{1}{n_i} \sum_{Y_{original} \in i^{\text{th}}\,\text{interval}} Y_{original}
\end{equation}

We can rewrite the new sequence as $\{(i, y_i), i \in N\}$. In order to make our subsequent analysis more convenient, the starting point of the entire sequence is set as (0,0), i.e. when $i=0$, $y_i=0$.

For a precise CSM model, the original data points must be distributed around the centers. If we know the distribution in advance, we can precisely embed the distribution in the model. However, in a general case where we cannot make any assumptions about data distribution, the number of intervals n should be big so that the original data can be precisely approximated by the CSM model. We use the midpoints of the intervals along the X axis, say $[m_i, m_{i+1}]$,  to create equally spaced sequences. %

\subsection{Prerequisite of the efficiency of the model}
The CSM model assumes that the data distribution on the primary attribute (X-axis) is not extremely skewed and is close to uniform. Also, it assumes that the original data is large enough such that it can be accurately approximated by the interval model. To measure how close the data distribution is to a uniform distribution, we use the Kullback-Leibler (KL) Divergence. In our case, let's denote the set of X coordinates of all points is $X_t$, and then we need to define a new set to store all unique values in $X_t$ that are not repeated, and we call it the unique set of $X_t$, denoted as $X_u$, and the number of unique values in the unique set $X_u$ is $N_{unique}$. Since we have $P_{\text{uniform},i} = 1/N_{unique},  \forall i \in N$, and given $i\in [1,N_{unique}]$,  $X_i \in X_u$, $P_i = count(X_k = X_i)/ N_i, \forall X_k \in X_t$, KL-divergence could be expressed as
\begin{equation}
    D_{KL}(P || P_{\text{uniform}}) = \sum_i^{N_{unique}} P_i log(\frac{P_i}{P_{\text{uniform},i}})
\end{equation}

KL-Divergence provides a distance between the distribution of the  original points along the X axis and a uniform distribution. Let us denote the marginal distribution function of X axis is $P(X)$ and the distribution function of a typical uniform distribution is $P_{uniform}(X)$. When $P(X)=P_{uniform}(X)$, their KL distance is 0; otherwise, the greater the difference, the greater the distance. Since our model is under a nearly uniform distribution hypothesis, we can test that when KL distance becomes smaller and closer to 0, our model will perform better.

Figure~\ref{figt2_1} shows a worst-case scenario for the CSM model to represent the original data sets. Since the  data is skewed and the X values are far from  a uniform distribution, some segments are empty, hence the CSM model will no longer be equally spaced.

\begin{figure}
\centering
\includegraphics[width=1\linewidth]{figures-part1/Picture1.pdf}
\caption{Skewed data cases}
\label{figt2_1}
\end{figure}

\subsection{Relationship between new sequence and original one.} The goal is to show how far the original data points are from these centers. So let us assume a distribution model, i.e., we can assume all original points follow the distribution $N(y_i , \sigma_i)$, where the $y_i$ is the corresponding centers of the original points. The idea is equivalent to making assumptions on the generation rules of the original sequence given the new sequence. Then we can directly define the noise bar/ margin bar of these centers and say that all points are limited with high possibilities in a certain range around their centers. Put formally,

\begin{equation}
\forall \  X_{original} \in [m_i,m_{i+1}], P [Y_{original} \in [y_i-  2\sigma_i, y_i +2 \sigma_i] ] = 95\%
\end{equation}

Let us define $bar_m = max_{i} (\sigma_i), i \in N$, then we can say it is very possible (p = 95\%) that almost all original data points are limited in the $[ax+\varepsilon+2bar_m, ax+\varepsilon- 2bar_m ]$ before the fist Exit Time of new sequence {(i, $y_i$), i $\in$ N}

\begin{figure}
  \centering
  \begin{minipage}[b]{0.9\linewidth}
    \includegraphics[width=\linewidth]{figures-part1/Picture3_1.pdf}
    \subcaption{An example random walk}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.9\linewidth}
    \includegraphics[width=\linewidth]{figures-part1/Picture3_2.pdf}
    \subcaption{The corresponding transformed random walk}
  \end{minipage}
  \hfill
  \caption{Random walk illustration. The specific sequence model here refers to the key-position sequence proposed by Ferragina et al.~\cite{ferragina2020learned}. The difference between our model and the model in \cite{ferragina2020learned} is that for Soft-FDs we do not need to exchange the coordinate plane of the new stochastic sequence constructed by the CSM model, and the model is applicable for any unskewed value-value sequences. (a) shows the sequence of the centroids of the intervals, which are estimated using the CSM method mentioned in section \ref{s7_3}. We treat this sequence as a random walk. (b) shows the transformed random walk mentioned in section \ref{subsec:theory-capacity}, which is used in the stochastic analysis.} %
 \label{fig:transformed_random_walk}
\end{figure}

\section{Proof of Theorem~\ref{t1}}

\begin{proof}
Based on the CSM model and the reasonable assumptions made, our data points should be limited by linear segments, each of which consists of two boundary lines. Given the i.i.d. increments, the new sequence should be described as a plain stochastic process. When considering the expected numbers of keys (We call the values along Y-axis of the new sequence as "keys") covered by a linear segment, we only need to find the Mean First Exit Time (MFET) of the new sequence $\{(i, y_i), i \in N\}$.

As mentioned in \cite{gardiner1985handbook}, the Mean First Exit Time is defined from the spatial domain $D$ as $i^* := inf \{ i \geq 0, X_i \notin D \}$. Thus, in our case, the MFET can be written as $i^* = inf \{ i \in N | y_i > ai + \varepsilon \vee  y_i  <  ai - \varepsilon \}$

To make our formula more intuitive and concise, we use new symbols to simplify the stochastic sequence using the approach suggested by Ferragina et al.~\cite{ferragina2020learned}, where we consider $y_i  = \sum_{j=1}^i G_j$, and define $W_j = G_j - a$. Thus, we have $Z_i = y_i - a \cdot i = \sum_{j=1}^i (G_j - a) = \sum_{j=1}^i W_j$.

The statistical properties of the transformed stochastic process $Z_i$ and its increments $W_i$ can be easily computed based on  Ferragina et al.~\cite{ferragina2020learned}, Also, following the Central Limit Theorem, equation 3.1.(3)~\cite{ferragina2020learned}, the conditions mentioned in Masoliver et al.~\cite{masoliver2005extreme} and Redner~\cite{redner2001guide}, we know that when $\sigma \ll \varepsilon $,  the transformed stochastic process converges to a Brownian motion in continuous time.

According to \cite{gardiner1985handbook}, for a driftless Brownian motion, the Mean First Exit Time (MFET) out of an interval $[-\delta/2, \delta/2]$ is $T(x_0) = \frac{(\delta/2)^2-x_0^2}{\sigma^2}$, where $x_0$ denotes the initial position.

In our case, $x_0 =0$ and $\delta = 2\varepsilon$, thus we can easily conclude that $MFET = \frac{\varepsilon^2}{\sigma^2}$. The result means that for the new sequence, the expected numbers of keys covered by a linear segment is $MFET = \frac{\varepsilon^2}{\sigma^2}$. As we mentioned above, it is also reasonable to use this result to estimate the expected number of data points covered in the original Soft-FD model.

\end{proof}

\section{Proof of Theorem~\ref{t2}}

\begin{proof}

Following the proof of Theorem \ref{t1}, we want to express the expected number of keys covered by a single linear segment as a function of margin parameter $\varepsilon$ and the variance of the gap distribution $\sigma$. It can be easily shown that the transformed stochastic process $Z_i$ has increments with mean $d=\mu-a$ and variance $\sigma^2$. Based on prior analyses~\cite{ferragina2020learned}, when introducing the drift coefficient, the MFET out of an interval $[-\delta/2,\delta/2]$ for a Brownian motion with drift coefficient $d\rightarrow 0 $ and diffusion rate $\sigma$ can be written as
\begin{equation}
T(0) = \frac{\varepsilon}{d} tanh(\frac{\varepsilon d}{\sigma^2})
\end{equation}
When we introduce our model and the slope $a$, it is easy to see that the maximum of $T(0)$ is achieved for $d=0$, i.e., when $a=\mu$.

\end{proof}

\section{Proof of Theorem~\ref{t3}}

\begin{proof}
Now that we have the expected value of the Mean First Exit time, we need to know the second moment of MFET to compute the variance. Following Gardiner~\cite{gardiner1985handbook}, Equation 5.2.140-156), the second moment $T_2(x)$ of the exit time of a Brownian motion with diffusion rate $\sigma$ starting at x is the solution of the partial differential equation $-2T(x) = \frac{\sigma^2}{2} \frac{\partial^2 T_2(x)}{\partial x^2}$.

Where $T(x) = \frac{(\delta/2)^2-x^2}{\sigma^2}$ is the MFET. Thus, we have
\begin{equation}
    T_2(x) = \int -\frac{4}{\sigma^2} T(x) dx
\end{equation}

with boundary conditions $T_2(\pm\delta/2) =0$. By solving for $T_2(x)$, the second moment of the exit time is $T_2(0) = \frac{5\varepsilon^4}{3\sigma^4}$ when setting $x_0 =0 $ and $\delta = 2\varepsilon$. Therefore,

\begin{equation}
Variance = T_2(0) - [T(0)]^2 =\frac{2\varepsilon^4}{3 \sigma^4}
\end{equation}

\end{proof}

\section{Proof of Theorem~\ref{t4}}

\begin{proof}

Consider that one single linear segment cannot cover all of the data, so we can assume the total number of segments needed to be s given a stream of stochastic sequence with length n. Suggested by Ferragina et al.~\cite{ferragina2020learned}, we similarly define
\begin{equation}
s(n) := max \{k| k \geq 1, s.t.  S_k \leq n\}
\end{equation}
where $S_k = i_1^* + i_2^*+ ... + i^*_k$.

Recall that a renewal process is an arrival process in which the interarrival intervals are positive, independent and identically distributed (i.i.d.) random variables, we notice that $\{s(n)\}_{n\geq 0}$ is a \textit{renewal counting process}. Therefore, based on~\cite{embrechts2013modelling}, $\mathbb{E}[s(n)] = \lambda n + O(1)$ as $n \rightarrow \infty$, $Var[s(n)] = \chi^2\lambda^3n + O(n)$ as $n \rightarrow \infty$, and $s(n)/n \rightarrow \lambda$. In our case, it holds:
\begin{equation}
\frac{1}{\lambda} = \frac{\varepsilon^2}{\sigma^2} \ \  \text{and} \ \ \chi^2 =\frac{2\varepsilon^4}{3 \sigma^4}
\end{equation}

Hence, almost surely  $s(n)/n \rightarrow \lambda = \frac{\sigma^2}{\varepsilon^2}$. Thus, we also have $s(n) \rightarrow n \cdot \frac{\sigma^2}{\varepsilon^2}$
Given this result, we conclude that the number of segments s converges to $O(n/\varepsilon^2)$.

\end{proof}

\section{Comparison with the Grid Index}
To understand the effect of the proposed index on memory footprint reduction, we compare it with a multidimensional index, specifically a grid index. For the sake of simplicity, we compare the Soft-FD index against a square grid and do not consider workload-aware or distribution-based optimizations on grids.

Consider a grid index with N dimensions. If the data has soft functional dependencies between some dimensions, we can partition N dimensions into \textit{primary} and \textit{soft-dependent} attributes where for each attribute in the soft-dependent set, say Y, there is an attribute from the primary dimensions, say X, such that $X\rightarrow Y$ is a soft FD. Let us denote $k^{\text{th}}$ the ($k^{\text{th}}$ pair of X-Y soft functional dependency. $a_k$ is the slope of the fitted curve of Soft-FD model.

A grid index, on the other hand, creates an N-dimensional array of cells where each cell stores points for specific ranges in each dimension. Figure~\ref{fig:square_grid_search} shows how a 2D grid processes the range query ${x \in [l_x, h_x], y \in [l_y, h_y]}$. The grid scans 14 cells for processing the query (empty cells still require a lookup). The soft FD index, however, translates the Y-axis constraints $y \in [l_y, h_y]$ to X-axis constraints $x \in [l'_x, h'_x]$ and the final constrains on the X-axis is the intersection of the two ranges ($[l'_x, h'_x] \cap [l'_x, h'_x])$. In the example shown in Figure~\ref{fig:square_grid_search}, the X-axis range inferred from the Y-axis, $[l'_x, h'_x]$, is a smaller range than the actual constraints on $X$ which is $[l_x, h_x]$. Therefore, the soft-FD index scans a smaller area ($S_s$) than the grid ($S_{\text{Grid}}$). In general, $S_s$ may be smaller or bigger than $S_{\text{Grid}}$ depending on the query constraints, the size of the grid cells, and the margins of the soft-FD index.

We analyze how reducing the dimensions affects the index structures.  We are interested to see "how many cells does the 2-D grid need to scan, compared to a soft-FD index that keeps the records in a contiguous array, assuming that both indexes scan areas of roughly the same size". Therefore, we consider a grid index in which the number of cells is specifically chosen such that the area the grid scans equals a constant value t times the scanned area in the Soft-FD model, i.e., $S_{Grid} = t \cdot S_s$. When t=1, it means we have exactly the same scanned area between the Soft-FD and grid models.

The number of cells that a square grid index scans can be estimated as the ratio between the whole area and the scanned area.

\begin{equation}
    n_k =\frac{S_{whole}}{t \cdot S_s}  =  (\frac{Y_{range}}{t \cdot \varepsilon} \cdot \frac{X_{range}}{(2\varepsilon+q_y)/a_k})
\end{equation}

\begin{figure}
\centering
\includegraphics[width=0.99\linewidth]{figures-part1/Picture5.pdf}
\vspace{-8pt}
\caption{An example Square-Grid.  The area that the grid scans for the range query $\{ (x,y) | l_x \leq x \leq h_x, l_y \leq y \leq h_y)\}$ is marked with a red rectangle.}
\label{fig:square_grid_search}
\end{figure}

We define $r_k$ as the ratio between length and the width of s-box:
\begin{equation}
    r_k = \frac{\text{Length(B-box)}}{\text{Width(B-Box)}} = \frac{\sqrt{Y_{range}^2+X_{range}^2}}{2\varepsilon / \sqrt{1+a_k^2}}
\end{equation}

Then, we can compute the scanned cells in grid as:

\begin{equation*}
\begin{aligned}
n_k &= \frac{X_{range} \cdot Y_{Range} \cdot a_k}{t \cdot ( \frac{(1+a_k^2)(Y_{range}^2+X_{range}^2)}{r_k^2} + q_y \frac{(\sqrt{1+a_k^2})(\sqrt{Y_{range}^2+X_{range}^2}}{r_k} ) } \\
    &= \frac{X_{range} \cdot Y_{Range} \cdot a_k}{t \cdot (f(r_k|a_k,X,Y)^2+ q_y f(r_k|a_k,X,Y))}
\end{aligned}
\end{equation*}

Where $f(r_k|a_k,X,Y)=(\sqrt{1+a_k^2})(\sqrt{Y_{range}^2+X_{range}^2})/r_k $ is a function of $r_k$. Given the distribution of data points and a fixed linear dependence, when $r_k$ increases,  $f(r_k|a_k,X,Y)$ decreases, and then $n_k$ increases. It can be easily imagined that when $ r_k \rightarrow \infty$, $n_k$ will get close to infinity as well. Thus, for K pairs of attributes in total (K is O(d), d denotes the total dimensions), we may need to create $n_1\cdot n_2 ... \cdot n_K = n^K$ cells in total. It can be easily concluded that if $r_k$ is larger, i.e., the B-box has a narrow margin, therefore and equivalent grid index needs a large number of cells to reach the almost same space cost as Soft-FD model.

\section{Introduction}

Multidimensional data plays a crucial role in  data analytics applications.%
Indexing multidimensional data, however, is challenging as the curse of dimensionality hits: with every additional dimension indexed, the performance of the index degrades. %
A promising approach to tackle the curse of dimensionality is using machine learning techniques and exploit patterns in data distribution for more efficient indexing. For example, learned indexes automatically model and use the distribution of the underlying data to locate the data records~\cite{kraska2018case, galakatos2018tree,kipf2020radixspline, nathan2020learning, ding2020alex, hadian2019interpolation} and the idea has been extended to indexing multidimensional data~\cite{nathan2020learning}.

In this paper we develop a new class of learned indexes for multidimensional data that uses dependencies between attributes of either the full or a subset of the dataset to improve performance of the index structure. Our approach is motivated by the observation that it is common in real-world datasets for two or more attributes of the data to correlate.
We argue that by taking learned indexes to the multidimensional case, in addition to learning from CDF of the data, we can also learn from relationships between attributes of the data such as the correlation between $id$ and $timestamp$, a common case in real-world datasets; or between flight distance and flight time in an airline dataset. The idea of learning the relationship between attributes of data has already been used to improve estimating the selectivity of a given query and thus to improve query optimizers~\cite{ilyas2004cords} and one-dimensional secondary indexes~\cite{wu2019designing}. We take this idea a step further to indexing multidimensional data.

More precisely, we develop models that explain correlations in the attributes of the data and we show that a multidimensional index does not need to index every dimension if some attributes are correlated. The index only needs to store one dimension per each group of correlated attributes, thereby effectively reducing the dimensionality of the dataset. In case a query targets an attribute $C_d$  that is not indexed but there is another indexed attribute $C_x$ correlated to $C_d$ ($C_x\rightarrow C_d$), we use our model to check which range of values in $C_x$ correlate with the query and run a translated query over the indexed attribute instead. As we show experimentally, the suggested approach significantly shrinks the memory footprint of the index, by four orders of magnitudes depending on the number of the FDs and their degree of correlation, while improving the overall lookup time of the indexes by 25\%.

\section{Related Work}
\label{sec:relatedwork}
Our ideas build on model-based indexes, including learned indexes and interpolation search, as well as spatial indexes.

Recently, it was suggested that models driven from data can improve the lookup time of indexes and reduce memory footprint in what are called learned indexes~\cite{kraska2018case}. In a learned index, the CDF of the key distribution is learned by fitting a model; then the learned model is used as a replacement for the conventional index structures (such as B+trees) for finding the location of the query results. Index learning frameworks such as the RMI model~\cite{kraska2018case} are capable of learning arbitrary models, although a further theoretical study~\cite{ferragina2020learned} %
have shown that models such as linear splines are effective for most real-world datasets. Spline-based learned indexes include Piecewise Geometric Model index (PGM-index)~\cite{ferragina2020pgm}, Fiting-tree~\cite{galakatos2018tree}, Model-Assisted B-tree (MAB-tree)~\cite{hadian2020madex}, Radix-Spline~\cite{kipf2020radixspline}, Interpolation-friendly B-tree (IF-Btree)~\cite{hadian2019interpolation} and others
~\cite{llaveshi2019accelerating,setiawan2020function}. A comprehensive comparison of learned indexing approaches can be found here~\cite{ferragina2020survey}.

COAX is inspired by hybrid learned indexes that combine machine learning with traditional indexes structures, including RadixSpline~\cite{kipf2020radixspline}, FITing-tree~\cite{galakatos2018tree}, Interpolation-Friendly B-tree~\cite{hadian2019interpolation}, and MADEX~\cite{hadian2020madex}. Hybrid learned indexes have been well explored in the one-dimensional case.
\ifextended
For example, RadixSpline~\cite{kipf2020radixspline} uses radix-trees as the top-level model while FITing-tree~\cite{galakatos2018tree} and IFB-tree~\cite{hadian2019interpolation} use B+-tree as the top-level index structure. Then they use a series of piecewise linear functions in the leaf level.
\fi
Furthermore, adaptability and updatability of learned indexes have been explored in a similar area \cite{ding2020alex, hadian2019considerations}. Finally, in the multivariate area, learning from a workload has also shown interesting results \cite{nathan2020learning,hadian2020handsoff}.

\ifextended
Besides the main trend in learned indexes (focusing on range indexing), machine learning has also inspired other indexing and retrieval tasks. This includes bloom filters~\cite{mitzenmacher2018model,dai2019adaptive}, inverted indexes~\cite{xiang2018pavo}, conjunctive Boolean intersection\cite{oosterhuis2018potential}, learned indexing for strings~\cite{wang2020sindex}, rule-matching~\cite{li2019accelerating,zhang2020efficient}, and computing list intersections~\cite{ao2011efficient}.
\fi

Another direction that we exploit in this paper is the statistical dependency between the attributes (data columns), i.e.,  the notion of \textit{soft functional dependencies (Soft FDs)}~\cite{ilyas2004cords,wu2019designing}, which is a relaxed definition of FDs. A soft FD between X and Y means that the value of X determines the value of Y with a high probability, i.e., we can predict Y using X but there might be errors in prediction, for example, from Flight departure time we can determine the approximate arrival time.
Soft FDs have been mainly used for selectivity estimation in query optimization~\cite{ilyas2004cords,kimura2009correlation,liu2016exploiting}, designing materialized views and indexes~\cite{zdonik2010coradd}, data integration from multiple data sources~\cite{wang2009functional}, and reducing the number of secondary indexes~\cite{wu2019designing}. In this work, however, we aim to design an index structure that uses soft FDs to decrease memory footprint and accelerate query execution in a \textit{multidimensional index}.

In contrast to the related work like HERMIT, which is based on unclustered secondary indexes, COAX builds a multidimensional primary index, which is more efficient for range indexing as it does not require heavy join operations for multidimensional queries. Moreover, related work only considers cases with a small percentage of outliers (the records that do not follow the dependency pattern) while COAX consists of two indexes where the outliers are organised as a separate multidimensional index, hence supporting datasets with a much `softer' functional dependency, i.e., a considerable number of outliers (e.g., $25\%$). Finally, previous work on soft-FD requires the DBA to manually introduce all soft-functional dependencies and handcraft the index layout for the soft-FD, which is very time-consuming for the DBA. COAX, on the other hand, automatically detects the correlated columns and works with any multidimensional index structure.

\section{Approach Overview}

\label{sec:overview}
We are interested in exploiting correlations in a multidimensional dataset to build a more efficient index.
The key components of COAX, illustrated in Figure~\ref{fig:overview}, are as follows:

\begin{figure}
\centering
    \includegraphics[width=.99\linewidth]{figures/overview.pdf}
\vspace{-7pt}
\caption{The suggested index structure: a primary index (top) indexes only one dimension from each group of correlated attributes, while a small outlier index handles the outliers and guarantees retrieval of all results.}
\label{fig:overview}
\vspace{-10pt}
\end{figure}

\begin{itemize}[leftmargin=*]
    \item \textbf{Query translation.}
    The core idea of COAX is that to build an $n$-dimensional index on a data where $m$ attributes are highly correlated with the other $n-m$ attributes (i.e., $m$ dependent attributes), we can build a multidimensional index on the $n-m$ attributes which results in a much smaller multidimensional index.  If a query constraint targets one of the dependent attributes, COAX transforms the constraint into another constraint on one of the indexed attributes. Query translation uses a model that predicts the \textit{dependent attributes} using a set of \textit{indexed attributes}, along with the tolerance margins.
    \item \textbf{Learning the correlations.} COAX detects whether a functional dependency exists between two or more attributes, and evaluates whether the dependency can be effectively modelled in the presence of outliers.
    \item \textbf{Learned Soft-FD index.} We apply a pre-processing step to our data. We use the learned correlations to separate data that agrees with the learned dependency from the remaining points that are regarded as outliers. We create a \textit{primary index} on the data points that have up to a certain deviation from the learned correlation (i.e., those that are within a certain tolerance margin around the fitted line). The primary index only indexes one attribute per each set of correlated attributes. For the rest of the correlated attributes, a model is learned to represent the correlation between \textit{indexed attributes} and \textit{learned attributes} is used to execute queries. If a query targets a dependent attribute $C_d$ that is not indexed but is correlated with an indexed attribute $C_x$, then the learned correlation model converts query constraints targeting $C_d$ to an equivalent constraint on $C_x$.
    \item \textbf{Outlier index.} Data points that do not fall within the tolerance margin of the soft FD model are excluded from the primary index and are indexed with all dimensions in an \textit{outlier index}, which is a typical multidimensional index structure.
\end{itemize}

\section{COAX Query Translation}
\label{sec:query-translation}
Let us consider the simple case where we want to answer queries on two attributes $C_1$ and $C_2$:

\begin{lstlisting}[language=SQL,
morekeywords={clustered},
mathescape=true]
    SELECT * FROM tbl WHERE     $q_1^{low} < C_1 < q_1^{high}$
                        AND     $q_2^{low} < C_2 < q_2^{high}$;
\end{lstlisting}

We define a query by a rectangle characterised by its lowermost leftmost point $(q_1^{low},~ q_2^{low})$ and uppermost rightmost point $(q_1^{high},~ q_2^{high})$. Note that with this setting, we can express the case where, for example, only the first dimension is queried by defining $q_2^{high}=\infty$ and $q_2^{low}=-\infty$. Similarly, we can express point queries by defining the lower and upper points to be equal. %

Suppose that the attributes to be indexed are correlated, i.e., there is a soft functional dependency between one attribute, say $C_x$ (the \textit{indexed} attribute), and another dependent attribute $C_d$.
In this case, a range index can be built on only one of the attributes ($C_x)$, and the query constraint that targets a non-indexed attribute $C_d$ can be mapped to equivalent query constraints on the indexed attribute using the prediction model and its error bounds. To do this without loss of accuracy, we need an oracle dependency function $\psi: C_x \rightarrow C_d$ that calculates the value of $C_d$ based on a given $C_x$ for each row in the dataset. Because in practice finding such an oracle function may prove impossible for a \textit{soft} functional dependency, we must relax this concept and allow our model to instead estimate an approximate value for $C_d$, i.e., $\hat{\psi}: C_x \rightarrow C_d$

Similar to learned range indexes \cite{kraska2018case}, using an approximation without any bounds is impractical since we want to avoid scanning the entire dataset. We must therefore define a tight error bound for the approximation.
To do so, we argue that once a significant majority of the values of the dependent attribute $C_d$ are very close to the values predicted by $\hat{\psi}$ model. For any point $(p_x, p_d) \in (C_x, C_d)$ in our primary index we have:

\begin{equation}
p_d \in [\hat{\psi}(p_x) - \epsilon_{LB}, \psi(p_x) + \epsilon_{UB}]
\end{equation}

Where $\epsilon_{LB}$ and $\epsilon_{UB}$ are the the lower bound and upper bound error margins, or as illustrated graphically, the distances at which the data separators have been drawn in both directions. We then keep the records that fall between these bounds and leave outliers aside to be inserted into the outlier index. Figure~\ref{fig:overview} shows the process of defining the two parallel lines characterising the lower and upper error bounds of a linear regression model, and the role of our primary and outlier index.

To create a primary index on $C_x$ and $C_d$, we only need to sort the rows based on the $C_d$ attribute. To answer a range query on both dimensions, we need to (1) calculate which range of values in the indexed dimension corresponds to the queried range for the missing dimension and (2) scan the intersection of the queried ranges projected on the indexed dimension.
Put differently, because the data in the primary index fits in within the lower and upper bound estimates of the model, we can tighten the lower and upper bounds of our query for each of the correlated dimensions making the overall scanned range smaller. As illustrated in Figure~\ref{intersection}, we need to find the intersection of the query rectangle with our lower and upper thresholds. We then scan the records in the indexed attribute ($C_d$) between the more selective bounds (drawn as solid vertical lines in Figure~\ref{intersection}), i.e.:
\begin{equation}
\hspace{-5pt}
\left[max\left(\hat{\psi}(q_1^{low}), q_2^{low}-\epsilon_{LB}\right), min\left(\hat{\psi}(q_1^{high}), q_2^{high}+\epsilon_{UB}\right)\right]
\end{equation}

\begin{figure}
  \centering
  \begin{minipage}[b]{0.44\linewidth}
    \includegraphics[width=\linewidth]{figures/query_intersect.pdf}
  \end{minipage}
  \hspace{0.02\linewidth}
  \begin{minipage}[b]{0.44\linewidth}
    \includegraphics[width=\linewidth]{figures/query_limited.pdf}
  \end{minipage}
  \vspace{-10pt}
  \caption{Query execution on the primary index. Query constraints targeting the dependent attributes $C_d$ are mapped to equivalent constraints on the indexed attribute $C_x$ using the model and the error bounds. The final query constraint is the intersection of the two constraints on $C_x$}
  \vspace{-8pt}
\label{intersection}
\end{figure}

\section{Training the Soft-FD Models}
\label{sec:detecting-the-dependencies}

Detecting the soft-FDs and learning a soft-FD model that
is computationally expensive. To tackle this, COAX uses a fraction of keys rather than the full key set to train the model and evaluate the efficiency of adopting a potential soft-FD.
More precisely, COAX only considers centres of \textit{dense areas} in a sample drawn from the dataset. We overlay a multidimensional grid on the key space and count the number of records in each cell. We then filter out any cells that do not reach a threshold in their count and consider our training data to be the weighted centres of the remaining cells.
\ifextended
This is depicted in Figure~\ref{fig:densepoints}. %

\begin{figure}
  \centering
  \begin{minipage}[b]{0.44\linewidth}
    \includegraphics[width=\linewidth]{figures/2.pdf}
  \end{minipage}
  \hspace{0.03\linewidth}
  \begin{minipage}[b]{0.44\linewidth}
    \includegraphics[width=\linewidth]{figures/0.pdf}
  \end{minipage}
  \caption{An error margin can be defined by considering the  the correlation model of the data (left) and the density of the data records around the model (right)}
  \label{fig:densepoints}
\end{figure}
\fi

After the training set (bucket centres) is found, we recursively consider unique pairs of attributes and use a Monte Carlo sampler to check whether a linear model fits the training records (Algorithm \ref{alg:split}) to learn correlations between multiple attributes. If two attributes are found to be correlated, we save the resulting pair along with their model parameters. In the final step, we merge all groups that have an attribute in common and pick one attribute in each group to be the predictor responsible for estimating the remaining attributes in its group. %

\begin{algorithm}
\SetAlgoLined
\textbf{Input:} Centred attribute values: $C_x$, $C_d$ [$N$] \\
\textbf{Result:} Model parameters ($m$, $b$), $primary\_index$, $outlier\_index$ \\
$C_x\_sample$ = $C_x$.sample($sample\_count$) \\
$C_d\_sample$ = $C_d$.sample($sample\_count$) \\
$w_x$ = $C_x\_sample$.max() / $bucket\_chunks$ \\
$w_d$ = $C_d\_sample$.max() / $bucket\_chunks$ \\
$buckets$ = [$bucket\_chunks$][$bucket\_chunks$] \\
\For{$i\gets 0$ \KwTo $sample\_count$}{
    $buckets$[$C_x$[$i$] / $w_x$][$C_d$[$i$] / $w_d$] += $1$ \\
}
$C_x\_train$ = $C_d\_train$ = [] \\
\For{$i\gets 0$ \KwTo $bucket\_chunks$}{
    \For{$j\gets 0$ \KwTo $bucket\_chunks$}{
        \If{$buckets$[$i$][$j$] $>$ $threshold$} {
            $C_x\_train$ += [i * $w_x$ + 0.5$w_x$] * $buckets$[$i$][$j$] \\
            $C_d\_train$ += [j * $w_d$ + 0.5$w_d$] * $buckets$[$i$][$j$] \\
        }
    }
}
$m, b$ = linear\_regress($C_x\_train$, $C_d\_train$) \\
$displacements$ = $(C_d - (m \cdot C_x - b))$\\
\For{$i\gets 0$ \KwTo $N$}{
    \eIf{$- \epsilon_{LB} < displacements[i] < \epsilon_{UB}$} {
        $primary\_index$.insert($C_x$[$i$], $C_d$[$i$]) \\
    } {
        $outlier\_index$.insert($C_x$[$i$], $C_d$[$i$]) \\
    }
}

\caption{Splitting Data}
\label{alg:split}
\end{algorithm}

The accuracy and runtime of the learning step can be adjusted by tuning parameters given in our proposed algorithm. To increase the accuracy of the model, we can draw a larger learning sample from the dataset, group them in smaller cells and define a lower cell acceptance threshold. This, however, increases the number of records processed by the regression algorithm and can degrade training run time.

The bucketing step significantly reduces the number of records the regression algorithm has to consider without impeding the method's ability to generalise. This reduces the training time but more importantly, it provides an added benefit; recall that we have already inserted our sample records in a grid index (to use centre points of its denser cells to define our training set), we can maintain the trained index for later use. As new records are added, a sample of new items can be inserted in the existing grid index without having to populate it from scratch. This in combination with the fact that we have used a Bayesian method for learning the regression model, can help supporting updates on the index, as we can use the previous gradient and intersect and continuously adjust our existing model.

\section{Index Implementation}
\label{sec:indexlayout}

To evaluate differences in performance when predicting dimensions, we need to build an index on \textit{indexed dimensions}. We implement our index on top of Grid Files~\cite{nievergelt1981grid} with a number of modifications. In particular, we choose boundaries for each cell based on quantiles along each dimension and use the same number of grid lines for each attribute. Addresses for all cells are sorted using the original ordering of attributes in the dataset. Furthermore, each cell stores records in a contiguous block of virtual memory in a row store format. Finally, rows within each page are sorted based on a given function similar to the approach proposed in Flood \cite{nathan2020learning}. Sorting the rows inside pages means that we can reduce the dimensionality of the grid by one. This is because instead of having grid lines for the particular sorted attribute, we can use binary search to locate items (or a scan between two bounding binary searches in a range query).

\ifextended

Note that picking grid lines based on the distribution of the dataset does not mean that we have regular cells. Although doing so does reduce the standard deviation in cell lengths for non-uniform datasets, bucket lengths are still allowed to grow arbitrarily large. Figure~\ref{fig:histofpagesize} shows the variation in cell lengths in one of our experiments.

\begin{figure}
  \centering
    \begin{minipage}[b]{\linewidth}
  \centering
    \includegraphics[width=.75\linewidth]{figures/page_sizes.pdf}
    \subcaption{Non-uniform distribution of page sizes in 2D grid layout}
    \label{fig:histofpagesize}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.46\linewidth}
    \includegraphics[width=\linewidth]{figures/grid.pdf}
    \subcaption{2D Index Layout}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.46\linewidth}
    \includegraphics[width=\linewidth]{figures/columns.pdf}
    \subcaption{Learned 1D Grid}
  \end{minipage}
  \hfill
  \caption{Reducing index dimensionality allows having more accurate grids for the remaining predictor dimensions}
  \vspace{-10pt}
 \label{gridshape}
\end{figure}

\fi

The combination of predicting attributes and having a sorted dimension means that for a dataset with $n$ dimensions and $m$ predicted attributes, we only need an index with $n-m-1$ dimensions. Due to this reduced dimensionality, we will show in section \ref{sec:memoryperformancetradeoff} that the resulting index makes much more efficient use of memory.

\section{Theoretical Analysis}
\label{sec:theoretical_analysis}
In this section, we analyze how the performance of the soft-FD model is affected by the margin size and how its memory footprint compares with a multidimensional index (square grid) that performs the same number of comparisons.

\subsection{Effect of Margin Size}
Figure~\ref{fig:theory_softfd_scan_areas} compares the area scanned by the soft-FD model, with the area of the actual result set. We define the following regions:

\begin{itemize}[leftmargin=*]
    \item \textit{B-box} (shown as a green box) is the index \textit{ boundaries}): the area that contains all data points (records) restricted by two borderlines and hence supported by the Soft-FD index. Any data point outside of B-box needs to be handled by the outlier index.
    \item \textit{R-box} is the \textit{Result set}, which is shown as a red parallelogram.
    \item S-Box is the \textit{Scanned} area, illustrated by a  blue parallelogram. For the index to return all results, we need have $\textit{R-box} \subset \textit{S-box}$. Both S-box and R-box are within the green rectangle with dashed lines.

\end{itemize}

Without loss of generality, we assume that the margin has the same length from both sides, i.e., $\epsilon_{LB} = \epsilon_{UB} = \epsilon$. Also, we consider linear models only, and assume that B-box is symmetric, which means that $\hat{\psi}(x) = ax$. Therefore, the two boundary lines are defined as $ y=ax+ \varepsilon$ and $y= ax- \varepsilon$. Note that, if the model is non-symmetric ($\hat{\psi}(x) = ax + b, b\neq 0$) or if $\epsilon_{LB} = \epsilon_{UB}$, the areas of B-box, S-Box, and R-box are the same and we transform the problem to a symmetric equivalent with a parallel movement.

The query constraints can be on the X-axis, the Y-axis, or both. The constraints on either of the axes are translated to its equivalent in the other axis (considering the $\pm \varepsilon$ boundaries) and eventually define some S-box parallelogram as explained in Section~\ref{sec:query-translation}. Therefore, without loss of generality, here we consider a range query with constraints on the Y-axis only while other queries can be translated to this case. Given the pre-defined range $(h_y,l_y)$, i.e., we want to find all points $(x_i,y_i)$ where $y_i \in [q_y,l_y]$. Let us denote the data range on the X-axis (the indexed attribute) as $X_{range}$ and the range on the Y-axis (the dependent attribute) as $Y_{range}$.

We define $q_y$ as the range of the query $q_y = h_y - l_y$. The area of R-box (the red parallelogram) is denoted as $S_r$. R-box is the result set, and we ideally expect the soft-FD index to scan exactly the R-box region (i.e., the red parallelogram in Figure~\ref{fig:theory_softfd_scan_areas}).
 Following the equations of boundary lines  $ y=ax+ \varepsilon$ and $y= ax- \varepsilon$ and the definition of $\varepsilon$ above, $S_r$ can be computed using the base of the R-Box ($Base_{r}$) and its height ($Height_{r}$):

\begin{equation}
\label{eq:s_r}
S_r = Base_{r} \cdot Height_{r} =(\frac{hy+\varepsilon}{a}-\frac{hy-\varepsilon}{a}) \cdot q_y = q_y \cdot \frac{2\epsilon}{a}
\end{equation}

\begin{figure}
\centering
\includegraphics[width=0.99\linewidth]{figures-part1/Picture4.pdf}
\vspace{-10pt}
\caption{Illustrating the notation. B-box defines the boundaries of the index (the range of records indexed by the Soft-FD index). R-box (red parallelogram) is the result set. S-box (blue parallelogram) is the area scanned. The range query $(h_y,l_y)$ is shown with red dashed lines.}
\label{fig:theory_softfd_scan_areas}
\end{figure}

For the Soft-FD model, we define the scanned area $S_s$ as the area of the S-box (the blue parallelogram in Figure~\ref{fig:theory_softfd_scan_areas}). $S_s$ is likewise estimated using the base and height of the S-box:

\begin{equation}
    S_s = Base_{s} \cdot Height_{s} = \frac{2\varepsilon(2\varepsilon+q_y)}{a}
\end{equation}

We define the \textit{effectiveness} of the Soft-FD model as the ratio between $S_r$, the effective scanning area in ideal cases, and $S_s$, the actual area that the Soft-FD index needs to scan:

\begin{equation}
\label{eq:effectiveness}
   \text{effectiveness} = \frac{S_r}{S_s} = \frac{q_y}{2\varepsilon+q_y}
\end{equation}

Effectiveness is the ratio of the red area and blue area in Figure~\ref{fig:theory_softfd_scan_areas}, which is affected by the width of the B-box ($2\epsilon$). It can be concluded from Equation~\ref{eq:effectiveness} that when the margin is tighter and $\varepsilon$ gets closer to 0, effectiveness gets closer to 1, which means the area that the Soft FD index estimates for scanning match the actual result set, i.e., S-Box fits R-Box and $S_r = S_s$. Similarly, when $\varepsilon$ gets larger, the ratio gets smaller, which means that the Soft-FD model is less effective. We assumed that the data distribution is close to uniform, otherwise the PDF of the distribution has to be considered in Equation~\ref{eq:effectiveness}.

\subsection{The Capacity of Linear Soft-FD Models}
\label{subsec:theory-capacity}
In this section, we provide a stochastic analysis to estimate the capacity of a soft-FD index. If the segmentation number n is large enough, the number of data points in the original data set and the number of keys in the new sequence are of the same order of magnitude. Thus, we can estimate the capacity of a soft-FD index with the properties of the new sequence. Our key results are:
\begin{itemize}[leftmargin=*]
    \item The expected number of keys covered by a linear segment (Theorem \ref{t1})
    \item The number of segments needed to cover a stream of length n (Theorem \ref{t4}), which is the capacity of a linear model for a soft-FD index.
\end{itemize}

We also provide additional conclusions, including  Theorem \ref{t2} which helps us explain the necessary conditions for the optimal value of Theorem \ref{t1}. %
\ifextended
The proofs of all theorems is provided in the Appendix.
\else
The proofs of all theorems is provided in the Appendix of the extended version of this paper\footnote{\url{https://arxiv.org/abs/2006.16393}}.
\fi

Ferragina et al.~\cite{ferragina2020learned}  suggest a stochastic process to measure the capacity of learned indexes by making an approximate assumption of a stochastic process for the position-key sequence and designed reasonable distributions over X-axis (Key axis). We build on their thinking with the help of our CSM model, and we can directly assume the gap distribution of the Y-axis data, so that we no longer need the swapping of the coordinate. In other words, by discretizing the continuous value-value sequence via the CSM model, we generalized their stochastic sequence model.  In practice, we assume that the sequence gaps $\{g_i\}$ are random variables which are sampled from the i.i.d. distribution $G_i$ with probability density function $f_G$, and then we can make assumptions on the mean and variance of the gap distribution, with mean $\mathbb{E}[G_i] = \mu$ and variance $Var[G_i] = \sigma^2$.

\begin{theorem}
In the soft-FD model, if a single linear segment has slope $a=\mu$ and the margin parameter $\varepsilon$ is sufficiently larger than the variance of the gap distribution $\sigma$, the expected number of keys covered by this linear segment is
$
 \frac{\varepsilon^2}{\sigma^2}
$
\label{t1}
\end{theorem}

\begin{theorem}
Given the same assumptions of Theorem \ref{t1}, the expected number of keys covered by a single linear segment can be expressed as a function of margin parameter $\varepsilon$ and the variance of the gap distribution $\sigma$. The maximum value of this function, i.e. the largest expected number of keys covered is achieved when the slope is $\mu$.
\label{t2}
\end{theorem}

\begin{theorem}
Given the assumptions and symbols of Theorem \ref{t1}, the variance of the number of keys covered by a single linear segment is $\frac{2\varepsilon^4}{3 \sigma^4}$
\label{t3}
\end{theorem}

Even though this paper mainly discusses a linear soft-FD model (in terms of a linear model with a margin of constant width), one can use more complicated non-linear methods to model soft functional dependencies that cannot be modelled with a linear model. Among non-linear models, we specifically consider linear splines, which are recently shown to be very effective in learned indexes for modelling the value-to-position mappings~\cite{galakatos2018tree,kipf2020radixspline,ferragina2020pgm}. Linear splines still consist of linear models, where each linear model is used in a specific region. Theorem~\ref{t4} suggests the number of segments that a linear spline model requires for modelling soft-FDs with a maximum error of $\epsilon$.

\begin{theorem}
Following the basic assumptions of Theorem \ref{t1}, given a data stream of length n and the margin parameter $\varepsilon$, the number of segments s needed to cover the stream can be computed from the results of Theorem \ref{t1} and Theorem \ref{t2}, which converges to
$n \cdot \frac{\sigma^2}{\varepsilon^2}$
\label{t4}
\end{theorem}

\section{Evaluation}
\label{sec:evaluation}

\subsection{Experimental Setup}
\subsubsection{Implementation and Runtime Environment} We implement the online section of our index in C and compile it using Clang 10.0.0. All of the indexes in our experiments run in a single thread and use single-precision floating point values. We build the soft-FD model using Python and the pymc3 library \cite{pymc3}. We run our experiments on an Intel Core i5-8210Y CPU running at 3.6 GHz (L1: 128KB, L2: 512KB, L3: 4MB) and 8GB of RAM.

\subsubsection{Datasets}
We run experiments on two real-world datasets:

\textit{Open Street Map (\textit{OSM})}: we use 4 dimensions of the OSM data for the US Northeast region \cite{osm} which contains 105M records; The $Id$ and $Timestamp$ attributes in the OSM dataset are correlated and its $Latitude$ and $Longitude$ coordinates contain multiple dense areas. For this dataset we group ($Id$, $Timestamp$) for the case of learned index.

\textit{\textit{Airlines}}: data from US Airlines flights from 2000 up to 2009, which has 8 attributes and 80M records. The airline dataset is more interesting for our experiments because it contains many correlated dimensions. Example grouping in this dataset in our experiments usually consists of ($Distance$, $TimeElapsed$, $AirTime$) and ($ArrTime$, $DepTime$, $ScheduledArrTime$). We can reduce the grid dimensionality to 2-4(depending on the tolerated error threshold). Table~\ref{tbl:datasets} summarises the key aspects of the datasets.

\begin{table}
\setlength\extrarowheight{3pt}
  \begin{center}
    \label{tab:table1}
    \begin{tabular}{l c r}
     \hline
       & \textbf{Airline} & \textbf{OSM}\\
     \hline
      \textbf{Count} & 80M & 105M\\
      \textbf{Key Type} & float & float\\
      \textbf{Dimensions} & 8  &  4\\
      \textbf{Correlated Dimensions} & (3, 3)  &  2\\
      \textbf{Indexed Dimensions (Soft-FD Index)} & 2-4  &  3\\
      \textbf{Primary Index Ratio} & 92\%  &  73\% \\
     \hline
    \end{tabular}
    \caption{Dataset characteristics}
    \label{tbl:datasets}
  \end{center}
  \vspace{-15pt}
\end{table}

We generate the queries by picking a random record from the data. Then, we find the K nearest records and take the minimum and maximum values corresponding to each dimension. Our range queries are rectangles and target all attributes in the index. %

\subsubsection{Baselines}
We compare our suggested method with the \textit{R-Tree}, arguably the most broadly used index for multidimensional data, and two grid structures as baselines: the uniform grid and column files.

\textit{Uniform grid}: or equivalently the full grid, is a hash structure that breaks down each attribute into uniformly sized grid cells between their minimum and maximum values. The address for each cell is stored independently and no adjacent cells are "shared/merged" explicitly. In memory, addresses for all cells are sorted using the original ordering of attributes in the dataset. Furthermore, each cell stores points in a contiguous block of virtual memory in a row store format.

\textit{Column files}: Essentially a non uniform grid, uses the CDF of the data to align/arrange its cell boundaries and sorts data within each cell based on one of the attributes in the data, thus reducing the dimensionality of the index by one. In a lookup on the sorted dimension, we use binary search in each cell to get the range that needs to be scanned. Column files is  similar to the approach~\cite{nathan2020learning} with the difference that it does not assume that the query workload is known and hence uses the data distribution to arrange and align the grid layout.

\textit{Full scan}: Every item in the dataset is checked against queries.

\subsection{Results}
\subsubsection{Tuning}
In this experiment we measure and compare the execution time for all indexes. We use the configuration that performs best for each index. This configuration consists of chunk size for the full grid, chunk size and sort dimension for the column files and COAX, and the node capacity (non-leaf and leaf capacity) of the R-Tree. For example, we evaluated different node capacities between 2 to 32 for the for the R-Tree index and the best performance for each experiment (i.e., point queries and individually for each selectivity rate in range queries) was used. The best node size for R-Tree is between 8 and 12.%

Due to memory constraints, we %
limit any index that would require more memory overhead for its index directory than memory occupied by the underlying data itself. %

We evaluate our results using range queries and point queries that are drawn randomly from each dataset. We define a point query as a range query where the lower bound and upper bound in the matching hyper rectangle are equal.

\subsubsection{Point and range queries}
As seen in Figure~\ref{runtime}, COAX outperforms both the R-Tree and full grid. The main drawback in the case of full grid is the higher index dimensionality and the fact that it is limited in terms of how many cells it can use.
\ifextended
An example illustration for this in 2D is shown in Figure~\ref{gridshape}.
\fi
This is because with a skewed dataset, most grid cells become empty or very small in size. In addition, in comparison to Column Files, COAX benefits from a smaller number of memory lookups. The decreased total number of cells in COAX also translates to binary search on larger ranges in each cell, which makes COAX even more efficient.

\begin{figure}
\centering
    \includegraphics[width=\linewidth]{figures/run_times.pdf}
 \caption{Query runtime performance on airline and OSM data for range and point queries. Note the log scale.}
\label{runtime}
\end{figure}

\begin{figure}
\centering
    \includegraphics[width=\linewidth]{figures/selectivity.pdf}
\vspace{-7pt}
\caption{Runtime comparison for range queries with different selectivity values on airline data for year 2008 (7M)}
\label{runtimeselectivity}
\end{figure}

\subsubsection{Effect of selectivity in range queries}
In addition to this, we run the same experiment with the range queries with selectivity sizes. In this experiment we use the airline data for the year 2008 only. The results, shown in Figure~\ref{runtimeselectivity}, indicate that the Learned Gird does not lose performance on larger/shorter queries. We can check whether the query intersects with the primary, the outlier, or both indexes; and run it against the appropriate indexes. For queries with larger selectivities, it is hence more likely for both indexes to be invoked which results in more invocation and bigger overhead for the outlier index.

\todo[inline]{difference in pre processing step. and limitations}
\todo[inline]{bar plot of memory}
\todo[inline]{why the osm data doesnt perform that good}
\todo[inline]{explain what is seen in the Figures more}
\todo[inline] {make a table for run times}
\todo[inline] {normalise run times}

\subsubsection{Memory Usage}
\label{sec:memoryperformancetradeoff}

Figure~\ref{fig:pointercost} plot the range query performance against memory overhead in the case of COAX, attribute files and the R-Tree. The results show that all grid indexes have a sweet spot. This is because as we increase the number of cells, although we are likely to scan fewer items, after a certain point the increased pointer lookups starts to hurt performance mainly because there is diminishing returns in reducing the actual items considered when increasing the grid size. %
\ifextended
This effect is illustrated in Figure~\ref{gridshape}.
\fi

\begin{figure}
  \centering
    \begin{minipage}[b]{\linewidth}
  \centering
    \includegraphics[width=\linewidth]{figures/memory_performance2.pdf}
    \subcaption{Airlines (7M)}
  \end{minipage}
  \hfill
  \centering
    \begin{minipage}[b]{\linewidth}
  \centering
    \includegraphics[width=\linewidth]{figures/memory_performance.pdf}
    \subcaption{OSM (9M)}
  \end{minipage}
  \caption{Runtime vs memory footprint tradeoff for COAX and competitors. Note the log scale}
  \label{fig:pointercost}
\end{figure}

\section{Conclusions \& Future Work}
\label{sec:conclusions}
In this paper we address the degradation of performance/query execution time for every additionally indexed dimension. Instead of indexing all dimensions, COAX learns the soft-FDs, i.e., the correlation between different attributes. By doing so, we no longer have to index the \textit{dependent} attributes and can thus reduce the number of dimensions indexed, thereby accelerating query execution and reducing memory overhead. In case the dependent attribute is queried for, we use the model (as well as the outlier index) to find a starting point for scanning the data. As we show experimentally, our approach uses substantially less memory and also executes queries faster. COAX shrinks the memory footprint of the index by four orders of magnitude, while reducing the query execution time by 25\%.

Our idea can be extended to the case of non-linear models for the dependency and the margins, including a mixture of models. Also, COAX can be extended to support updates. We leave this as future work.

redpajama_set_name: RedPajamaArXiv


Convenient. Can be conducted any time that suits your schedule. No hassle. No need to empty out the kitchen and store. No need to vacate the premise No odor, no stain, and no fume. High performance. Ensures total elimination of cockroaches. Long lasting control of all types of cockroaches. Gel Baiting is a non-spray system for cockroach control. Proven effective in thousands of homes, offices, restaurants, factories.
They are nocturnal in habit and are rarely seen during daytime. Because of their evasive behavior and nocturnal habit, for every one you see, there can be many more hiding and multiplying in hidden places. If you see cockroaches by day could mean a possible sign of severe infestation.Cockroaches can enter homes and apartments in many different ways, from the outside through cracks and crevices, vents, sewer and drain pipes. They can also get entry through grocery bags,boxes, etc.
A. Promise you High Quality of the Product.
We a re a professional manufacturer who specialize in producing moth repellent and so on. In order to keep high quality of products, we always use the best quality of raw materiels to producce our products and strickly supervise the process of producing. Because of our persistent persue of best quality, our products have been popular for 10 years among customers, especially in the Africa, Asia and so on market.
B. Promise you Best Price.
As a professional manufacturer we not only offer you the best quality but also the best price. Because we have 10 years experience of manufacturing products and we have a super-professional and technical work team, we can well control of the cost of our products, labor resource and so on. That is why we can promis you the best price.
C. Promise you Best Service.
With 6 years of experience of exporting, our team know well of the process of international trade, and we can provide you with the best service during the foreign trade business .


text:
Pierre-Marcel Rousselin est un homme politique français né le  à Caen (Calvados) et décédé le  à Rully (Calvados).

Magistrat, il est conseiller auditeur à la cour d'appel de Caen en 1813, puis devient avocat en 1818. Il est nommé procureur général de cette cour d'appel le  et premier président en 1835. Il est nommé pair de France le .

Source

Naissance en janvier 1788
Naissance à Caen au XVIIIe siècle
Décès en mai 1863
Décès dans le Calvados
Pair de France (Monarchie de Juillet)
Magistrat français du XIXe siècle
Décès à 75 ans

redpajama_set_name: RedPajamaWikipedia


"What if you could reduce your planning process from 1 week to 1 hour, or from 1 hour to 1 second? What if you could, at the click of a button, improve your bottom line by double digits? In this session, you will learn to do just that by leveraging IBM's powerful Machine Learning (ML) and Decision Optimization (DO) technologies together. You will learn the differences and complementary strengths of ML and DO, learn best practices, and see examples of combining these technologies to achieve financial gains and efficiencies based on some IBM Data Science Elite client projects. The session also includes a demo of combining ML & DO in IBM Data Science Experience (DSX)."
This webcast was produced by Susara van Den Heever, IBM Data Science Elite program director at IBM.


text:
S&P Says Qatar Developer Ezdan Faces Restructuring, Default Risk
Ezdan Holding Group faces the risk of debt restructuring or default as the Qatari real estate developer is yet to obtain credit-lines to meet upcoming maturities, according to S&P Global Ratings, Bloomberg News reported. "Despite discussing payment option plans, the company is still in the negotiation stage of securing a committed credit line to address its significant upcoming debt maturities and amortization schedule," according to the ratings agency. S&P cut Ezdan's rating to CCC from B- with negative outlook. Ezdan's $500 million senior unsecured sukuk matures on May 18.
Kuwait Seeks Approval to Use Wealth Fund to Finance Deficit
Tuesday, February 23 2021
Kuwait's government submitted a draft law to parliament seeking permission to withdraw as much as 5 billion dinars ($16.5 billion) a year from the country's sovereign wealth fund to help finance a spiraling deficit, Bloomberg News reported. If approved by lawmakers, it would be the first time since the aftermath of the Gulf War in 1990 that Kuwait had extracted funds from the $600 billion Future Generations Fund. Previous withdrawals were treated as loans and had to be repaid.
As Lebanon's Banks Struggle to Raise Capital, a Deadline Looms
Wednesday, February 17 2021
Paralysed by financial crisis and riven with political risk, a number of Lebanon's banks are struggling to meet a central bank target to raise their capital defences by 20% by the end of this month, Reuters reported. Less than half of the country's dozen or so large banks are expected to meet the requirement, which the central bank set in August to reinforce the sector, according to four banking sources with direct knowledge of the situation.
International Companies Without Headquarters in Saudi "Will Have to Make a Choice" to Land Government Contracts in 2024
International companies that want to participate in the Saudi government's investment opportunities "will have to make a choice" and establish regional headquarters in the kingdom as of 2024 or they will not win government contracts, the Saudi finance minister told Reuters yesterday.
Intelsat Files Restructuring Plan to Emerge from Bankruptcy
Monday, February 15 2021
Satellite operator Intelsat SA said on Friday it has filed a restructuring plan backed by some of its creditors, in a bid to reduce debt and emerge from bankruptcy in the second half of the year, Reuters reported. The plan aims to reduce debt by more than half to $7 billion and has the support of holders of about $3.8 billion of its debt, the company said. It has sought a hearing on Mar. 17 for a court approval to solicit votes on the plan.
Egypt Extends Rate Pause With Eye on Global Economic Risks
Friday, February 5 2021
Egypt held interest rates, putting monetary easing on pause for another month as the coronavirus keeps global markets on edge, Bloomberg News reported. The deposit rate will remain at 8.25% and the lending rate at 9.25%, the central bank's Monetary Policy Committee said Thursday in a statement. Ten of 13 economists surveyed by Bloomberg had predicted the decision. The second wave of the pandemic and containment steps "continue to weigh on the near-term outlook," the MPC said.
ATO Wins $137 Million from Binetters' Israeli Banks after 16-year Pursuit
Wednesday, February 3 2021
Two Israeli banks have paid $137 million to draw a curtain on the expanding pursuit of tax fraud cases related to the Binetter family, the founders of the Nudie Juice business, in a weekend settlement, the Financial Review reported.
ADCB Sees Creditors Approval for NMC Restructuring in First Half
Monday, February 1 2021
Abu Dhabi Commercial Bank PJSC, one of the biggest lenders to NMC Health Plc, expects creditors' approval for a restructuring plan for the collapsed hospital operator in the first half, Bloomberg News reported. The bank recorded 1.66 billion dirhams ($450 million) in provisions and interest in suspense toward NMC, Finablr Plc and associated companies last year, according to a statement. ADCB is "comfortable" with the provisioning levels, "given the positive developments in NMC's recent financial performance and its ongoing restructuring process," it said.
Saudi Arabia Returns to Dollar-Debt Market to Boost Finances
Saudi Arabia sold a two-part dollar bond as countries in the Gulf Arab region raise cash buffers to weather low oil prices and the coronavirus pandemic, Bloomberg News reported. The world's largest crude exporter priced $5 billion in bonds on Tuesday. The $2.75 billion 12-year notes were priced at 130 basis points over 10-year U.S. Treasuries, compared with guidance of 140 basis points and initial price talk of 165. The $2.25 billion 40-year security were priced at 3.45%, versus guidance in the 3.55% area and initial price talk of 3.75%.
Protests Mount in Tunisia over Economic Woes, with Hundreds Arrested
Tunisian youths clashed with security forces in cities across this North African nation for a fourth night on Monday, burning tires and hurling gasoline bombs to protest worsening economic problems, police violence and poor government services, the Washington Post reported. Security forces have retaliated with tear gas and water cannons to disperse the hundreds of teenagers. While scenes of mayhem and chaos captured in videos zipped across social media, there were also peaceful demonstrations.

redpajama_set_name: RedPajamaCommonCrawl


I keep hoping Tim Sullivan will chime in on this one. In a similar discussion on the tuba/euphonium Facebook page I think he suggested that Alexander, B & S, and VMI were virtually one in the same during a period in European history. What we see here in the US is limited by what is sold here in the US. There are lots of things that never reach our shores.
Dan Schultz wrote: I keep hoping Tim Sullivan will chime in on this one. In a similar discussion on the tuba/euphonium Facebook page I think he suggested that Alexander, B & S, and VMI were virtually one in the same during a period in European history. What we see here in the US is limited by what is sold here in the US. There are lots of things that never reach our shores.
I seem to remember reading that one, love hearing from the guys who immersed themselves into a particular area of horn study and can tell you everything you don't hear in the general discussion threads. I will have to look him up and hear his conclusion.


text:
Lessons from the gridiron
Joseph Krum, Executive Editor|December 3, 2016
Senior Joseph Krum runs onto the field for the first Round playoff game against Rowlett at Coppell High School.
Ale Ceniceros
I was in complete shock.
It was Saturday, Nov. 26 and I was at Waco ISD Stadium, my hands covering my face in disbelief to hide the tears. Just seconds earlier, my Coppell football team had just lost a heartbreaker in the third round of the playoffs, ending the season and my football career.
I hugged senior teammate Eric Loop. I hugged head coach Mike DeWitt. Then it hit me what had just happened. The sport that I had played for nine years was gone, just like that. After endless workouts and meetings and early morning practices, I would never be able to strap up a helmet and play the game that I loved so much.
Yet the impact of football on my life is something that has not stopped and never will. The lessons that it has given me has molded me into who I am today and who I will become.
"Football taught me so many things," senior defensive back Austin Weathers said. "It taught me how to be tough and how to be responsible, and it gave me life skills that I will keep for the rest of my life. I wouldn't trade [my playing career] for anything."
The first of many lessons that I really grasped from football is teamwork. Now it may seem simple and overused, but there is nothing like lining up with 10 other guys on the field with one object in mind: either score a touchdown or prevent the other team from scoring. And especially as an offensive lineman, the teamwork within the offensive line is crucial to have any success.
Courtesy: Laura Schertz
Teamwork has shaped my life as a student and as a member of society. Every day, whether it's a group project, carpooling to school, or even deciding where we should go out to eat as a family with my siblings, I have to work with others to accomplish a goal and football has given me that ability.
Football has shown me how to persevere and dedicate myself to something, especially when it gets tough. Throughout each before school practice that ended before the sun rises, each two-a-day in the blazing heat of August, each sprint drill that took every bit of energy I had left, I learned how to give my absolute best effort no matter what the circumstances where.
"As a coach I think one of my jobs is to show my kids how to be a competitor and excel and work hard at whatever they are doing," Coppell football coach Mike DeWitt said. "Whether that's in their job or academically, they will always have that trait to bow their neck when things get tough."
I had to persevere through several injuries throughout my career, including a broken leg and a concussion in seventh grade, but what I remember built up my character most was persevering through scout team. Scout team, when heard by most football players, is followed with a cringe. It is where, as a freshman or sophomore, the younger players "scout", or practice against, the varsity players.
My most vivid memory of scout team is my freshman year, when I scouted for the playoffs. I remember it being below freezing temperatures and getting pounded by the seniors on varsity, many of whom ended up playing football at the collegiate level. After enduring two weeks of the pain, while most of my friends did not bother to show up, I remember making a personal decision to go to practice no matter how terrible it was.
There is no reward for doing what I was told, but I started to instill a character trait within myself that set the foundation of who I am today.
Above all, I am appreciative of the relationships that I have made with my teammates. There is nothing like joking around with your teammates in the locker room before a game, and those relationships are what I will miss the most.
"The relationships I have grown with my teammates are stronger than any other relationship I've had," senior football player Rodrigo De La Garza said. "I can trust anyone on the team with my life, and that is not something you can build anywhere else."
Football is unique in the relationships it can create, the lessons it can teach and the morals it can provide. While the memories of playing will fade away as time passes, these aspects will not; they will stay with me for the rest of my life.
Joseph Krum, Executive Enterprise Editor
Joseph is the Executive Enterprise Editor on the Sidekick Newspaper and he also plays football for the high school. Joseph is a senior in high school...
Ale Ceniceros, Photography Editor
Ale is a senior and the Photography Editor for The Sidekick. She has been involved with photography for 7 years and hopes to continue down this path in...
Following Teacher Appreciation Night, girls rout Nimitz
Swim team entering district meet with splash of color
Are sports overrated extracurriculars?
Cowgirls to recognize teachers while taking on Nimitz
Coach's Box: Hartsburg applying Mavericks experiences to basketball coaching
It's time for equality for women in sports
Pros/cons of pushing kids into sports
Stop the clock


James T. Egan is a book cover designer residing on the Oregon coast. His work includes designs for romance author Elizabeth Cole. Here he discusses using extensive photo retouching skills to create the images for titles Honor & Roses and Choose the Sky, part of the Swordcross Knights series.


The Wings for Life World Run is a truly unique and global race for both runners and wheelchair participants. Instead of a finish line, competitors race side by side to keep ahead of the virtual Catcher Car. Now in its sixth year, on May 5, 2019 Wings for Life World Run participants in Brazil can also run together in Brasília - Distrito Federal. Meet up with your friends, download the Wings for Life World Run App and join all the other people running until the virtual Catcher Car catches you of course. The race starts at exactly 08:00. The virtual Catcher Car takes off 30 minutes after the start at 14 km/h and steadily increases its speed until the last athletes have been caught. 100% of all donations and the entry fees go directly into spinal cord research projects.
The race takes place at Parque da Cidade and starts at the 5th Parking Lot. Runners will go through 5km around the main training track of the park and wrapping up the lap back at the starting point, with a water station on the course.


We are a church that believes Jesus welcomes everyone, with no exceptions. So do we!
No matter where you are on your spiritual journey, no matter your age, or your background, we would love to invite you to experience our church family as we seek God together. And here's the thing – there's no need to dress up, be someone you're not, just come as you are.


Our collaboration with the Architects aims to achieve good lighting design. It is the comfort resolved in atmospheres from interior design and architecture. The way is to have a lighting design and control in its execution.


If for no other reason, the 1988 Oldsmobile Cutlass Supreme was significant as it was the last year that the Cutlass was offered in rear-wheel drive form. Whether this fact will have an impact on the future value of that model is an open question, as trends in the classic car market can be quite fickle. After all, I'm sure that during the 1960s, no-one would have believed that the Edsel would achieve the popularity that it has today. This Cutlass Supreme GT is claimed to be 1-of-400 built, but that's a claim that we'll examine in a moment. It's a bit rough around the edges, but it appears to have minimal rust. It is located in Rockingham, North Carolina, and is listed for sale here on eBay.
The Cutlass Supreme GT package actually wasn't an Oldsmobile model in itself but was a dress-up package that was authorized by Oldsmobile, and the work was completed by Tops and Trends in North Carolina. The package consisted of a non-functional hood scoop and rear spoiler, and while some people claimed that these items were a genuine H/O items, they were actually aftermarket components. On top of the standard Cutlass Supreme equipment, the cars were fitted with a floor console and shifter (although column shift was available as a delete option), two-tone paint, either chrome or painted wheels, and a dash plaque which provided the sequence number of the car out of the run of 400 vehicles. This is another area of some misconception because while the intention was to build 400 cars, the final number was significantly less. Most estimates put the final tally at somewhere between 250 and 280 vehicles, as records are vague, at best.
Overall, the GT actually looks relatively solid. The owner states that the underside of the car is clean, and most of the visible rust in the car seems to be confined to the passenger side of the car. There is a small area in the lower quarter panel on that side, and there is also some appearing along the bottom edge of the door on the same side. The paint itself seems to have held up reasonably well, although it is looking a bit tired on the trunk lid where there's also a couple of spots of rust. The owner says that there is a piece broken out of the hood scoop, but this piece is in the trunk, and that it could be repaired.
The interior of the vehicle is looking quite tired, but it is at least serviceable. The bonus with the GT is the fact that all of the interior items and trim are standard Cutlass Supreme items, so the parts needed to whip it back into shape are still available. The original radio/cassette player is missing from the dash, while the dash pad is cracked. The owner also says that the car needs a new headliner, while the carpet also looks like it needs to be replaced. Being a Supreme, the car is fitted with power windows, cruise control, and air conditioning, although the A/C doesn't work at present.
What should be under the hood is the 307ci Oldsmobile V8, and this would be backed by a 4-speed automatic transmission. The original engine isn't there anymore, but it does come with the car. What is sitting there now is a fairly warm Oldsmobile 455. It appears that the engine has undergone a recent rebuild, as the owner says that everything in the engine is new. It is also fitted with a new carburetor, a new fan and fan clutch, new Flowmaster headers, a new oil pump, a new distributor, along with new plugs and wires. The owner states that the car sounds really nice. It is also fitted with new tires, and these have only covered about 20 miles since they were fitted. One thing that the car will need is some work on the brakes. Apparently, the pedal is hard, so the brakes may require at least a partial overhaul.
Although there were less than the originally planned 400 Cutlass Supreme GTs built, this is not the first one that I've seen for sale in the last six months. The big question really is whether the GT Package actually adds anything to the overall value of the vehicle, or whether it merely constitutes bragging rights. The last one that I saw was not as good as this one, but it did have the original engine under the hood. That one had an asking price of $8,000. This one comes with the original engine but is currently fitted with a warmed-over big-block. Bidding hasn't been frantic on this car. Well actually, there's only been one bid, and that's for $2,000. However, it does appear that the reserve has been met, and there are 14 people who are watching it. Even if you consider the car as a plain old Cutlass Supreme that has been fitted with a big-block, it does have some potential at that price.
Dr. Olds is elderly now and when he was shown a picture of this Olds screamed No!, No! Oh please, No!
Original engine is not going to add any value. If you like to smoke tires and surprise people at the stoplights, this could be a good way to do it.
If this generation of Cutlass had been offered with a 455, a 4-speed transmission, and a stout rear end it would be the most sought-after car of the '80's – a fitting companion to a GNX.
No guts, no glory, GM.
Where is the non-functional hood scoop the car is supposed to have?
It is shown in one pic but not in others. It might be just sitting there. Also, 5.0 usually tells what's under the hood. It ain't no 5 liter!
I have a pair of 1988 Cutlass Supreme Classics-1 is my first car, has the identical interior only in burgundy from Factory with the chrome wheels. In 87 it would've been the Cutlass Salon model.
The GT for sale is an interesting car but nothing special- could've been Factory optioned that way except for the paint treatment, spoiler and fake hood scoop.
This car looks kind of tattered, hopefully it finds a good home.
Too many questions come with this purchase . Rust stains around the radiator cap before or after that new fat aluminum unit went in . Is the 200 auto still in it ? A sick 455 will thrash a 200 before you leave the driveway . Dual batteries ran on ONE ground , did some Kidd stick a "system" in it ? Thus cutting speaker holes everywhere ? Or , did it have hydraulics on it before the young master gave up ? And , yes where's the damn hood scoop ?
Eww an egr motor. Even the torque of a smog 455 will make that stock 200r4 come apart violently.
No Hood scoop, broken part or otherwise. Was it glued on, and the dot repainted?
In most locations this car wold have to be smogged, which this car would fail fabulously.
My 1987 Cutlass Supreme is the reason I said when I sold it in 1991 I'll never purchase another GM product. It was sharp for about a year, then the silver paint turned to more of a charcoal texture. I removed all the trim, sanded the whole car, primed it then shot a gallon of shimron paint on it that had 2.5 times the amount of metallic than the recipe called for. It was beautiful and a head-turner now, but talk about junk from the factory. The 307 started burning oil almost exactly at the 50000 mile mark, then the torque converter began to intermittently fail on longer drives. I had to get a "running start" to make it up hills. Leaky T-Tops too. I liked the factory chrome wheels though, and it did have a visible rear stabilizer bar which looked cool. Rally gauges, buckets, console, sporty steering wheel, but JUNK!! Leave these cars alone folks. The 1988 model was only built to use the leftover parts from the 1987's anyway.
Talk about keeping it real.. I totally agree with your comment and experience owning one. For the life of me I don't get how anything from this time period has any value. Stickers.. stripes..,bucket seats and a few worthless gauges still add up to nothing..
was painful. If that 455 has any kind of cam in it it could explain the brake & booster issues.
Craig, you are correct about the seller's description. He should have put down the crack pipe and had a literate person write the description.
Spun main in 350 76 class supreme broughm. One owner (my mom)swapped 69 455 out of delta 88 (also one owner)electronic ignition,quadrajet off 350,junkyard manifold,headers. Kept 2.41 open rearend. Surprised a few 5.0 mustang, and walked a new 86 vette on highway. Torque Rules.
I had an 87 Supreme Brougham. It was the V6 and it rode very well and also looked very nice. I had no problems with it and kept it for 5 yrs. before I sold it. I wish I still had it. Now, I love the 455 so much that I ran one in a camaro that ran 9.90's in the quartermile.(It was an experiment) I wish this guy would've taken his time and did this right. Talk about a street sleeper!


Tucker had just eaten carrots and peach cobbler. Yum! Believe it or not, he did actually eat all of it even though it looks like it all ended up on his shirt!
Caroline is showing off her new giraffe rain boots. She loves them and insists on wearing them most of the time. Her favorite look is duck pajamas and giraffe rain boots.


text:
KIWAP In Malayalam Movie Download 1080p 720p 480p
by admin December 19, 2022 December 19, 2022
KIWAP In Malayalam Movie Download Rajwap
All things are illegal if you go without permission, If you want to truly watch you go on the OTT platform and enjoy many movies and web series.
KIWAP In Malayalam Movie Download Movierulz
Movierulz dates all sorts of movies to date in Full HD factor. The users may see the movies and can get information about them from our article. Hence, it is illegal to support pirated content so we neither support nor promote it. Supporting it may turn you to be get punished and can be hanged in prison so of it. Just enjoy the Movie download.
It has released movie leaks in Hollywood, Bollywood, Southern, and other languages up to now. These sites offer many options, including the Movie download of HD printing, 720p 300Mb, 480p, 1080p, and 480p. However, it is illegal to pirate films and Download pirated ones, which is why we don't support pirate films at all.
KIWAP In Malayalam Movie Download Telegram Link
It is also an enormous medium through which movie links are readily accessible. In this case, movie groups are creaIT which contain links to leaked films are used. That is illegal, you should not go.
KIWAP In Malayalam Movie Download Ibomma
This is a very special platform for downloading movies or web series. From this platform, there will be no kind of problem or issue with downloading the picture. It is enormous and the most specified platform for the downloading of movies. From here you can easily download movies in any of the resolutions in full of HD quality. Hence, download the movie from this platform
KIWAP In Malayalam Movie Download Filmyhit
Filmyhit has released movie leaks on Hollywood, Bollywood, Southern, Web Series, Tv-Shows, and other languages up to now. These sites offer many options, including the Movie download of HD printing, 720p 300Mb, 480p, 1080p, and 480p. However, it is illegal to pirate films and download pirated ones, which is why we don't support pirate films at all.
KIWAP In Malayalam Movie Download Filmywap
On this site, you will find the entire collection from Hollywood, Bollywood, and other films in different languages. The pirate copy of the film will be posted in HD print resolution. It's illegal.
KIWAP In Malayalam Movie Download APK
APK website leaks Hindi, Bollywood, South InTitanicn, and Hollywood movies. The Movie download Chup can be accessed through this site, which is also in HD quality. However, pirating films and downloading pirated films is a crime that is illegal and comes with a promise of severe punishment for doing this.
KIWAP In Malayalam Movie Download Khatrimaza
It is to date downloads all sorts of films to date in Full HD resolution. The users are able to select a resolution between 1080p, 720p, or 480p. 1080p to download the film. It is a site known for its leaks of pirate films. It is also prohibited in many other countries, including InTitanic. You should not go Download movies.
KIWAP In Malayalam Movie Download Kuttymovies
It has released movie leaks on Hollywood, Bollywood, Southern, Web Series, Tv-Shows, and other languages. These sites offer many options, including the Movie Download of HD printing, 720p 300Mb, 480p, 1080p, and 480p. However, it is illegal to pirate films and pirate ones, which is why we don't support pirate films at all.
Disclaimer: This website never promotes any piracy content through this or any other website or platform. This website is for informational purposes only. In this article, we only give information. Piracy is an act of crime & It is considered a serious offence under the copyright act of 1957. Please stay away from such websites, and choose the right way to download movies.
Marathiworld Marathi Movie Download 1080p 720p 480p
Kuttymovies.in Tamil 2022 Movie Download 1080p 720p 480p
Movieflix Verse Bollywood Movie Download 1080p 720p 480p
Kaththi movie download in hindi dubbed- 1080p, 720p, 480p-min


Black cotton Loretto pleats t-shirts from muller of yoshiokubo featuring a round neck, short sleeves and contrasting rear panel.
Ivory cotton-silk blend embroidery long dress from muller of yoshiokubo featuring a deep V neck, long sleeves, a shift silhouette and a straight hem.
Brown cotton-linen blend Dry tweed dress from muller of yoshiokubo featuring a deep V neck, a sleeveless design, a mid-length, a flared skirt and frayed edges.
Cream linen blend Agdal dress from muller of yoshiokubo featuring a v-neck, long sleeves, a mid-length and a flared style.
Black cotton Bahia lace shift dress from muller of yoshiokubo featuring a v-neck, half sleeves, a knee length and lace panels.
Black Ben quilted oversized coat from muller of yoshiokubo.
Ochre yellow wool-blend open back flared dress from muller of yoshiokubo.
Ivory cotton blend printed shift dress from Muller of Yoshiokubo featuring a round neck, cap sleeves, a straight hem, a knee length and contrast back.
Burgundy cotton blend sleeveless embroidered midi dress from muller of yoshiokubo featuring a round neck, a sleeveless design, a button fastening, a mid-length, a shift silhouette and an embroidered design.


Halsey's "Without Me" (Capitol) will remain #1 on the T40 chart for a third week, as Republic's Ariana Grande leaps into the Top 10 with "7 Rings" on pace to be the Greatest Gainer, while Travis Scott's "Sicko Mode" (Cactus Jack/Grand Hustle/Epic) also breaks the Top 10.
At Rhythm, Team RCA delivered Khalid his first #1 at the format with "Better," while Lil Baby & Gunna's "Drip Too Hard" (QC/Motown/Capitol) breaks into the Top 5 and Post Malone's "Wow" (Republic) makes a strong push inside the Top 10.
And at Modern Rock we have a new #1, as Flora Cash's "You're Somebody Else" (Bee & El/RCA) moves into the top spot, while Cage The Elephant's "Ready To Let Go" (RCA) rockets to #13, up a massive 1100 spins.