Fast Capture of Cell-Level Provenance in Numpy DOI: 3736229.3736269 Conference: Provenance Week @ SIGMOD; June 27, 2025; Berlin, Germany ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Data provenance CCS: Theory of computation Data structures design and analysis
Jinjin Zhao, Sanjay Krishnan · 2025
Read Fast Capture of Cell-Level Provenance in Numpy DOI: 3736229.3736269 Conference: Provenance Week @ SIGMOD; June 27, 2025; Berlin, Germany ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Data provenance CCS: Theory of computation Data structures design and analysis by Jinjin Zhao, Sanjay Krishnan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18255.txt.
Introduction
Jinjin Zhao and Sanjay Krishnan track the origin of every cell in a computed array in a 2025 data systems study. Provenance, knowing which inputs produced which outputs, supports reproducibility and data governance. Capturing it inside a popular array library is hard: interfaces change quickly, operations vary widely, and data sets are huge.
Their prototype annotates arrays at cell level as computations run. Simple memory optimizations cut the delay that annotation adds by a large margin. Cheap provenance would let scientists audit array workflows step by step, instead of trusting a final table whose history is lost.
Catalog record
| CREATOR | Jinjin Zhao, Sanjay Krishnan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-18255
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Capture of Cell-Level Provenance in Numpy DOI: 3736229.3736269 Conference: Provenance Week @ SIGMOD; June 27, 2025; Berlin, Germany ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Data provenance CCS: Theory of computation Data structures design and analysis Jinjin Zhao, Sanjay Krishnan Abstract . Effective provenance tracking enhances reproducibility, governance, and data quality in array workflows. However, significant challenges arise in capturing this provenance, including: (1) rapidly evolving APIs, (2) diverse operation types, and (3) large-scale datasets. To address these challenges, this paper presents a prototype annotation system designed for arrays, which captures cell-level provenance specifically within the numpy library. With this prototype, we explore straightforward memory optimizations that substantially reduce annotation latency. We envision this provenance capture approach for arrays as part of a broader governance system for tracking for structured data workflows and diverse data science applications. 1. Introduction Array-structured programs are ubiquitous in data science tools, such as numpy arrays ( Harris et al. 2020 ) , pandas dataframes ( Wes McKinney 2010 ) , pytorch tensors ( Paszke et al. 2019 ) , spreadsheets, and similar frameworks. Capturing cell-level provenance from array operations can significantly improve the governance, reproducibility, and overall quality of data science pipelines. However, existing data systems still face significant challenges in automatically capturing cell-level provenance. We have identified three key characteristics of modern data pipelines that contribute to these challenges: (1) Changing APIs, (2) Diverse Operations, and (3) Scale of Datasets: (1) Changing APIs. While major data science libraries have stabilized in popularity, their APIs continue to undergo rapid iterations and frequent updates. Changes in the behavior of specific functions directly influence provenance patterns. For example, the shift from pandas version 1.x to 2.x introduced significant changes, including the removal of the ‘inplace=True‘ parameter in certain methods, affecting provenance tracking strategies. Thus, any provenance capture system must be flexible enough to adapt seamlessly to evolving APIs. (2) Diverse Operations. Data science pipelines include a much broader range of operations compared to traditional database operations ( Green et al. 2007 ) . These pipelines frequently involve diverse operations such as complex reshaping (e.g., NumPy’s ‘reshape‘ and ‘transpose‘ functions), convolution functions (e.g., pandas’ ‘apply‘ method), and transformations utilizing machine learning models (e.g., predictions from scikit-learn models). Capturing provenance across these varied operations requires a more generalized and flexible provenance model. (3) Scale of Datasets. The enormous size and dimensionality of contemporary datasets introduce significant complexity to provenance capture. For example, tracking cell-level provenance in large-scale genomics datasets, often containing millions of rows and thousands of columns, can be computationally expensive and storage-intensive. Therefore, efficient provenance capture mechanisms must manage storage overhead, scale effectively, and maintain performance without sacrificing accuracy. In this paper, we discuss our experiences addressing these challenges. Specifically, we describe our implementation of a prototype cell-level provenance capture tool for the numpy library. This tool is part of the larger DSLog system for array provenance management ( Zhao and Krishnan 2024a ) . While DSLog has been previously introduced, this is the first presentation of the tool’s implementation and performance. The core contribution of this paper is demonstrate that efficient memory management can significantly reduce provenance capture overhead, making real-time provenance capture feasible for larger-scale array data operations. Firstly, we demonstrate cell-level provenance by annotating every cell with a dynamic array representing its lineage. Secondly, by sequentially allocating memory for this dynamic array and pre-allocating a memory buffer, we achieve a reduction in annotation latency of up to 275x compared to a naive implementation. Lastly, although our current implementation targets only the numpy library, we conclude by briefly discussing how our approach could be universally extended to other libraries and data types, along with the implications of universal provenance capture systems for data science research. 1.1. Motivating Example Figure 1. Visual illustration of two non-standard array operations common in imaging and scientific applications. Figure 2. Example of provenance capture. Consider an imaging application where a sensor outputs a 2D array representing pixel intensities ranging from 0 to 1. Such scenarios frequently occur in industrial defect detection, thermal imaging, and astronomy. A common analysis involves identifying pixels whose intensities significantly surpass those of their neighbors, signaling potential areas of interest. This analysis can be represented through a simplified array-based pipeline: ⬇ def hotspot ( X ): X_smoothed = smooth ( X ) hotspots = where ( X_smoothed > 0.5) return hotspots Here, smooth(X) applies a smoothing filter (e.g., calculating mean intensity within a neighborhood), and where(condition) generates coordinates for pixels meeting the specified condition. Figure 1 visually demonstrates these operations. From a provenance perspective, users may seek to trace the origin of a detected hotspot back to the original pixels contributing to its detection. Each output pixel identified by the where operation depends on a neighborhood of pixels processed by smooth . Capturing this relationship requires recording precise cell-level provenance, linking each output pixel back to the corresponding region in the input array. DSLog explicitly captures such cell-level provenance via bipartite mappings between input and output array cells. With these mappings, users can efficiently trace any hotspot back to its source pixels. Our prototype provenance capture system, integrated into the numpy library, automatically generates these mappings during pipeline execution. This prototype specifically targets capturing the union of all input cell contributions to output cells. 2. Provenance Capture 2.1. Python Implementation We first introduce our Python implementation of annotation-based provenance capture to demonstrate the core workflow for generating tracking information. We define a custom CellProvenance data type for the numpy library. This data type includes typical scalar data and a list of cell indices indicating dependencies from previous cells. Figure 2 shows an example of the capture workflow with CellProvenance. ⬇ # annotated data type class CellProvenance : data_value : Any parents : List [ Indices ] Before an operation is performed, we first create an array using this data type (1) . Next, we initialize the parents property with the original array indices (2) ; for instance, the top-left cell in the array could be annotated with the index (0, 0). ⬇ # provenance initialization c . parents = [( c . index1 , c . index1 )] Each array operation in the numpy library is extended so that the parents property of the output value becomes the union of the parents properties from the input values (3-4) . This effectively captures lineage information for all numpy operations. ⬇ # provenance operation c . parents = Union ( a . parents , b . parents ) Given an annotated output array with each cell annotated with provenance, DSLog can generate a compressed relational table that represents provenance for that operation. Although relatively straightforward, this implementation addresses two of the three challenges discussed in the introduction. Since our provenance annotations integrate easily with any numpy operation (achievable through simple decorator declarations in Python), it is robust to changing APIs. Moreover, since provenance is captured in real-time at the cell level, it effectively can represent diverse operations. However, this annotation method is computationally intensive because the provenance operation is applied individually to each cell, and it scales poorly as the original array size increases. To improve this, our DSLog implementation more efficiently manages memory operations involved in