SSShaoxu Song

Shaoxu Song

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Shaoxu Song has a total of 114 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Retrieval-Augmented Generation with Covariate Time Series

    by Kenny Ye Liang, Zhongyi Pei, Huan Zhang, Yuhui Liu, Shaoxu Song, Jianmin Wang


  • Open Access

    FLEA: Frequency-based Lossless Encoding Algorithm for Periodic Time Series

    by Tianrui Xia, Jinzhao Xiao, Shaoxu Song

    Existing lossless time series compressors surprisingly ignore the strong periodic pattern, a common characteristic that limits their effectiveness on real-world data. To address this, we design FLEA (Frequency-based Lossless Encoding Algorithm), a novel lossless encoding scheme that exploits the frequency domain for periodic time series. While directly storing the extremely high precision frequency coefficients is obviously not an option to lossless compression, we propose to quantize the frequency coefficients and capture the corresponding low precision residuals in time domain. The core challenge is thus to optimize the trade-off between the encoding costs of the quantized frequency component and its time-domain residual. We address this by modeling it as a rate-optimal search problem, made tractable by an energy-based cost model that guides the global search for the optimal parameter. Moreover, FLEA introduces two adaptive encoders that (1) horizontally partition the frequency component for skewed and sparse coefficients, and (2) vertically partition the residual bit-width for the long-tailed distribution. Extensive experiments on a diverse suite of real-world datasets show that FLEA establishes a new state-of-the-art in compression ratio, particularly on its target periodic data, with an average improvement of 12.9% over the runner-up. Crucially, this is achieved with highly competitive throughput; its efficient decoding, more than twice as fast as its encoding, makes FLEA a powerful and practical solution for read-intensive database workloads, leading to its native implementation in Apache TsFile.

  • Open Access

    Improving LZ4 for Effective Compression and Efficient Query

    by Zhiheng Liu, Shaoxu Song

    LZ4 is a compression algorithm widely adopted in many database systems, which surprisingly has no support for directly querying the compressed data. Existing systems rely on full decompression for query processing, leading to increased query latency. Moreover, the LZ4 compression algorithm has issues like long match dependency, which reduces both compression effectiveness and the efficiency of compressed-data query processing. In this paper, (1) we propose LZV, a compression algorithm that employs a variable-length hash mechanism to identify maximal matches, significantly improving the compression ratio and reducing the compressed-data query overhead. (2) We propose compressed index search method that leverages auxiliary structure to efficiently query compressed data in LZ4 format directly. (3) Leveraging the ordered, quasi-uniformly spaced nature of the key column, we introduce compressed key search method that integrates prediction with binary search to retrieve the corresponding index for a given key efficiently. Finally, we implement the compressed-data query pipeline in Apache TsFile, an open-source KV storage system. Experimental results show that our approach significantly improves compression effectiveness and query efficiency.


  • Open Access

    Quantile Estimation with Duplicates

    by Tianrui Xia, Ziling Chen, Shaoxu Song

    Quantile estimation in data streams is a fundamental task in data analysis. Data structures named quantile sketches are constructed to summarize data and estimate quantiles using limited storage. Duplicate data records often occur in real-world data, while there is no relevant design or analysis in existing quantile sketches, including the best known method KLL sketch. In this paper, we present DupliSketch, a quantile sketch with optimizations for duplicates. The sketch compresses arrival duplicates into elements and performs randomized compaction operations to meet the space limit. To better summarize heavy-tailed data, DupliSketch maintains values frequent enough dynamically and counts them separately, while summarizes other values with weighted elements obtained from compactions. Analyses show its error in rank estimation, space complexity to provide error guarantees under input with duplicates, and time complexity. The approach is deployed as a user-defined function in a database Apache IoTDB. Extensive experiments support the theoretical analyses and compare DupliSketch with existing methods on real and synthetic datasets. On average, the error of the DupliSketch is 44% smaller than that of the baseline methods under the same space limit.

  • Open Access

    Learning Dependency Models for Subset Repair

    by Haoda Li, Jiahui Chen, Yu Sun, Shaoxu Song, Haiwei Zhang, Xiaojie Yuan

    Inconsistent values are commonly encountered in real-world applications, which can negatively impact data analysis and decision-making. While existing research primarily focuses on identifying the smallest removal set to resolve inconsistencies, recent studies have shown that multiple minimum removal sets may exist, making it difficult to make further decisions. While some approaches use the most frequent values as the guidance for the subset repair, this strategy has been criticized for its potential to inaccurately identify errors. To address these issues, we consider the dependencies between attribute values to determine a more appropriate subset repair. Our main contributions include (1) formalizing the optimal subset repair problem with attribute dependencies and analyzing its computational hardness; (2) computing the exact solution using integer linear programming; (3) developing an approximate algorithm with performance guarantees based on cliques and LP relaxation; and (4) designing a probabilistic approach with an approximation bound for efficiency. Experimental results on real-world datasets validate the effectiveness of our methods in both subset repair performance and downstream applications.

  • Open Access

    Sync Without Guesswork: Incomplete Time Series Alignment

    by Ding Jia, Jingyu Zhu, Yu Sun, Aoqian Zhang, Shaoxu Song, Haiwei Zhang, Xiaojie Yuan

    Multivariate time series alignment is critical for ensuring coherent analysis across variables, but missing values and timestamp inconsistencies make this task highly challenging. Existing approaches often rely on prior imputation, which can introduce errors and lead to suboptimal alignments. To address these limitations, we propose a constraint-based alignment framework for incomplete multivariate time series that avoids imputation and ensures temporal and structural consistency. We further design efficient approximation algorithms to balance accuracy and scalability. Experiments on multiple real-world datasets demonstrate that our approach achieves superior alignment quality compared to existing methods under varying missing rates. Our contributions include: (1) formally defining incomplete multiple temporal data alignment problem; (2) proposing three approximation algorithms balancing accuracy and efficiency; and (3) validating our approach on diverse real-world datasets, where it consistently outperforms existing methods in alignment accuracy and the number of aligned tuples.

  • Open Access

    From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies

    by Weiwei Deng, Yu Sun, Shaoxu Song, Xiaojie Yuan

    Spatio-temporal data collected from geographically distributed sources often contain dirty values that affect downstream applications. Temporal data repairing methods, e.g., based on speed constraints, may mistakenly treat sudden changes as errors, although they represent real events and occur simultaneously at multiple locations. Spatial data repairing approaches emphasize value consistency across different locations but ignore temporal pattern similarity. Meanwhile, existing spatio-temporal repairing methods focus more on spatial error correction rather than temporal value repairing across locations. Therefore, we use both temporal and spatial dependencies to identify and repair spatio-temporal errors. Our main contributions are: (1) formalizing the optimal spatio-temporal data repairing problem under constraints and proving its NP-hardness; (2) designing an exact algorithm that decomposes global repair into local decisions with pruning methods; (3) developing two approximate algorithms with theoretical guarantees and probabilities of hitting the optimal solution, where the first explores a wider search space for higher accuracy, and the second uses a greedy sliding-window strategy to improve efficiency; and (4) conducting experiments on nine real-world datasets and downstream applications against eleven baselines, which demonstrate the superiority and practicability of our methods.

  • Open Access

    Cleaning Time Series under Seasonal and Trend Constraints

    by Zijie Chen, Aoqian Zhang, Shaoxu Song

    Time series data are often found to be dirty, e.g., with anomalies or sensor failures. Such dirty data obviously hinder the downstream analysis tasks such as forecasting, clustering or classification. Simply discarding the potentially dirty data points is not an option, making the time series incomplete and incompatible to machine learning models. While many time series data cleaning techniques have been developed in the last decade, e.g., with the help of constraints on value fluctuation, the seasonal features are surprisingly ignored. In this paper, we propose to clean time series by first capturing seasonal and trend constraints, and then enforcing them for cleaning. Unfortunately, directly applying existing seasonal-trend decomposition methods is found imprecise (itself affected by errors) and incomplete (not computed at the beginning or end of the series). Moreover, unlike efficient cleaning with simple value fluctuation constraints, the time series cleaning problem with seasonal and trend constraints is proved to be NP-complete. In this sense, we first improve seasonal and trend filter with tolerance to errors and extension on two directions. Then, an efficient heuristic is designed to iteratively repair the time series and refine the seasonal and trend constraints. The approach has now become a built-in function in a product system Apache IoTDB. Experiments on real-world datasets demonstrate the superiority of our proposal in cleaning seasonal time series and improving downstream applications.

  • Open Access

    LSM-Raft: Optimizing Raft for LSM-tree Store

    by Xiaojian Zhang, Xinyu Tan, Shaoxu Song, Xiangdong Huang, Jianmin Wang

    The Raft consensus algorithm ensures strong consistency by replicating a totally ordered log of operations. However, this strict ordering introduces significant redundancy in databases built on Log-Structured Merge (LSM) trees, where follower-side log transmission and compaction often duplicate storage and computation. In this paper, we present LSM-Raft, a generalized extension of Raft that models the replicated log as a sequence of elements-comprising both atomic entries and compacted SSTables. By aligning log semantics and state machine behavior with LSM-tree principles, LSM-Raft enables more compact and efficient replication while preserving correctness. We generalize Raft's core safety properties to accommodate the relaxed log structure and formally verify them using TLA+. Moreover, we propose a cost-aware synchronization strategy that dynamically replaces delayed raw entries with semantically equivalent SSTables, minimizing transmission and compaction overhead. Experimental results show that LSM-Raft improves overall throughput and significantly reduces resource utilization under real-world workloads, demonstrating its practicality in high-ingest, compaction-intensive environments.


  • Open Access

    Minimum Change≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints

    by Jiahui Chen, Yu Sun, Shaoxu Song, Haiwei Zhang, Xiaojie Yuan

    Erroneous data frequently arise in practical scenarios due to a variety of factors, severely degrading data quality and impeding downstream applications. A widely adopted strategy for error detection is to detect conflicts based on integrity constraints and identify the minimum number of errors, thereby ensuring that the remaining cells satisfy the constraints. However, the minimum change principle may not be applicable in practical scenarios, since errors can occur simultaneously or irregularly. Therefore, this study employs Bayesian statistics to identify erroneous attribute values in conflicting cells that violate inter-attribute dependencies, rather than simply relying on the minimum change principle. This approach ensures that our work neither misses multiple erroneous attribute values conflicting with each other nor mistakenly detects outliers without errors. Furthermore, to address the efficiency issues commonly encountered in constraint-based data cleaning methods, we design 1) parallel conflict detection and error determination methods with the guaranteed parallel scalability, and 2) efficient incremental error detection strategies that can also be executed in parallel with such guarantees. Experiments conducted on various datasets demonstrate the superiority of our error detection methods in terms of both effectiveness and efficiency.