Computer scientists have designed and evaluated a query-native storage framework named SparseCalib that substantially compresses large-scale system provenance graphs while maintaining lossless data preservation and accelerating forensic analysis routines. Provenance graphs have become a fundamental data representation for enterprise security auditing and advanced persistent threat investigations because they systematically record fine-grained causal dependencies among running processes, file modifications, and network communications across operating system components. However, continuously recording these high-velocity system interactions generates vast volumes of structured graph data that rapidly overwhelm conventional database storage and severely degrade query responsiveness when forensic analysts attempt to investigate complex, multi-stage cyberattacks.
To overcome the acute storage overhead and latency bottlenecks inherent in long-term audit logs, the research team structured SparseCalib around the empirical access patterns commonly executed during security incident investigations. Security analysts rarely require the materialization or sequential scanning of an entire multi-gigabyte provenance graph before beginning forensic triage. Instead, typical investigative workflows follow a target-centric lifecycle that begins with point-of-interest filtering to identify suspicious system entities from alerts or log artifacts, followed by directional traversals across causal edges. Specifically, investigators perform backward tracing to explore incoming dependencies and locate original attack entry points, and forward tracing to evaluate outgoing causal effects, assess downstream compromise, and track lateral movement across enterprise assets.
Existing provenance storage approaches struggle to satisfy lossless audit preservation, compact physical storage, and rapid multi-scenario query execution at the same time. Lossy causal reduction and semantic pruning methods discard seemingly redundant events or temporary objects, but removing such edges risks breaking critical attack chains and producing false negatives during post-incident investigations. Conversely, lossless approaches such as general-purpose compressors impose heavy decompression latencies before answering queries, while standard graph databases like Neo4j incur heavy disk footprints due to extensive indexing structures. Recent learned compression architectures such as Leonard and Dehydrator train neural models to predict graph structure, yet their auxiliary calibration files require substantial disk space and compute time to correct prediction errors, while also lacking complete bidirectional tracing capabilities.
SparseCalib resolves these trade-offs by physically decomposing the incoming provenance graph into three distinct, query-aligned substructures rather than treating storage as a monolithic compression challenge. The framework constructs a dedicated NODEATTR store that maps unique attribute identifiers to the nodes possessing those values, a FORWARD store that maps source entities to their complete outgoing operational events, and an asymmetric BACKWARD accelerator that maps destination entities directly to their distinct predecessor nodes. Crucially, the BACKWARD structure deduplicates reverse connections to speed up upstream traversals, leaving the complete event types, timestamps, and interaction multiplicities preserved losslessly inside the FORWARD component. This asymmetric co-design ensures that security queries can execute locally against specialized artifacts without materializing the broader provenance graph.
To guarantee that these decomposed graph records occupy minimal disk footprint while remaining directly addressable, SparseCalib applies field-level redundancy reduction followed by structural normalization. Variable-length string attributes, including repetitive process names, executable paths, and operational tags, are converted into compact fixed-length numerical identifiers via a persistent global reference dictionary. In parallel, numerical temporal fields are compressed using monotonic delta encoding, where initial timestamps are retained in full precision while subsequent entries record only narrow positive increments that can be quickly reconstructed through cumulative summation. Structural normalization then flattens irregular one-to-many graph relationships into uniform one-to-one record arrays ordered deterministically by grouping keys, establishing a continuous position space suitable for vectorization.
To enable direct, reconstruction-free record localization across flattened tables without introducing ambiguous one-to-many lookups, the system reformulates record addressing into deterministic input-output pairs by introducing an occurrence sequence counter. Under this learning objective, an input tuple combining the query identifier and an occurrence sequence index maps deterministically to an exact storage position within the normalized array, reserving an occurrence index of zero to retrieve the total record count for cardinality estimation. This mathematical formulation allows a specialized neural architecture to execute learned position mapping. The system partitions each substructure by its primary query keys and deploys localized models, effectively trading broader global generalization for localized memorization accuracy while keeping model parameter footprints small.
At the architectural core of this learned indexing mechanism sits the Binary Hashing Multi-gate Mixture-of-Experts model, known as BiHash-MMoE. Because discrete record positions lack meaningful numerical continuity, standard regression techniques fail when retrieving precise storage addresses, while monolithic multi-class classification over millions of output addresses would require prohibitive softmax computations. SparseCalib addresses this by decomposing the target integer position into contiguous binary segments, predicting each segment through independent classification heads. The network incorporates binary code-based hash embeddings to decouple embedding capacity from large input identifier cardinalities, while a multi-gate mixture-of-experts structure routes input signals across task-specific private experts and shared representations to capture structural dependencies without inflating model weights.
To satisfy the strict lossless preservation mandate required for forensic auditing, SparseCalib couples its learned model with an exhaustive mapping error calibration layer that guarantees exact position resolution. Following training, the framework exhaustively verifies every predicted position against ground-truth array coordinates, storing only the mismatched entries in an auxiliary integer calibration array. During warm query execution, vectorized binary search checks incoming batched keys against the sorted calibration entries in logarithmic time, instantaneously replacing any inaccurate model prediction with the verified coordinate before retrieving disk records. In the evaluated benchmarks, SparseCalib reached over ninety-nine percent initial training accuracy across partitions, allowing the resulting calibration layer to average just 0.23 megabytes, or 0.68 percent of total storage space.
Experimental evaluations conducted across five provenance graph instances constructed from the DARPA Transparent Computing Engagement #5 CADETS log family demonstrated marked storage and latency advantages over existing baselines. Compared to the general-purpose graph database Neo4j, SparseCalib reduced total persistent space overhead by an average of 97.2 percent across all five datasets. When measured against the specialized lossless learned baselines Dehydrator and Leonard, SparseCalib lowered on-disk storage by an average of 64.8 percent and 96.4 percent, respectively. Furthermore, testing parameter storage precision revealed that saving model checkpoints in half-precision floating-point format achieved nearly identical inference accuracy to full precision, with a maximum absolute accuracy discrepancy of only 0.0038, enabling additional reductions in parameter footprint.
The framework also demonstrated substantial speedups in query efficiency across point-of-interest filtering, forward tracing, and backward tracing workloads under varying batch configurations. In point-of-interest evaluations querying up to 10,000 sampled attribute keys, SparseCalib yielded lower warm batch latencies than both Leonard and Neo4j across 499 of 505 evaluated conditions, achieving a response time of 0.09 seconds on the first dataset at maximum batch size compared to 0.39 seconds for Leonard and 0.47 seconds for Neo4j. In backward tracing tests with 2,000 queried starting points, SparseCalib recorded a mean latency of 0.147 seconds across the five graphs, markedly outperforming Neo4j at 22.317 seconds and Dehydrator at 146.537 seconds.
While SparseCalib achieves pronounced storage compression and high-throughput query execution, the authors noted specific architectural boundaries and scope limitations. The current implementation is designed as a static construction pipeline optimized for offline retention windows; streaming updates, incremental record insertions, and live graph mutations are not supported without retraining or repartitioning. Moreover, high query throughput relies on loading models, normalized arrays, and calibration structures into GPU memory, making resident hardware capacity a critical deployment factor. The researchers emphasized that extending the architecture to support continuous online log streaming, exploring CPU-only execution paths, and validating performance across broader enterprise log distributions represent necessary directions for future provenance storage research.
Subject of Research: Query-native storage and learned position mapping for system provenance graphs
Article Title: SparseCalib: a reconstruction-free query-oriented storage framework for provenance graphs
Article References: Tang, R., Shen, G., Guo, C., Cui, Y., & Chen, Y. (2026). SparseCalib: a reconstruction-free query-oriented storage framework for provenance graphs. Journal of King Saud University Computer and Information Sciences, 38(10), Article 1031. https://doi.org/10.1007/s44443-026-01439-2
Image Credits: AI Generated
DOI: 10.1007/s44443-026-01439-2
Keywords: SparseCalib, provenance graphs, system auditing, APT investigation, threat detection, graph storage, learned indexing, BiHash-MMoE, causal dependencies, point-of-interest filtering, forward tracing, backward tracing, Transparent Computing, data compression, structural normalization, forensic analysis
News Source: Denise Maddox. (November 20, 2026). Query Native Storage Cuts Provenance Graph Footprint While Accelerating Forensic Searches. Scienmag.



