# S2p: Provenance Research for Stream Processing System
## 9 Related Work
### Runtime Overhead Optimization  
In the end, we will summarize the existing optimization solutions to avoid excessive runtime overhead when the normal big data systems are extended with provenance capability, shown in Table 6.  
One solution to minimize the negative impact on the original system is source data sampling to constrain the data size that will be tracked. Provenance solutions such as tracing framework [32; 33] adopt this strategy. It leads to relatively little performance degradation for some specific scenarios (e.g., performance bottleneck detection) by adjusting the sampling rate. However, the sampling strategy is essentially weak in other scenarios (e.g., trial-and-error debugging) where provenance for all data is required.  
Unlike the previous strategy that focuses on the source data, another one is to reduce intermediate data by trimming the provenance data or discarding unnecessary intermediate  
\begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Optimization Strategies** & **Provenance Systems** & **Target** \\ \hline Source data sampling & Tracing Framework [32; 33] & Processing Time \\ \hline Fixed-size provenance annotation & GeneLog [4; 24] & Latency/Throughput \\ \hline  & Newt [29] & Processing Time \\ \cline{2-3}  & Titian [19] & Processing Time \\ \cline{2-3} Intermediate data reduction & Arthur [31] & Processing Time \\ \cline{2-3}  & On-the-fly provenance tracking [34] & Throughput \\ \hline Generate provenance & Ariadne [22; 23] & Processing Time \\ \hline \hline \end{tabular}
\end{table}
Table 6: Optimization solutions to reduce runtime overhead for big data provenance.  
data. It can be further divided into two strategies, i.e., fixed-size provenance annotation and intermediate data reduction.  
As for the fixed-size provenance annotation strategy, it always incurs a minimal, constant size overhead for each data. However, this strategy is not generally applicable. Taking GeneALog [4; 24] as an example, it assumes a strict temporal order for both input and output data. This kind of assumption does not always hold for modern DSP systems.  
In terms of intermediate data reduction, it is a commonly adopted strategy. It usually works with selectively replaying data processing so that fewer data are required to record in the runtime. It also works for some specific provenance problems (e.g., why-provenance) where intermediate data are not directly involved in the provenance query results. However, deterministic data processing is required for many replaying related solutions. Intermediate data reduction may lack the capability to support a fine-grained provenance analysis where intermediate results may contribute to the provenance results.  
Generating provenance lazily is also working as an option to reduce overhead. It works by decoupling the provenance analysis from the original data process. For big data systems, especially DSP systems, which are required to deal with data at high rates and low latency, eager provenance generation will always incur significant overhead. However, this strategy needs to store source data and intermediate data temporarily to construct the provenance further. This may potentially bring in a storage burden for large-scale data processing applications.