# SbMBR Tree--A Spatiotemporal Data Indexing and Compression Algorithm for Data Analysis and Mining
###### Abstract  
In the field of data analysis and mining, adopting efficient data indexing and compression techniques to spatiotemporal data can significantly reduce computational and storage overhead for the abilities to control the volume of data and exploit the spatiotemporal characteristics. However, traditional lossy compression techniques are hardly suitable due to their inherently random nature. They often impose unpredictable damage to scientific data, which affects the results of data mining and analysis tasks that require certain precision. In this paper, we propose a similarity-based minimum bounding rectangle (SbMBR) tree, a tree-based indexing and compression method, to address the aforementioned problem. Our method can hierarchically select appropriate minimum bounding rectangles according to the given maximum acceptable errors and use the average value contained in each selected MBR to replace the original data to achieve data compression with multi-layer loss control. This paper also provides the corresponding tree construction algorithm and range query processing algorithm for the indexing structure mentioned above. To evaluate the data quality preservation in cross-domain data analysis and mining scenarios, we use mutual information as the estimation metric. Experimental results emphasize the superiority of our method over some of the typical indexing and compression algorithms. spatiotemporal data; lossy compression; data indexing; clustering 2023  
[PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], X. Although the QbMBR tree can compress data to a certain extent, it only divides the data in space, and does not consider the similarity of the data itself, nor can it bound error rates [9]. Dimensionality reduction techniques retain some meaningful properties while reducing the volume of data. Unfortunately, they are more suitable to deal with data generated from semantic segmentation rather than from spatiotemporal partitioning since the latter one tends to produce partitions with arbitrary patterns. Therefore, the dimensionality reduction techniques are not directly compatible with the spatiotemporal indexing methods. Zip and 7z represent traditional lossless compression, and their weakness is the low compression ratio as compared to the aforementioned lossy compression methods. Our previous investigation has found that the compression and indexing tasks can be resolved simultaneously [10]. In this paper, we extend our previous study and propose a similarity-based minimum bounding rectangle (SbMBR) tree, a tree-based indexing and compression method to address the aforementioned problems. The main idea of this method is that it divides the space into minimum bounding rectangles according to the similarity of data value and constructs an index tree on this basis. For certain data analysis and mining tasks, the delineated minimum bounding rectangles can not only be queried, decompressed, and restored to the original data, but also be used as low-dimensional features. The main contributions of this paper are listed below:  
1. We introduce a hierarchical indexing structure, which takes full advantage of the feature that adjacent information in some spatiotemporal regions is similar. Building a tree based on local data similarity measurement allows us to control errors precisely for data compression and range query. 2. We propose the tree-building algorithm and range query processing algorithm on the indexing structure mentioned above. We also propose to merge MBRs with the Hilbert curve [11; 12], which further improves the effectiveness of the tree-building process. 3. For particular cross-domain data mining and analysis scenarios, the lossy effect on data utility is effectively estimated via a comparison of mutual information calculated before compression and after reconstruction. 4. We evaluate the proposed algorithms based on actual datasets.