{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:45Z","timestamp":1775638485793,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":89,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1350888,CNS-1514520,IIS-1619287,IIS-1816149,CNS-1564287,CFS-1953350,IIS-1801446,"],"award-info":[{"award-number":["CCF-1350888,CNS-1514520,IIS-1619287,IIS-1816149,CNS-1564287,CFS-1953350,IIS-1801446,"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3452802","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"1623-1636","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["At-the-time and Back-in-time Persistent Sketches"],"prefix":"10.1145","author":[{"given":"Benwei","family":"Shi","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"given":"Zhuoyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"given":"Yanqing","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_3_2_2_4_1","volume-title":"FOCS","author":"Alan F.","year":"1998","unstructured":"F. Alan , K. Ravi , and V. Santosh . Fast monte-carlo algorithms for finding low-rank approximations . In FOCS , 1998 . F. Alan, K. Ravi, and V. Santosh. Fast monte-carlo algorithms for finding low-rank approximations. In FOCS, 1998."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.844498"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_3_2_2_7_1","first-page":"1","volume-title":"RANDOM","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , T. S. Jayram , R. Kumar , D. Sivakumar , and L. Trevisan . Counting distinct elements in a data stream . In RANDOM , pages 1 -- 10 , 2002 . Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting distinct elements in a data stream. In RANDOM, pages 1--10, 2002."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095167"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0060"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.136"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_2_17_1","volume-title":"APPROX\/RANDOM","volume":"60","author":"Cohen M. B.","year":"2016","unstructured":"M. B. Cohen , C. Musco , and J. Pachocki . Online row sampling . In APPROX\/RANDOM , volume 60 , 2016 . M. B. Cohen, C. Musco, and J. Pachocki. Online row sampling. In APPROX\/RANDOM, volume 60, 2016."},{"key":"e_1_3_2_2_18_1","volume-title":"ICALP","author":"Cohen M. B.","year":"2016","unstructured":"M. B. Cohen , J. Nelson , and D. P. Woodruff . Optimal approximate matrix product in terms of stable rank . In ICALP , 2016 . M. B. Cohen, J. Nelson, and D. P. Woodruff. Optimal approximate matrix product in terms of stable rank. In ICALP, 2016."},{"key":"e_1_3_2_2_19_1","volume-title":"Proc. International Conference on Very Large Data Bases","author":"Cormode G.","year":"2005","unstructured":"G. Cormode and M. Garofalakis . Sketching streams through the net: Distributed approximate query tracking . In Proc. International Conference on Very Large Data Bases , 2005 . G. Cormode and M. Garofalakis. Sketching streams through the net: Distributed approximate query tracking. In Proc. International Conference on Very Large Data Bases, 2005."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_3_2_2_21_1","volume-title":"Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4(1--3):1--294","author":"Cormode G.","year":"2012","unstructured":"G. Cormode , M. N. Garofalakis , P. J. Haas , and C. Jermaine . Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4(1--3):1--294 , 2012 . G. Cormode, M. N. Garofalakis, P. J. Haas, and C. Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4(1--3):1--294, 2012."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_2_23_1","volume-title":"SODA","author":"Cormode G.","year":"2008","unstructured":"G. Cormode , S. Muthukrishnan , and K. Yi . Algorithms for distributed functional monitoring . In SODA , 2008 . G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. In SODA, 2008."},{"key":"e_1_3_2_2_24_1","volume-title":"ICDE","author":"Cormode G.","year":"2006","unstructured":"G. Cormode , S. Muthukrishnan , and W. Zhuang . What's different: Distributed, continuous monitoring of duplicate-resilient aggregates on data streams . In ICDE , 2006 . G. Cormode, S. Muthukrishnan, and W. Zhuang. What's different: Distributed, continuous monitoring of duplicate-resilient aggregates on data streams. In ICDE, 2006."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368962"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2539943"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316741"},{"key":"e_1_3_2_2_28_1","unstructured":"B. Ding S. Huang S. Chaudhuri K. Chakrabarti and C. Wang. Sample  B. Ding S. Huang S. Chaudhuri K. Chakrabarti and C. Wang. Sample"},{"key":"e_1_3_2_2_29_1","first-page":"679","volume-title":"SIGMOD","year":"2016","unstructured":"seek : Approximating aggregates with distribution precision guarantee . In SIGMOD , pages 679 -- 694 , 2016 . seek: Approximating aggregates with distribution precision guarantee. In SIGMOD, pages 679--694, 2016."},{"key":"e_1_3_2_2_30_1","first-page":"3441","article-title":"Fast approximation of matrix coherence and statistical leverage","volume":"13","author":"Drineas P.","year":"2012","unstructured":"P. Drineas , M. Magdon-Ismail , M. W. Mahoney , and D. P. Woodruff . Fast approximation of matrix coherence and statistical leverage . Journal of Machine Learning Research , 13 : 3441 -- 3472 , 2012 . P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13:3441--3472, 2012.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_2_2_33_1","volume-title":"Priority sampling for estimation of arbitrary subset sums. JACM, 54(32)","author":"Duffield N.","year":"2007","unstructured":"N. Duffield , C. Lund , and M. Thorup . Priority sampling for estimation of arbitrary subset sums. JACM, 54(32) , 2007 . N. Duffield, C. Lund, and M. Thorup. Priority sampling for estimation of arbitrary subset sums. JACM, 54(32), 2007."},{"key":"e_1_3_2_2_34_1","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"Feigenbaum J.","year":"2005","unstructured":"J. Feigenbaum , S. Kannan , A. McGregor , S. Suri , and J. Zhang . Graph distances in the streaming model: The value of space . In Proc. ACM-SIAM Symposium on Discrete Algorithms , 2005 . J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. Graph distances in the streaming model: The value of space. In Proc. ACM-SIAM Symposium on Discrete Algorithms, 2005."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.103"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009718"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514926"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796588"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.93"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989401"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412335"},{"key":"e_1_3_2_2_43_1","volume-title":"ICDE","author":"Jeyashanker S.","year":"2008","unstructured":"S. Jeyashanker , S. Kashyap , R. Rastogi , and P. Shukla . Efficient constraint monitoring using adaptive thresholds . In ICDE , 2008 . S. Jeyashanker, S. Kashyap, R. Rastogi, and P. Shukla. Efficient constraint monitoring using adaptive thresholds. In ICDE, 2008."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998204"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.17"},{"key":"e_1_3_2_2_48_1","first-page":"1975","volume-title":"Proceedings of the Thirty-Second Conference on Learning Theory","volume":"99","author":"Karnin Z.","year":"2019","unstructured":"Z. Karnin and E. Liberty . Discrepancy, coresets, and sketches in machine learning . In Proceedings of the Thirty-Second Conference on Learning Theory , volume 99 of PMLR, pages 1975 -- 1993 , 2019 . Z. Karnin and E. Liberty. Discrepancy, coresets, and sketches in machine learning. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of PMLR, pages 1975--1993, 2019."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367518"},{"key":"e_1_3_2_2_50_1","volume-title":"Proceedings ACM-SIAM Symposium on Discrete Algorithms","author":"Langberg M.","year":"2010","unstructured":"M. Langberg and L. J. Schulman . Universal $eps$-approximators for integrals . In Proceedings ACM-SIAM Symposium on Discrete Algorithms , 2010 . M. Langberg and L. J. Schulman. Universal $eps$-approximators for integrals. In Proceedings ACM-SIAM Symposium on Discrete Algorithms, 2010."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093763"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066295"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.56"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66956"},{"key":"e_1_3_2_2_57_1","first-page":"1452","volume-title":"International Conference on Machine Learning","author":"Lopez-Paz D.","year":"2015","unstructured":"D. Lopez-Paz , K. Muandet , B. Sch\u00f6lkopf , and I. Tolstikhin . Towards a learning theory of cause-effect inference . In International Conference on Machine Learning , pages 1452 -- 1461 , 2015 . D. Lopez-Paz, K. Muandet, B. Sch\u00f6lkopf, and I. Tolstikhin. Towards a learning theory of cause-effect inference. In International Conference on Machine Learning, pages 1452--1461, 2015."},{"key":"e_1_3_2_2_58_1","volume-title":"Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning","author":"Mahoney M. W.","year":"2011","unstructured":"M. W. Mahoney . Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning , NOW Publishers , 3(2), 2011 . M. W. Mahoney. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, NOW Publishers, 3(2), 2011."},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.68"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183737"},{"key":"e_1_3_2_2_67_1","volume-title":"ICALP","author":"Phillips J. M.","year":"2008","unstructured":"J. M. Phillips . Algorithms for $eps$-approximations of terrains. In ICALP , 2008 . J. M. Phillips. Algorithms for $eps$-approximations of terrains. In ICALP, 2008."},{"key":"e_1_3_2_2_68_1","volume-title":"3rd","author":"Phillips J. M.","year":"2016","unstructured":"J. M. Phillips . Coresets and sketches. In 3rd , editor, Handbook of Discrete and Computational Geometry, chapter 48. CRC Press , 2016 . J. M. Phillips. Coresets and sketches. In 3rd, editor, Handbook of Discrete and Computational Geometry, chapter 48. CRC Press, 2016."},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142578"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/1876037.1876072"},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376958"},{"key":"e_1_3_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376681"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.133"},{"key":"e_1_3_2_2_76_1","volume-title":"Proceedings ACM-SIAM Sympoisum on Discrete Algorithms","author":"Tai W. M.","year":"2018","unstructured":"W. M. Tai and J. M. Phillips . Improved coresets for kernel density estimates . In Proceedings ACM-SIAM Sympoisum on Discrete Algorithms , 2018 . W. M. Tai and J. M. Phillips. Improved coresets for kernel density estimates. In Proceedings ACM-SIAM Sympoisum on Discrete Algorithms, 2018."},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.34"},{"key":"e_1_3_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807237"},{"issue":"1","key":"e_1_3_2_2_79_1","first-page":"131","article-title":"Theory and practice of bloom filters for distributed systems","volume":"14","author":"Tarkoma S.","year":"2012","unstructured":"S. Tarkoma , C. E. Rothenberg , and E. Lagerspetz . Theory and practice of bloom filters for distributed systems . IEEE CST , 14 ( 1 ): 131 -- 155 , 2012 . S. Tarkoma, C. E. Rothenberg, and E. Lagerspetz. Theory and practice of bloom filters for distributed systems. IEEE CST, 14(1):131--155, 2012.","journal-title":"IEEE CST"},{"key":"e_1_3_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599929"},{"key":"e_1_3_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749443"},{"key":"e_1_3_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627836"},{"key":"e_1_3_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559820"},{"key":"e_1_3_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2735381"},{"key":"e_1_3_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"},{"key":"e_1_3_2_2_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465319"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452802","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3452802","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3452802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:05Z","timestamp":1750195685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":89,"alternative-id":["10.1145\/3448016.3452802","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3452802","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}