{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:25:35Z","timestamp":1773818735139,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Beijing Natural Science Foundation","award":["4222028"],"award-info":[{"award-number":["4222028"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972401, 61932001, 61832017, and 62072458"],"award-info":[{"award-number":["61972401, 61932001, 61832017, and 62072458"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"PCL","award":["PCL2021A12"],"award-info":[{"award-number":["PCL2021A12"]}]},{"name":"Beijing Outstanding Young Scientist Program","award":["BJJWZYJH012019100020098"],"award-info":[{"award-number":["BJJWZYJH012019100020098"]}]},{"name":"Alibaba Group through Alibaba Innovative Research Program, by CCF-Baidu Open Fund","award":["2021PP15002000"],"award-info":[{"award-number":["2021PP15002000"]}]},{"name":"HKRGC","award":["16201318, 16201819, 16205420"],"award-info":[{"award-number":["16201318, 16201819, 16205420"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            A\n            <jats:italic>persistent data structure<\/jats:italic>\n            , also known as a\n            <jats:italic>multiversion data structure<\/jats:italic>\n            in the database literature, is a data structure that preserves all its previous versions as it is updated over time. Every update (inserting, deleting, or changing a data record) to the data structure creates a new version, while all the versions are kept in the data structure so that any previous version can still be queried.\n          <\/jats:p>\n          <jats:p>Persistent data structures aim at recording all versions accurately, which results in a space requirement that is at least linear to the number of updates. In many of today\u2019s big data applications, in particular, for high-speed streaming data, the volume and velocity of the data are so high that we cannot afford to store everything. Therefore, streaming algorithms have received a lot of attention in the research community, which uses only sublinear space by sacrificing slightly on accuracy.<\/jats:p>\n          <jats:p>\n            All streaming algorithms work by maintaining a small data structure in memory, which is usually called a\n            <jats:italic>sketch<\/jats:italic>\n            ,\n            <jats:italic>summary<\/jats:italic>\n            , or\n            <jats:italic>synopsis<\/jats:italic>\n            . The summary is updated upon the arrival of every element in the stream, thus it is\n            <jats:italic>ephemeral<\/jats:italic>\n            , meaning that it can only answer queries about the current status of the stream. In this article, we aim at designing persistent summaries, thereby giving streaming algorithms the ability to answer queries about the stream at any prior time.\n          <\/jats:p>","DOI":"10.1145\/3531053","type":"journal-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T08:55:27Z","timestamp":1653296127000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Persistent Summaries"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3436-9060","authenticated-orcid":false,"given":"Tianjing","family":"Zeng","sequence":"first","affiliation":[{"name":"Gaoling School of Artificial Intelligence, Renmin University of China, Haidian District, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3620-5086","authenticated-orcid":false,"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Gaoling School of Artificial Intelligence, Renmin University of China, Haidian District, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-4488","authenticated-orcid":false,"given":"Ge","family":"Luo","sequence":"additional","affiliation":[{"name":"Huatai Securities (Shanghai) Asset Management, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5757-9135","authenticated-orcid":false,"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[{"name":"School of Information, Renmin University of China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9777-9676","authenticated-orcid":false,"given":"Ji-Rong","family":"Wen","sequence":"additional","affiliation":[{"name":"Gaoling School of Artificial Intelligence, Renmin University of China, Haidian District, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_3_2_3_2","first-page":"137","volume-title":"J. Comput. Syst. Sci.","author":"Alon N.","year":"1999","unstructured":"N. Alon, Y. Matias, and M. Szegedy. 1999. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58, 1 (1999), 137\u2013147."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_3_2_5_2","unstructured":"Anonymous. Details omitted due to double-blind reviewing."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_3_2_9_2","first-page":"264","volume-title":"VLDB J.","author":"Becker B.","year":"1996","unstructured":"B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. 1996. An asymptotically optimal multiversion B-tree. VLDB J. 5 (1996), 264\u2013275."},{"key":"e_1_3_2_10_2","first-page":"1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916)","author":"Ben-Basat R.","year":"2016","unstructured":"R. Ben-Basat, G. Einziger, R. Friedman, and Y. Kassner. 2016. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916). 1\u20139."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559818"},{"key":"e_1_3_2_12_2","volume-title":"Theoret. Comput. Sci.","author":"Brodal G. S.","year":"2012","unstructured":"G. S. Brodal, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas. 2012. Fully persistent B-trees. Theoret. Comput. Sci. 841 (Nov. 2012), 10\u201326."},{"key":"e_1_3_2_13_2","first-page":"106","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"Carter J. Lawrence","year":"1977","unstructured":"J. Lawrence Carter and Mark N. Wegman. 1977. Universal classes of hash functions. In Proceedings of the ACM Symposium on Theory of Computing. 106\u2013112."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_3_2_16_2","volume-title":"Algorithmica","author":"Chazelle Bernard","year":"1986","unstructured":"Bernard Chazelle and Leonidas Guibas. 1986. Fractional cascading: I. A data structuring technique. In Algorithmica, Vol. 1."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2015.15"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/511334.511376"},{"key":"e_1_3_2_19_2","unstructured":"Edith Cohen Ofir Geri and Rasmus Pagh. 2020. Composable sketches for functions of frequencies: Beyond the worst case. Retrieved from https:\/\/arxiv.org\/abs\/2004.04772."},{"key":"e_1_3_2_20_2","first-page":"58","volume-title":"J. Algor.","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode and S. Muthukrishnan. 2005. An improved data stream summary: The count-min sketch and its applications. J. Algor. 55 (2005), 58\u201375."},{"key":"e_1_3_2_21_2","first-page":"249","volume-title":"ACM Trans. Database Syst.","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode and S. Muthukrishnan. 2005. What\u2019s hot and what\u2019s not: Tracking most frequent items dynamically. ACM Trans. Database Syst. 30 (2005), 249\u2013278."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1341431.1341433"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564699"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12142"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745771"},{"key":"e_1_3_2_27_2","first-page":"79","volume-title":"Proceedings of the International Conference on Very Large Data Bases","volume":"1","author":"Gilbert Anna C.","year":"2001","unstructured":"Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin Strauss. 2001. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Proceedings of the International Conference on Very Large Data Bases, Vol. 1. 79\u201388."},{"key":"e_1_3_2_28_2","volume-title":"Soc. Industr. Appl. Math. J. Sci. Comput.","author":"Guha S.","year":"2009","unstructured":"S. Guha and A. McGregor. 2009. Stream order and order statistics: Quantile estimation in random-order streams. Soc. Industr. Appl. Math. J. Sci. Comput. 38 (2009)."},{"key":"e_1_3_2_29_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Hsu Chen-Yu","year":"2019","unstructured":"Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. 2019. Learning-based frequency estimation algorithms. In Proceedings of the International Conference on Learning Representations. Retrieved from https:\/\/openreview.net\/forum?id=r1lohoCqY7."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.01.027"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_60"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_3_2_33_2","first-page":"51","volume-title":"ACM Trans. Database Syst.","author":"Karp Richard M.","year":"2003","unstructured":"Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou. 2003. A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28 (2003), 51\u201355."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2192447"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066295"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66956"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.56"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287400"},{"key":"e_1_3_2_39_2","first-page":"1095","volume-title":"ACM Trans. Database Syst.","author":"Metwally Ahmed","year":"2006","unstructured":"Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2006. An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Database Syst. 31 (2006), 1095\u20131133."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"J. Misra and D. Gries. 1982. Finding repeated elements. 2 (1982) 143\u2013152.","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_3_2_41_2","first-page":"413","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Muthukrishnan S.","year":"2003","unstructured":"S. Muthukrishnan. 2003. Data streams: Algorithms and applications. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). SIAM, 413."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2010.172"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358758"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183737"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142578"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247503"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13818-8_29"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376681"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.133"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807237"},{"key":"e_1_3_2_51_2","first-page":"391","volume-title":"IEEE Trans. Knowl. Data Eng.","author":"Varman P. J.","year":"1997","unstructured":"P. J. Varman and R. M. Verma. 1997. An efficient multiversion access structure. IEEE Trans. Knowl. Data Eng. 9 (1997), 391\u2013409."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","unstructured":"Hao Wu Junhao Gan and Rui Zhang. 2020. Learning based distributed tracking. Retrieved from https:\/\/arxiv.org\/abs\/2006.12943.","DOI":"10.1145\/3394486.3403255"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531053","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:26Z","timestamp":1750186826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3531053"],"URL":"https:\/\/doi.org\/10.1145\/3531053","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}