Sorting Compressed Time Series

Compression is commonly used to reduce storage costs in large-scale time series databases. While time series data should be ordered by timestamps, they often arrive out of order due to network delay and thus need to be sorted. However, most existing compression schemes do not support direct swap operations on compressed data, and thus need to decompress for sorting. The challenges of sorting directly the compressed data are the potential space amplification and high time costs when performing swap operations. In this paper, (1) we design the Order-Sensitive Encoding (OSE) method, which not only reduces space usage as the orderliness of the time series improves, but also delivers high encoding and decoding speeds. Based on the space-bound of OSE, (2) we propose the Compressed Bubble Sort (CBS) algorithm, which enables sorting compressed data without space amplification. Notably, it achieves a time complexity of $O(n)$, since the delay of time series data typically follows an exponential distribution. Furthermore, (3) we propose the Compressed Merge Sort (CMS) algorithm for merging two compressed and ordered time series in database compaction. It needs only $O(1)$ time cost by leveraging the ordered nature of data segments, given the exponential delay distribution. The proposed OSE has been implemented as encoding method in Apache TsFile, while CBS and CMS as compressed sorting operators in Apache IoTDB. The experimental results demonstrate that our approach significantly improves both space and time efficiency.