# SbMBR Tree--A Spatiotemporal Data Indexing and Compression Algorithm for Data Analysis and Mining
## 3 Proposed Methodology  
### Structure of SbMBR Tree  
To achieve lossy compression of spatial data according to a given maximum error, we use MBRs (minimum bounding rectangles) to partition the spatial data. An MBR contains data within a certain space range, as well as information about the average value of these data and the maximum error of these data [8]. In the process of compression, we select appropriate MBRs according to the given maximum acceptable error and use the average value contained in each selected MBR to replace the original data.  
To realize the above-mentioned selection process quickly, we constructed an index tree for these MBRs. We call the index tree SbMBR tree. The structure of the SbMBR tree is similar to that of the R-tree. Each node in the SbMBR tree contains an MBR. The MBR in the child node is completely contained by the MBR of the parent node. The maximum error value contained in nodes at the same layer in the SbMBR tree is the same. The maximum error value contained in the node in the deeper position in the tree is smaller than that of the node in the shallow position. In particular, the root node contains the entire spatial data, and its maximum error value is the largest in the tree. An example of the structure of an SbMBR tree is shown in Figure 1.  
The structure of the SbMBR tree will be described more formally below. Let \(S=\{R_{1},R_{2},\ldots,R_{n}\}\) be a set of \(n\) MBRs in the plane. Each MBR contains six properties, namely, the x-coordinate of the bottom left corner \(x_{\min}(R_{i})\), the y-coordinate of the bottom left corner \(y_{\min}(R_{i})\), the x-coordinate of the top right corner \(x_{\max}(R_{i})\), the y-coordinate of the top right corner \(y_{\max}(R_{i})\), as well as the average value \(\mu(R_{i})\) and the maximum error \(\epsilon(R_{i})\) of the data in the area denoted by the bottom left and top right corners.  
**Definition 1**.: _The union MBR \(P\) of two MBRs, \(R_{1},R_{2}\), is denoted by \(P=R_{1}\cup R_{2}\); \(P\) satisfies:_  
\[x_{\min}(P)=\min(x_{\min}(R_{1}),x_{\min}(R_{2})) \tag{1}\]  
\[y_{\min}(P)=\min(y_{\min}(R_{1}),y_{\min}(R_{2})) \tag{2}\]  
\[x_{\max}(P)=\max(x_{\max}(R_{1}),x_{\max}(R_{2})) \tag{3}\]  
\[y_{\max}(P)=\max(y_{\max}(R_{1}),y_{\max}(R_{2})) \tag{4}\]  
_where \(\mu(P)\) is the average value of the data in the area denoted by the bottom left corner \((x_{\min}(P),y_{\min}(P))\) and the top right corner \((x_{\max}(P),y_{\max}(P))\), and \(\epsilon(P)\) is the maximum error of the data in the area denoted by the bottom left corner \((x_{\min}(P),y_{\min}(P))\) and the top right corner \((x_{\max}(P),y_{\max}(P))\)._  
The SbMBR tree \(T_{S}\) on \(S\) is defined as follows: Each node of the SbMBR tree contains only one MBR. All the elements of \(S\) are leaf nodes in the SbMBR tree \(T_{S}\). If \(S\) contains only one MBR, \(T_{S}\) contains only one single leaf node; otherwise, we use some packing algorithm mentioned below to partition set \(S\) into some disjointed subsets. Without loss  
Figure 1: An example of SbMBR tree.  
of generality, we assume that set \(S\) is partitioned into \(S_{1},S_{2},\ldots,S_{k}\), where \(\underset{i=1}{\overset{k}{\cup}}S_{i}=S\), \(S_{i}\cap S_{j}=\varnothing,i\
eq j,i,j=1,2,\ldots,k\). Let \(P_{i}=\underset{R\in S_{i}}{\cup}R\), which means that \(P_{i}\) is the union MBR of all elements in \(S_{i}\). Let \(P=\{P_{1},P_{2},\ldots,P_{k}\}\). \(T_{S}\) is derived from the recursive SbMBR tree \(T_{P}\). For each leaf node \(P_{i}\) of the tree \(T_{P}\), let all the elements in \(S_{i}\) be the child nodes of \(P_{i}\), so that \(T_{S}\) is constructed, whose leaf nodes are all in the set \(S\).