{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:38:16Z","timestamp":1780346296049,"version":"3.54.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p>\n            Data lineage describes the relationship between individual input and output data items of a workflow and is an integral ingredient for both traditional (e.g., debugging or auditing) and emergent (e.g., explanations or cleaning) applications. The core, long-standing problem that lineage systems need to address---and the main focus of this paper---is to quickly capture lineage across a workflow in order to speed up future queries over lineage. Current lineage systems, however, either incur high lineage capture overheads, high lineage query processing costs, or both. In response, developers resort to manual implementations of applications that, in principal, can be expressed and optimized in lineage terms. This paper describes S\n            <jats:sc>moke<\/jats:sc>\n            , an in-memory database engine that provides both fast lineage capture and lineage query processing. To do so, S\n            <jats:sc>moke<\/jats:sc>\n            tightly integrates the lineage capture logic into physical database operators; stores lineage in efficient lineage representations; and employs optimizations if future lineage queries are known up-front. Our experiments on microbenchmarks and realistic workloads show that S\n            <jats:sc>moke<\/jats:sc>\n            reduces the lineage capture overhead and lineage query costs by multiple orders of magnitude as compared to state-of-the-art alternatives. On real-world applications, we show that S\n            <jats:sc>moke<\/jats:sc>\n            meets the latency requirements of interactive visualizations (e.g., &lt; 150ms) and outperforms hand-written implementations of data profiling primitives.\n          <\/jats:p>","DOI":"10.14778\/3184470.3184475","type":"journal-article","created":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T19:50:53Z","timestamp":1581882653000},"page":"719-732","source":"Crossref","is-referenced-by-count":30,"title":["Smoke"],"prefix":"10.14778","volume":"11","author":[{"given":"Fotis","family":"Psallidas","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eugene","family":"Wu","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000024"},{"key":"e_1_2_1_2_1","first-page":"1151","volume-title":"VLDB","author":"Agrawal P.","year":"2006","unstructured":"P. Agrawal , O. Benjelloun , A. D. Sarma , C. Hayworth , S. Nabar , T. Sugihara , and J. Widom . Trio: A system for data, uncertainty, and lineage . In VLDB , pages 1151 -- 1154 , 2006 . P. Agrawal, O. Benjelloun, A. D. Sarma, C. Hayworth, S. Nabar, T. Sugihara, and J. Widom. Trio: A system for data, uncertainty, and lineage. In VLDB, pages 1151--1154, 2006."},{"key":"e_1_2_1_3_1","volume-title":"Algorithms for provisioning queries and analytics. CoRR, abs\/1512.06143","author":"Assadi S.","year":"2015","unstructured":"S. Assadi , S. Khanna , Y. Li , and V. Tannen . Algorithms for provisioning queries and analytics. CoRR, abs\/1512.06143 , 2015 . S. Assadi, S. Khanna, Y. Li, and V. Tannen. Algorithms for provisioning queries and analytics. CoRR, abs\/1512.06143, 2015."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSIA.2017.8339089"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316767"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/108844.108874"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610520"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872802"},{"key":"e_1_2_1_10_1","volume-title":"CIDR","author":"Chen A.","year":"2017","unstructured":"A. Chen , Y. Wu , A. Haeberlen , B. T. Loo , and W. Zhou . Data provenance at internet scale: architecture, experiences, and the road ahead . In CIDR , 2017 . A. Chen, Y. Wu, A. Haeberlen, B. T. Loo, and W. Zhou. Data provenance at internet scale: architecture, experiences, and the road ahead. In CIDR, 2017."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066296"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994530"},{"key":"e_1_2_1_14_1","volume-title":"http:\/\/square.github.io\/crossfilter\/","year":"2015","unstructured":"Crossfilter. http:\/\/square.github.io\/crossfilter\/ , 2015 . Crossfilter. http:\/\/square.github.io\/crossfilter\/, 2015."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055550"},{"key":"e_1_2_1_17_1","volume-title":"CIDR","author":"Deutch D.","year":"2013","unstructured":"D. Deutch , Z. G. Ives , T. Milo , and V. Tannen . Caravan: Provisioning for what-if analysis . In CIDR , 2013 . D. Deutch, Z. G. Ives, T. Milo, and V. Tannen. Caravan: Provisioning for what-if analysis. In CIDR, 2013."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035957"},{"key":"e_1_2_1_19_1","unstructured":"EU GDPR. https:\/\/www.eugdpr.org\/.  EU GDPR. https:\/\/www.eugdpr.org\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000058"},{"key":"e_1_2_1_21_1","volume-title":"http:\/\/bit.ly\/fbfolly","author":"Facebook","year":"2017","unstructured":"Facebook folly. http:\/\/bit.ly\/fbfolly , 2017 . Facebook folly. http:\/\/bit.ly\/fbfolly, 2017."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.15"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056125"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824122"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2041746.2041755"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1357054.1357203"},{"key":"e_1_2_1_29_1","volume-title":"CIDR","author":"Ikeda R.","year":"2011","unstructured":"R. Ikeda , H. Park , and J. Widom . Provenance for generalized map and reduce workflows . In CIDR , 2011 . R. Ikeda, H. Park, and J. Widom. Provenance for generalized map and reduce workflows. In CIDR, 2011."},{"issue":"3","key":"e_1_2_1_30_1","first-page":"42","article-title":"Panda: A system for provenance and data","volume":"33","author":"Ikeda R.","year":"2010","unstructured":"R. Ikeda and J. Widom . Panda: A system for provenance and data . Data Engineering Bulletin , 33 ( 3 ): 42 -- 49 , 2010 . R. Ikeda and J. Widom. Panda: A system for provenance and data. Data Engineering Bulletin, 33(3):42--49, 2010.","journal-title":"Data Engineering Bulletin"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850595"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453925"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732953"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807269"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064049"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054775"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.179"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346452"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12129"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523619"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1476589.1476628"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"issue":"1","key":"e_1_2_1_43_1","first-page":"3","article-title":"Compiling database queries into machine code","volume":"37","author":"Neumann T.","year":"2014","unstructured":"T. Neumann and V. Leis . Compiling database queries into machine code . Data Engineering Bulletin , 37 ( 1 ): 3 -- 11 , 2014 . T. Neumann and V. Leis. Compiling database queries into machine code. Data Engineering Bulletin, 37(1):3--11, 2014.","journal-title":"Data Engineering Bulletin"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.104"},{"key":"e_1_2_1_45_1","unstructured":"Airline On-Time Performance. http:\/\/stat-computing.org\/dataexpo\/2009\/the-data.html.  Airline On-Time Performance. http:\/\/stat-computing.org\/dataexpo\/2009\/the-data.html."},{"key":"e_1_2_1_46_1","unstructured":"Airline On-Time Statistics and Delay Causes. https:\/\/www.transtats.bts.gov\/OT_Delay\/OT_DelayCause1.asp.  Airline On-Time Statistics and Delay Causes. https:\/\/www.transtats.bts.gov\/OT_Delay\/OT_DelayCause1.asp."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598624"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_49_1","unstructured":"Physician Compare National. https:\/\/data.medicare.gov\/data\/physician-compare.  Physician Compare National. https:\/\/data.medicare.gov\/data\/physician-compare."},{"key":"e_1_2_1_50_1","volume-title":"Smoke: Fine-grained lineage at interactive speed. ArXiv e-prints, abs\/1801.07237","author":"Psallidas F.","year":"2018","unstructured":"F. Psallidas and E. Wu . Smoke: Fine-grained lineage at interactive speed. ArXiv e-prints, abs\/1801.07237 , 2018 . F. Psallidas and E. Wu. Smoke: Fine-grained lineage at interactive speed. ArXiv e-prints, abs\/1801.07237, 2018."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078752"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856329"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/832277.834354"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742799"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064024"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367531"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544881"},{"key":"e_1_2_1_60_1","volume-title":"CIDR","author":"Wu E.","year":"2017","unstructured":"E. Wu , F. Psallidas , Z. Miao , H. Zhang , L. Rettig , Y. Wu , and T. Sellam . Combining design and performance in a data visualization management system . In CIDR , 2017 . E. Wu, F. Psallidas, Z. Miao, H. Zhang, L. Rettig, Y. Wu, and T. Sellam. Combining design and performance in a data visualization management system. In CIDR, 2017."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078603"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3184470.3184475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:58:15Z","timestamp":1672225095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3184470.3184475"}},"subtitle":["fine-grained lineage at interactive speed"],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.14778\/3184470.3184475"],"URL":"https:\/\/doi.org\/10.14778\/3184470.3184475","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}