{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T14:59:47Z","timestamp":1788879587549,"version":"build-2803163510"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"JSPS KAKENHI","award":["JP24KJ0461, JP25K22810, JP23K28089, JP22K19802, JP23K24949"],"award-info":[{"award-number":["JP24KJ0461, JP25K22810, JP23K28089, JP22K19802, JP23K24949"]}]},{"name":"JST CREST","award":["JP-MJCR22M2"],"award-info":[{"award-number":["JP-MJCR22M2"]}]},{"DOI":"10.13039\/100009619","name":"AMED","doi-asserted-by":"crossref","award":["JP21zf0127005"],"award-info":[{"award-number":["JP21zf0127005"]}],"id":[{"id":"10.13039\/100009619","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003051","name":"NEDO","doi-asserted-by":"crossref","award":["JPNP20017"],"award-info":[{"award-number":["JPNP20017"]}],"id":[{"id":"10.13039\/501100003051","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>Stream processing enables real-time data analysis. Recent stream processing engines (SPEs) execute stream processing in a distributed manner for real-time analysis of massive amounts of data produced by IoT devices and sensors. It has been widely adopted in various applications that support critical decision making. To explain the results of stream processing, ensuring provenance is indispensable. Provenance clarifies the relationship between input data and output data in the processing. With provenance, we can understand what input data contributed to the output. Existing frameworks for providing provenance for stream processing generate provenance or additional information to construct provenance at runtime. However, these approaches impose substantial overhead in ordinary stream processing. In this paper, we propose a new framework, named LPStream, for fine-grained lazy provenance. LPStream is the first framework to support lazy provenance for stream processing. In the ordinary execution mode, LPStream executes stream processing with checkpointing but without provenance generation. If provenance is necessary for some target output tuples, it replays the processing from an appropriate checkpoint and generates the provenance for the target tuple. We explain the design and implementation of LPStream and evaluate its performance by comparing LPStream with stream processing without provenance and with eager provenance. The experimental results demonstrate the effectiveness of our proposal.<\/jats:p>","DOI":"10.1145\/3749172","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-25","source":"Crossref","is-referenced-by-count":3,"title":["LPStream: Fine-grained Lazy Provenance for Stream Processing"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0096-2827","authenticated-orcid":false,"given":"Masaya","family":"Yamada","sequence":"first","affiliation":[{"name":"University of Tsukuba, Tsukuba, Ibaraki, Japan and National Institute of Advanced Industrial Science and Technology, Koto, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2984-2258","authenticated-orcid":false,"given":"Hiroyuki","family":"Kitagawa","sequence":"additional","affiliation":[{"name":"University of Tsukuba, Tsukuba, Ibaraki, Japan and National Institute of Advanced Industrial Science and Technology, Koto, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2204-8561","authenticated-orcid":false,"given":"Salman Ahmed","family":"Shaikh","sequence":"additional","affiliation":[{"name":"National Institute of Advanced Industrial Science and Technology, Koto, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0595-2230","authenticated-orcid":false,"given":"Toshiyuki","family":"Amagasa","sequence":"additional","affiliation":[{"name":"University of Tsukuba, Tsukuba, Ibaraki, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7242-5126","authenticated-orcid":false,"given":"Akiyoshi","family":"Matono","sequence":"additional","affiliation":[{"name":"National Institute of Advanced Industrial Science and Technology, Koto, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"5th USENIX Workshop on the Theory and Practice of Provenance (TaPP 13)","author":"Akoush Sherif","year":"2013","unstructured":"Sherif Akoush, Ripduman Sohan, and Andy Hopper. 2013. HadoopProv: Towards Provenance as a First Class Citizen in MapReduce. In 5th USENIX Workshop on the Theory and Practice of Provenance (TaPP 13). USENIX Association, Lombard, IL."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/flink.apache.org\/ Retrieved","year":"2024","unstructured":"Apache. 2024a. Flink. https:\/\/flink.apache.org\/ Retrieved June 15, 2024."},{"key":"e_1_2_1_3_1","volume-title":"HDFS Architecture Guide. https:\/\/hadoop.apache.org\/docs\/stable\/hadoop-project-dist\/hadoop-hdfs\/HdfsDesign.html Retrieved","year":"2024","unstructured":"Apache. 2024b. HDFS Architecture Guide. https:\/\/hadoop.apache.org\/docs\/stable\/hadoop-project-dist\/hadoop-hdfs\/HdfsDesign.html Retrieved June 1, 2024."},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/kafka.apache.org\/ Retrieved","year":"2024","unstructured":"Apache. 2024c. Kafka. https:\/\/kafka.apache.org\/ Retrieved June 1, 2024."},{"key":"e_1_2_1_5_1","volume-title":"https:\/\/kafka.apache.org\/documentation\/streams\/ Retrieved","author":"KAFKA","year":"2024","unstructured":"Apache. 2024d. KAFKA STREAMS. https:\/\/kafka.apache.org\/documentation\/streams\/ Retrieved June 15, 2024."},{"key":"e_1_2_1_6_1","volume-title":"2024 e. Spark Streaming Programming Guide. https:\/\/spark.apache.org\/docs\/latest\/streaming-programming-guide.html Retrieved","year":"2024","unstructured":"Apache. 2024 e. Spark Streaming Programming Guide. https:\/\/spark.apache.org\/docs\/latest\/streaming-programming-guide.html Retrieved June 15, 2024."},{"key":"e_1_2_1_7_1","volume-title":"2024 f. Structured Streaming Programming Guide. https:\/\/spark.apache.org\/docs\/latest\/structured-streaming-programming-guide.html Retrieved","year":"2024","unstructured":"Apache. 2024 f. Structured Streaming Programming Guide. https:\/\/spark.apache.org\/docs\/latest\/structured-streaming-programming-guide.html Retrieved June 15, 2024."},{"key":"e_1_2_1_8_1","first-page":"480","volume-title":"Proceedings of the Thirtieth International Conference on Very Large Data Bases -","volume":"30","author":"Arasu Arvind","year":"2004","unstructured":"Arvind Arasu, Mitch Cherniack, Eduardo Galvez, David Maier, Anurag S. Maskey, Esther Ryvkina, Michael Stonebraker, and Richard Tibbetts. 2004. Linear road: a stream data management benchmark. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (VLDB '04). VLDB Endowment, 480-491."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858036.2858408"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44503-X_20"},{"key":"e_1_2_1_11_1","first-page":"379","volume-title":"Foundations and Trends\u00ae in Databases","volume":"1","author":"Cheney James","year":"2009","unstructured":"James Cheney, Laura Chiticariu, and Wang-Chiew Tan. 2009. Provenance in Databases: Why, How, and Where. Foundations and Trends\u00ae in Databases, Vol. 1, 4 (2009), 379-474."},{"key":"e_1_2_1_12_1","volume-title":"Flink and Spark Streaming. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 1789-1792","author":"Chintapalli Sanket","year":"2016","unstructured":"Sanket Chintapalli, Derek Dagit, Bobby Evans, Reza Farivar, Thomas Graves, Mark Holderbaugh, Zhuo Liu, Kyle Nusbaum, Kishorkumar Patil, Boyang Jerry Peng, and Paul Poulosky. 2016. Benchmarking Streaming Computation Engines: Storm, Flink and Spark Streaming. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 1789-1792."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066296"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0083-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_16_1","first-page":"1345","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD'08)","author":"Susan","unstructured":"Susan B. Davidson and Juliana Freire. 2008. Provenance and Scientific Workflows: Challenges and Opportunities. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD'08). 1345-1350."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1939399.1939403"},{"key":"e_1_2_1_18_1","volume-title":"2009 IEEE 25th International Conference on Data Engineering. 174-185","author":"Glavic B.","unstructured":"B. Glavic, and G. Alonso. 2009. Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting. In 2009 IEEE 25th International Conference on Data Engineering. 174-185."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488222.2488256"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3427796.3433931"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0486-1"},{"key":"e_1_2_1_22_1","first-page":"118","article-title":"Inferring Fine-Grained Data Provenance in Stream Data Processing: Reduced Storage Cost, High Accuracy","author":"Huq Mohammad Rezwanul","year":"2011","unstructured":"Mohammad Rezwanul Huq, Andreas Wombacher, and Peter M. G. Apers. 2011. Inferring Fine-Grained Data Provenance in Stream Data Processing: Reduced Storage Cost, High Accuracy. In Database and Expert Systems Applications. 118-127.","journal-title":"Database and Expert Systems Applications."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850595"},{"key":"e_1_2_1_24_1","volume-title":"TLC Trip Record Data. https:\/\/www.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page Retrieved","author":"New York City","year":"2024","unstructured":"City of New York. 2024. TLC Trip Record Data. https:\/\/www.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page Retrieved August 16, 2024."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102552"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430928"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565825"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184475"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/RCIS.2012.6240427"},{"key":"e_1_2_1_30_1","volume-title":"https:\/\/rocksdb.org\/ Retrieved","author":"Source Meta Open","year":"2024","unstructured":"Meta Open Source. 2024a. RocksDB. https:\/\/rocksdb.org\/ Retrieved June 1, 2024 from"},{"key":"e_1_2_1_31_1","unstructured":"Open Source. 2024b. LPStream Implementation. https:\/\/github.com\/madamaya\/lpstream"},{"key":"e_1_2_1_32_1","volume-title":"Nexmark-a benchmark for queries over data streams (draft). Technical report","author":"Tucker Pete","year":"2008","unstructured":"Pete Tucker, Kristin Tufte, Vassilis Papadimos, and David Maier. 2008. Nexmark-a benchmark for queries over data streams (draft). Technical report (2008)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.2978480"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3102645"},{"key":"e_1_2_1_35_1","volume-title":"EDA-PS Workshop.","author":"Vijayakumar Nithya","year":"2007","unstructured":"Nithya Vijayakumar and Beth Plale. 2007. Tracking stream provenance in complex event processing systems for workflow-driven computing. In EDA-PS Workshop."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11890850_6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248054.1248082"},{"key":"e_1_2_1_38_1","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE). 865-876","author":"Wu E.","unstructured":"E. Wu, S. Madden, , and M. Stonebraker. 2013. SubZero: A fine-grained lineage system for scientific databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 865-876."},{"key":"e_1_2_1_39_1","volume-title":"streaming-benchmarks. https:\/\/github.com\/yahoo\/streaming-benchmarks Retrieved","year":"2024","unstructured":"yahoo. 2022. streaming-benchmarks. https:\/\/github.com\/yahoo\/streaming-benchmarks Retrieved August 26, 2024."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00769-7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.3390\/app11125523"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303758"},{"key":"e_1_2_1_43_1","volume-title":"Fine-Grained Provenance for Matching & ETL. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 184-195","author":"Zheng N.","unstructured":"N. Zheng, A. Alawini, and Z. G. Ives. 2019. Fine-Grained Provenance for Matching & ETL. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 184-195."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:33:43Z","timestamp":1781325223000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749172"],"URL":"https:\/\/doi.org\/10.1145\/3749172","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}