In modern data systems, the primary bottleneck of high-performance computing has shifted away from pure CPU cycles toward data movement and memory bandwidth. When processing massive datasets, traditional architectures pay a heavy "data tax": data must be fetched from storage, transferred across narrow buses, and fully decompressed in memory before any actual computation can begin. As Shanjiang Tang et al. note in their editorial on heterogeneous computing, this cycle of I/O and decompression frequently becomes the dominant system bottleneck. In fact, Jörg Mensmann et al. demonstrate in A GPU-Supported Lossless Compression Scheme for Rendering Time-Varying Volume Data that for highly compressed datasets, the decompression speed itself can choke the entire processing pipeline.
To bypass this bottleneck, a powerful paradigm has emerged: executing mathematical, relational, and analytical operations directly within the compressed domain. Rather than treating compression merely as a passive storage-saving technique, modern algorithms treat compressed structures as first-class computational formats. By rewriting operators to manipulate compressed coefficients, runs, or tokens directly, these systems eliminate decompression overhead and frequently achieve sublinear execution speeds by processing structural shortcuts.
Rewriting Operators for Compressed Encodings
The core intuition behind compressed-domain computation is that structured compression formats contain mathematical properties that can be exploited directly. Instead of expanding a compressed block back into raw tuples or dense arrays, standard relational and mathematical operators can be redesigned to work natively on the encoded representations.
Consider Run-Length Encoding (RLE), which compresses repetitive data into pairs of (value, run_length). In a traditional database, performing a join or intersection requires expanding these runs into individual rows. However, as shown by the authors of GPU Acceleration of SQL Analytics on Compressed Data, specialized parallel algorithms can execute relational operations directly on the RLE segments themselves. By matching the boundaries of the runs rather than individual rows, the computational complexity scales with the number of compressed runs rather than the total row count.
Similarly, for basic data mining primitives like dot products and $p$-norms, Masafumi Oyamada et al. introduce a framework in Compressed Vector Set: A Fast and Space-Efficient Data Mining Framework that processes compressed blocks much like sorted lists in a merge operation. This avoids scalar decompression entirely, transforming mathematical operations into highly efficient block-merging routines.
Traditional Workflow:
[Compressed Data] ──(Decompress)──> [Raw Data] ──(Compute)──> [Result]
Compressed-Domain Workflow:
[Compressed Data] ─────────────────(Compute)────────────────> [Result]
(Scales with compressed blocks/runs)
This principle extends to complex analytical environments:
- Relational Queries: Kaushik Chakrabarti et al. develop a novel query algebra in Approximate Query Processing Using Wavelets that executes selections, projections, and joins directly on multi-dimensional wavelet coefficients, bypassing intermediate materialization.
- Database Formats: Anna Pavlenko et al. analyze how modern analytical engines leverage the structural properties of formats like Parquet and ORC in Data formats in analytical DBMSs: performance trade-offs and future directions, utilizing built-in dictionary encodings to perform filtering and projection directly on encoded values.
Computing via Structural Traversal
When data is compressed into hierarchical or graph-based structures—such as trees, grammars, or decision diagrams—computation can be reframed as a structural traversal. If a dataset contains massive structural redundancy, a well-designed compression format will capture that redundancy as shared nodes or rules. Computing on the compressed format means we only have to evaluate each unique structural element once.
A clear example of this is found in text analytics. In G-TADOC: Enabling Efficient GPU-Based Text Analytics without Decompression, Feng Zhang et al. perform text processing directly over context-free grammar structures represented as Directed Acyclic Graphs (DAGs). Because repetitive text patterns are deduplicated into single grammar rules, a parallel GPU architecture can traverse the DAG and process repeated rules exactly once, avoiding redundant computations across the entire text stream.
This traversal-based computation applies broadly across diverse domains:
- Convex Optimization: In The Symbolic Interior Point Method, Martin Mladenov et al. represent massive constraint matrices as Algebraic Decision Diagrams (ADDs). Standard linear algebra routines, such as matrix-vector multiplications, are executed as recursive-descent traversals over the compressed graph, preventing the memory blowup associated with flattening the matrix.
- Machine Learning Training: Fengan Li et al. apply this to mini-batch Stochastic Gradient Descent in Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent. They execute matrix operations by directly traversing prefix trees and encoded tables, integrating mathematical operations into the data traversal process itself.
- Spreadsheet Dependency Tracking: In Efficient and Compact Spreadsheet Formula Graphs, Dixin Tang et al. apply mathematical functions directly to compressed metadata graphs to determine affected formula nodes during cell updates, turning compression into a direct query acceleration mechanism.
Pushing Compression Through Machine Learning Pipelines
Machine learning workloads are notoriously data-intensive, making them ideal candidates for compressed-domain execution. Rather than compressing data merely for cold storage and decompressing it at the start of an ML pipeline, recent research focuses on pushing compressed formats all the way through feature engineering, split-finding, and model training.
Sebastian Baunsgaard introduces a holistic framework in Morphing-based Compression for Data-centric ML Pipelines that allows data to be "morphed" and reorganized into different workload-optimized compressed formats without ever undergoing full decompression. This end-to-end approach preserves data sparsity and correlation across the entire pipeline, eliminating redundant decompression cycles between independent stages like feature engineering and model training.
Traditional ML Pipeline:
[Compressed Storage] ──> Decompress ──> [Raw Features] ──> Train ──> [Model]
Morphing-Based Pipeline:
[Compressed Storage] ──> Morph Encodings ──> [Compressed Features] ──> Train Directly ──> [Model]
For tree-based models, Firas Abuzaid et al. demonstrate in Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale that split-finding operations can be executed directly on RLE formats. Because the data remains highly compact, the active dataset fits entirely within the processor’s faster cache layers, maximizing CPU cache locality and minimizing high-latency main memory accesses.
For matrix-heavy workloads, Frederick R. Reiss et al. introduce Compressed Linear Algebra (CLA) in Compressed Linear Algebra for Large-Scale Machine Learning. By designing cache-conscious algorithms and specialized encoding formats, they enable fundamental linear algebra operations to run directly on compressed matrix representations, bypassing the typical I/O bottlenecks associated with loading large-scale machine learning datasets.
Domain-Specific Adaptations and Hardware Acceleration
The strategy of computing directly on compressed data spans numerous highly specialized domains, from graph analytics and quantum simulation to time-series processing and custom hardware accelerators.
Graph and Network Analytics
Iterative graph algorithms, such as PageRank and centrality calculations, typically require massive sparse matrix-vector multiplications. Xintian Yang et al. present the SPUR framework in Summarization via Pattern Utility and Ranking: A Novel Framework for Social Media Data Analytics, which executes these iterative multiplications directly on compressed matrix representations. This reduces the total number of required operations and yields significant computational speedups over raw data formats.
Quantum Circuit Simulation
Simulating quantum circuits on classical hardware suffers from exponential memory growth. To combat this, Yuhong Song proposes the Mera framework in Mera: Memory Reduction and Acceleration for Quantum Circuit Simulation via Redundancy Exploration. Mera executes tensor products and matrix-vector multiplications directly on compressed sparse formats without intermediate decompression steps, allowing memory-efficient simulations to achieve substantial speedups rather than suffering from a performance penalty.
Time-Series and Biological Data
In Highly Efficient Direct Analytics on Semantic-aware Time Series Data Compression, Guoyou Sun et al. demonstrate that density-based clustering and outlier detection can be performed directly on compressed time-series streams. Operating directly on the compressed data simplifies the construction of underlying data structures, such as neighborhood graphs, minimizing memory access requirements.
In genomics, Yeremia Gunawan Adhisantoso et al. show in HiCMC: High-Efficiency Contact Matrix Compressor that integrating structural analysis results directly into a compressed biological data stream provides researchers with immediate analytical insights upon decompression, turning the compression process itself into a value-added step.
Hardware Acceleration
The ultimate realization of this paradigm involves embedding compressed-domain processing directly into hardware pipelines. In SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks, Rangharajan Venkatesan et al. present a hardware accelerator that maintains weights and activations in a compressed sparse format throughout the entire processing pipeline—all the way from memory to the multipliers. By avoiding decompression before internal transfers, the design drastically minimizes on-chip data movement, maximizing both computational throughput and energy efficiency.
Key Foundational Work
Approximate Query Processing Using Wavelets (2000) — contributed 2 concept elements to this direction.
Efficacious Data Cube Exploration by Semantic Summarization and Compression (2003) — contributed 2 concept elements to this direction.