{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:25:07Z","timestamp":1755998707143,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,6,3]],"date-time":"2021-06-03T00:00:00Z","timestamp":1622678400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,3]],"date-time":"2021-06-03T00:00:00Z","timestamp":1622678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s00778-021-00668-3","type":"journal-article","created":{"date-parts":[[2021,6,3]],"date-time":"2021-06-03T12:03:21Z","timestamp":1622721801000},"page":"933-957","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["In-order sliding-window aggregation in worst-case constant time"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9775-8165","authenticated-orcid":false,"given":"Kanat","family":"Tangwongsan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hirzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,3]]},"reference":[{"key":"668_CR1","unstructured":"Apache Flink: Scalable batch and stream data processing. https:\/\/flink.apache.org (2016). Retrieved Aug 2016"},{"key":"668_CR2","unstructured":"adamax: Re: Implement a queue in which $$\\text{push}\\_\\text{ rear }(), \\text{ pop }\\_\\text{ front }() \\, \\text{ and }\\, \\text{ get }\\_\\text{ min }()$$ are all constant time operations. http:\/\/stackoverflow.com\/questions\/4802038\/ (2011). Retrieved Aug (2016)"},{"key":"668_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Cormode, G., Huang, Z., Phillips, J., Wei, Z., Yi, K.: Mergeable summaries. In: Symposium on Principles of Database Systems (PODS), pp. 23\u201334 (2012)","DOI":"10.1145\/2213556.2213562"},{"key":"668_CR4","doi-asserted-by":"crossref","unstructured":"Akidau, T., Balikov, A., Bekiroglu, K., Chernyak, S., Haberman, J., Lax, R., McVeety, S., Mills, D., Nordstrom, P., Whittle, S.: MillWheel: Fault-tolerant stream processing at internet scale. In: Conference on Very Large Data Bases (VLDB) Industrial Track, pp. 734\u2013746 (2013)","DOI":"10.14778\/2536222.2536229"},{"key":"668_CR5","doi-asserted-by":"crossref","unstructured":"Ali, M., Chandramouli, B., Goldstein, J., Schindlauer, R.: The extensibility framework in Microsoft StreamInsight. In: International Conference on Data Engineering (ICDE), pp. 1242\u20131253 (2011)","DOI":"10.1109\/ICDE.2011.5767878"},{"key":"668_CR6","doi-asserted-by":"crossref","unstructured":"Arasu, A., Widom, J.: Resource sharing in continuous sliding window aggregates. In: Conference on Very Large Data Bases (VLDB), pp. 336\u2013347 (2004)","DOI":"10.1016\/B978-012088469-8.50032-2"},{"issue":"7","key":"668_CR7","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM (CACM) 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM (CACM)"},{"key":"668_CR8","doi-asserted-by":"publisher","first-page":"3107","DOI":"10.1007\/s10115-020-01444-5","volume":"62","author":"S Bou","year":"2020","unstructured":"Bou, S., Kitagawa, H., Amagasa, T.: L-BiX: incremental sliding-window aggregation over data streams using linear bidirectional aggregating indexes. J. Knowl. Inf. Syst. (KAIS) 62, 3107\u20133131 (2020)","journal-title":"J. Knowl. Inf. Syst. (KAIS)"},{"key":"668_CR9","doi-asserted-by":"crossref","unstructured":"Boykin, O., Ritchie, S., O\u2019Connell, I., Lin, J.: Summingbird: A framework for integrating batch and online MapReduce computations. In: Conference on Very Large Data Bases (VLDB), pp. 1441\u20131451 (2014)","DOI":"10.14778\/2733004.2733016"},{"key":"668_CR10","doi-asserted-by":"crossref","unstructured":"Carbone, P., Traub, J., Katsifodimos, A., Haridi, S., Markl, V.: Cutty: Aggregate sharing for user-defined windows. In: Conference on Information and Knowledge Management (CIKM), pp. 1201\u20131210 (2016)","DOI":"10.1145\/2983323.2983807"},{"key":"668_CR11","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd Edn. MIT Press (2009). http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"issue":"1","key":"668_CR12","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"668_CR13","doi-asserted-by":"crossref","unstructured":"Cranor, C., Johnson, T., Spataschek, O., Shkapenyuk, V.: Gigascope: A stream database for network applications. In: International Conference on Management of Data (SIGMOD) Industrial Track, pp. 647\u2013651 (2003)","DOI":"10.1145\/872757.872838"},{"key":"668_CR14","unstructured":"DEBS 2012 Grand Challenge: Manufacturing equipment. https:\/\/debs.org\/grand-challenges\/2012. Retrieved June 2020"},{"key":"668_CR15","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Fusy, E., Gandouet, O., Meunier, F.: HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm. In: Conference on Analysis of Algorithms (AofA), pp. 127\u2013146 (2007)","DOI":"10.46298\/dmtcs.3545"},{"key":"668_CR16","doi-asserted-by":"crossref","unstructured":"Gedik, B.: Generic windowing support for extensible stream processing systems. Software Practice and Experience (SP&E) pp. 1105\u20131128 (2013)","DOI":"10.1002\/spe.2194"},{"issue":"2","key":"668_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/3299887.3299892","volume":"47","author":"M Hirzel","year":"2018","unstructured":"Hirzel, M., Baudart, G., Bonifati, A., Della Valle, E., Sakr, S., Vlachou, A.: Stream processing languages in the big data era. SIGMOD Record 47(2), 29\u201340 (2018)","journal-title":"SIGMOD Record"},{"key":"668_CR18","doi-asserted-by":"crossref","unstructured":"Hirzel, M., Rabbah, R., Suter, P., Tardieu, O., Vaziri, M.: Spreadsheets for stream processing with unbounded windows and partitions. In: Conference on Distributed Event-Based Systems (DEBS), pp. 49\u201360 (2016)","DOI":"10.1145\/2933267.2933607"},{"issue":"1","key":"668_CR19","first-page":"51","volume":"39","author":"M Hirzel","year":"2017","unstructured":"Hirzel, M., Schneider, S., Gedik, B.: SPL: an extensible language for distributed stream processing. Trans Program Lang Syst (TOPLAS) 39(1), 51\u2013539 (2017)","journal-title":"Trans Program Lang Syst (TOPLAS)"},{"key":"668_CR20","doi-asserted-by":"crossref","unstructured":"Hirzel, M., Schneider, S., Tangwongsan, K.: Tutorial: sliding-window aggregation algorithms. In: Conference on Distributed Event-Based Systems (DEBS), pp. 11\u201314 (2017)","DOI":"10.1145\/3093742.3095107"},{"key":"668_CR21","unstructured":"Izbicki, M.: Algebraic classifiers: a generic approach to fast cross-validation, online training, and parallel training. In: International Conference on Machine Learning (ICML), pp. 648\u2013656 (2013)"},{"key":"668_CR22","doi-asserted-by":"crossref","unstructured":"Jugel, U., Jerzak, Z., Hackenbroich, G., Markl, V.: M4: A visualization-oriented time series data aggregation. In: Conference on Very Large Data Bases (VLDB), pp. 797\u2013808 (2014)","DOI":"10.14778\/2732951.2732953"},{"key":"668_CR23","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, S., Franklin, M.J., Davis, J., Farina, D., Golovko, P., Li, A., Thombre, N.: Continuous analytics over discontinuous streams. In: International Conference on Management of Data (SIGMOD), pp. 1081\u20131092 (2010)","DOI":"10.1145\/1807167.1807290"},{"key":"668_CR24","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, S., Wu, C., Franklin, M.: On-the-fly sharing for streamed aggregation. In: International Conference on Management of Data (SIGMOD), pp. 623\u2013634 (2006)","DOI":"10.1145\/1142473.1142543"},{"key":"668_CR25","doi-asserted-by":"crossref","unstructured":"Kulkarni, S., Bhagat, N., Fu, M., Kedigehalli, V., Kellogg, C., Mittal, S., Patel, J.M., Ramasamy, K., Taneja, S.: Twitter Heron: stream processing at scale. In: International Conference on Management of Data (SIGMOD), pp. 239\u2013250 (2015)","DOI":"10.1145\/2723372.2742788"},{"issue":"1","key":"668_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/1058150.1058158","volume":"34","author":"J Li","year":"2005","unstructured":"Li, J., Maier, D., Tufte, K., Papadimos, V., Tucker, P.A.: No pane, no gain: efficient evaluation of sliding-window aggregates over data streams. ACM SIGMOD Record 34(1), 39\u201344 (2005)","journal-title":"ACM SIGMOD Record"},{"key":"668_CR27","doi-asserted-by":"crossref","unstructured":"Murray, D.G., McSherry, F., Isaacs, R., Isard, M., Barham, P., Abadi, M.: Naiad: a timely dataflow system. In: Symposium on Operating Systems Principles (SOSP) (2013)","DOI":"10.1145\/2517349.2522738"},{"issue":"4","key":"668_CR28","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1017\/S0956796800001489","volume":"5","author":"C Okasaki","year":"1995","unstructured":"Okasaki, C.: Simple and efficient purely functional queues and deques. J. Funct. Program. (JFP) 5(4), 583\u2013592 (1995)","journal-title":"J. Funct. Program. (JFP)"},{"key":"668_CR29","doi-asserted-by":"crossref","unstructured":"Schneider, S., Gedik, B., Hirzel, M.: Tutorial: stream processing optimizations. In: Conference on Distributed Event-Based Systems (DEBS), pp. 249\u2013258 (2013)","DOI":"10.1145\/2488222.2488268"},{"issue":"4","key":"668_CR30","first-page":"61","volume":"38","author":"S Schneider","year":"2016","unstructured":"Schneider, S., Gedik, B., Hirzel, M.: Language runtime and optimizations in IBM Streams. Bull. IEEE Comput. Soc. Tech. Committee Data Eng. 38(4), 61\u201372 (2016)","journal-title":"Bull. IEEE Comput. Soc. Tech. Committee Data Eng."},{"issue":"2","key":"668_CR31","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1109\/TC.2013.221","volume":"64","author":"S Schneider","year":"2015","unstructured":"Schneider, S., Hirzel, M., Gedik, B., Wu, K.L.: Safe data parallelism for general streaming. IEEE Trans. Comput. (TC) 64(2), 504\u2013517 (2015)","journal-title":"IEEE Trans. Comput. (TC)"},{"key":"668_CR32","doi-asserted-by":"crossref","unstructured":"Shein, A.U., Chrysanthis, P.K., Labrinidis, A.: FlatFIT: Accelerated incremental sliding-window aggregation for real-time analytics. In: Conference on Scientific and Statistical Database Management (SSDBM), pp. 5.1\u20135.12 (2017)","DOI":"10.1145\/3085504.3085509"},{"key":"668_CR33","unstructured":"Shein, A.U., Chrysanthis, P.K., Labrinidis, A.: SlickDeque: High throughput and low latency incremental sliding-window aggregation. In: Conference on Extending Database Technology (EDBT), pp. 397\u2013408 (2018)"},{"key":"668_CR34","doi-asserted-by":"crossref","unstructured":"Srivastava, U., Widom, J.: Flexible time management in data stream systems. In: Principles of Database Systems (PODS), pp. 263\u2013274 (2004)","DOI":"10.1145\/1055558.1055596"},{"key":"668_CR35","unstructured":"Tangwongsan, K., Hirzel, M., Schneider, S.: Constant-time sliding window aggregation. Tech. Rep. RC25574, IBM Research (2015)"},{"key":"668_CR36","doi-asserted-by":"crossref","unstructured":"Tangwongsan, K., Hirzel, M., Schneider, S.: Low-latency sliding-window aggregation in worst-case constant time. In: Conference on Distributed Event-Based Systems (DEBS), pp. 66\u201377 (2017)","DOI":"10.1145\/3093742.3093925"},{"key":"668_CR37","doi-asserted-by":"crossref","unstructured":"Tangwongsan, K., Hirzel, M., Schneider, S.: Optimal and general out-of-order sliding-window aggregation. In: Conference on Very Large Data Bases (VLDB), pp. 1167\u20131180 (2019)","DOI":"10.14778\/3339490.3339499"},{"key":"668_CR38","doi-asserted-by":"crossref","unstructured":"Tangwongsan, K., Hirzel, M., Schneider, S., Wu, K.L.: General incremental sliding-window aggregation. In: Conference on Very Large Data Bases (VLDB), pp. 702\u2013713 (2015)","DOI":"10.14778\/2752939.2752940"},{"key":"668_CR39","unstructured":"Theodorakis, G., Koliousis, A., Pietzuch, P.R., Pirk, H.: Hammer slide: work- and CPU-efficient streaming window aggregation. In: Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS), pp. 34\u201341 (2018)"},{"key":"668_CR40","unstructured":"Theodorakis, G., Koliousis, A., Pietzuch, P.R., Pirk, H.: LightSaber: efficient window aggregation on multi-core processors. In: International Conference on Management of Data (SIGMOD), pp. 2505\u20132521 (2020). https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3389753"},{"key":"668_CR41","unstructured":"Theodorakis, G., Pietzuch, P.R., Pirk, H.: SlideSlide: A fast incremental stream processing algorithm for multiple queries. In: Conference on Extending Database Technology (EDBT), pp. 435\u2013438 (2020)"},{"key":"668_CR42","doi-asserted-by":"crossref","unstructured":"Toshniwal, A., Taneja, S., Shukla, A., Ramasamy, K., Patel, J.M., Kulkarni, S., Jackson, J., Gade, K., Fu, M., Donham, J., Bhagat, N., Mittal, S., Ryaboy, D.: Storm @Twitter. In: International Conference on Management of Data (SIGMOD), pp. 147\u2013156 (2014)","DOI":"10.1145\/2588555.2595641"},{"key":"668_CR43","doi-asserted-by":"crossref","unstructured":"Traub, J., Grulich, P., Cuellar, A.R., Bre$$\\ddot{\\text{ s }}$$, S., Katsifodimos, A., Rabl, T., Markl, V.: Scotty: efficient window aggregation for out-of-order stream processing. In: Poster at the International Conference on Data Engineering (ICDE-Poster) (2018)","DOI":"10.1109\/ICDE.2018.00135"},{"key":"668_CR44","unstructured":"Traub, J., Grulich, P., Cuellar, A.R., Bre$$\\ddot{\\text{ s }}$$, S., Katsifodimos, A., Rabl, T., Markl, V.: Efficient window aggregation with general stream slicing. In: Conference on Extending Database Technology (EDBT) (2019)"},{"issue":"3","key":"668_CR45","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/TPDS.2018.2868960","volume":"30","author":"A Villalba","year":"2019","unstructured":"Villalba, A., Berral, J.L., Carrera, D.: Constant-time sliding window framework with reduced memory footprint and efficient bulk evictions. Trans. Parallel Distrib. Syst. (TPDS) 30(3), 486\u2013500 (2019)","journal-title":"Trans. Parallel Distrib. Syst. (TPDS)"},{"key":"668_CR46","doi-asserted-by":"crossref","unstructured":"Yu, Y., Gunda, P.K., Isard, M.: Distributed aggregation for data-parallel computing: Interfaces and implementations. In: Symposium on Operating Systems Principles (SOSP), pp. 247\u2013260 (2009)","DOI":"10.1145\/1629575.1629600"},{"key":"668_CR47","doi-asserted-by":"crossref","unstructured":"Zaharia, M., Das, T., Li, H., Hunter, T., Shenker, S., Stoica, I.: Discretized streams: Fault-tolerant streaming computation at scale. In: Symposium on Operating Systems Principles (SOSP), pp. 423\u2013438 (2013)","DOI":"10.1145\/2517349.2522737"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00668-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00668-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00668-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T16:35:24Z","timestamp":1672331724000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00668-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,3]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["668"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00668-3","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2021,6,3]]},"assertion":[{"value":"9 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}