Reproduce “Learned Compression of Nonlinear Time Series With Random Access” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Andrea Guerra, Giorgio Vinciguerra, Antonio Boffa, Paolo Ferragina
NeaTS introduces a compression scheme for nonlinear time series, providing efficient random access through error-bounded nonlinear functional approximations and an optimal partitioning algorithm. The approach achieves high compression ratios, fast sequential decompression, and rapid random access, outperforming existing methods on various real-world datasets.
Key insights
- The classic O'Rourke's algorithm for optimal piecewise linear approximation can be generalized to various nonlinear functions by transforming the approximation problem into a linear system in a 2D parameter space.
- Global optimal partitioning of a time series for compression, considering multiple nonlinear function types and error bounds, is solvable via a shortest path algorithm on a directed acyclic graph, with O(n log ∆) time complexity.
- Combining error-bounded nonlinear functional approximations with tailored succinct data structures enables a solution that concurrently optimizes compression ratio, sequential decompression speed, and random access efficiency for time series.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.