In modern data-intensive systems, the primary bottleneck is often not the complexity of a single operation, but the massive redundancy across many operations. Whether processing a batch of graph queries, training neural operators on physical simulations, or monitoring event streams, systems frequently recompute the same intermediate states.
The research direction emerging across these papers is a shift from isolated query execution to amortized computation. By identifying structural overlaps—whether in the form of shared subgraphs, common data subspaces, or recurring temporal patterns—systems can compute a result once and reuse it across thousands of independent tasks.
Exploiting Structural Redundancy in Graphs
Graph-based learning and querying are notoriously expensive due to the combinatorial nature of subgraphs. However, real-world graphs (like molecules or social networks) contain significant local symmetry.
Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancy by Qian Tao and Muhan Zhang demonstrates that nodes in different subgraphs often maintain identical local neighborhoods. Their ENFA framework identifies these "equivalent" states, allowing the system to skip redundant message-passing operations. Similarly, MIMO-LP by Yixin Song "multiplexes" multiple link-prediction queries into a single forward pass, superposing signals into a shared latent space to avoid processing overlapping edges multiple times.
For path enumeration and pattern matching, BatchEnum and TRIC utilize trie-based structures to index and share common sub-paths across a batch of queries, preventing the system from repeatedly traversing the same intermediate vertices.
Multi-Query Optimization in Streaming and Relational Data
In streaming environments, the cost of maintaining private indexes for every query is prohibitive. Shared Arrangements by Frank McSherry et al. introduces a "single-writer, multiple-reader" model where independent dataflows share the same in-memory state. This eliminates the redundant I/O and memory footprint caused by every query independently processing the same input updates.
This philosophy extends to event sequences and relational data:
- Event Streams: SHARON shares intermediate aggregates across multiple sequence queries, avoiding the construction of full event sequences for each.
- Relational Models: SPARE by Benjamin Hilprecht exploits the fact that many records in a database reference the same entities, using "relational pruning" to avoid re-processing identical sub-structures.
Recycling Work Across Mathematical Subspaces
The principle of sharing work is also being applied to scientific computing and unstructured data. When generating training data for neural operators, Sorting Krylov Recycling (SKR) by Hong Wang identifies that related physical problems (like PDEs) share overlapping mathematical subspaces. By intelligently ordering these problems, the system "recycles" the solution from one system to accelerate the next.
In the realm of unstructured data, TASTI and MEME by Daniel Kang replace expensive per-query proxy models with shared semantic indexes. This allows a single embedding-based structure to serve multiple disparate tasks—such as object counting and attribute filtering—amortizing the high cost of deep learning inference across the entire query workload.
Summary of Intuition
The core insight across these 33 papers is that isolation is the enemy of efficiency. By moving from a "query-at-a-time" mindset to a "workload-at-a-time" mindset, these researchers show that we can achieve order-of-magnitude speedups. The mechanism is always the same: identify the shared structural backbone of the work and compute it only once.