The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends. Blank, L., Cabello, S., Hajiaghayi, M. T., Krauthgamer, R., Mahabadi, S., Nusser, A., Phillips, J. M., & Sauer, J. In Bhattacharya, S., Nanongkai, D., Benedikt, M., & Puppis, G., editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)., volume 374, pages 37:1–37:24, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Artwork Size: 24 pages, 1216331 bytes ISBN: 9783959774284 Medium: application/pdf![The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting.
@inproceedings{blank_expiration_2026,
title = {The {Expiration} {Streaming} {Model}: {Diameter}, k-{Center}, {Counting}, {Sampling}, and {Friends}},
volume = {374},
copyright = {Creative Commons Attribution 4.0 International license, info:eu-repo/semantics/openAccess},
issn = {1868-8969},
shorttitle = {The {Expiration} {Streaming} {Model}},
url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37},
doi = {10.4230/LIPICS.ICALP.2026.37},
abstract = {An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting.},
language = {en},
urldate = {2026-07-15},
booktitle = {53rd {International} {Colloquium} on {Automata}, {Languages}, and {Programming} ({ICALP} 2026).},
publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
author = {Blank, Lotte and Cabello, Sergio and Hajiaghayi, Mohammad Taghi and Krauthgamer, Robert and Mahabadi, Sepideh and Nusser, André and Phillips, Jeff M. and Sauer, Jonas},
editor = {Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
year = {2026},
note = {Artwork Size: 24 pages, 1216331 bytes
ISBN: 9783959774284
Medium: application/pdf},
keywords = {Theory of computation → Computational geometry, Theory of computation → Streaming, sublinear and near linear time algorithms, WG: Observable, clustering, diameter, sampling, sliding window, streaming},
pages = {37:1--37:24},
}
Downloads: 0
{"_id":"PSMz5hZhSKvjBnExu","bibbaseid":"blank-cabello-hajiaghayi-krauthgamer-mahabadi-nusser-phillips-sauer-theexpirationstreamingmodeldiameterkcentercountingsamplingandfriends-2026","author_short":["Blank, L.","Cabello, S.","Hajiaghayi, M. T.","Krauthgamer, R.","Mahabadi, S.","Nusser, A.","Phillips, J. M.","Sauer, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends","volume":"374","copyright":"Creative Commons Attribution 4.0 International license, info:eu-repo/semantics/openAccess","issn":"1868-8969","shorttitle":"The Expiration Streaming Model","url":"https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37","doi":"10.4230/LIPICS.ICALP.2026.37","abstract":"An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting.","language":"en","urldate":"2026-07-15","booktitle":"53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026).","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","author":[{"propositions":[],"lastnames":["Blank"],"firstnames":["Lotte"],"suffixes":[]},{"propositions":[],"lastnames":["Cabello"],"firstnames":["Sergio"],"suffixes":[]},{"propositions":[],"lastnames":["Hajiaghayi"],"firstnames":["Mohammad","Taghi"],"suffixes":[]},{"propositions":[],"lastnames":["Krauthgamer"],"firstnames":["Robert"],"suffixes":[]},{"propositions":[],"lastnames":["Mahabadi"],"firstnames":["Sepideh"],"suffixes":[]},{"propositions":[],"lastnames":["Nusser"],"firstnames":["André"],"suffixes":[]},{"propositions":[],"lastnames":["Phillips"],"firstnames":["Jeff","M."],"suffixes":[]},{"propositions":[],"lastnames":["Sauer"],"firstnames":["Jonas"],"suffixes":[]}],"editor":[{"propositions":[],"lastnames":["Bhattacharya"],"firstnames":["Sayan"],"suffixes":[]},{"propositions":[],"lastnames":["Nanongkai"],"firstnames":["Danupon"],"suffixes":[]},{"propositions":[],"lastnames":["Benedikt"],"firstnames":["Michael"],"suffixes":[]},{"propositions":[],"lastnames":["Puppis"],"firstnames":["Gabriele"],"suffixes":[]}],"year":"2026","note":"Artwork Size: 24 pages, 1216331 bytes ISBN: 9783959774284 Medium: application/pdf","keywords":"Theory of computation → Computational geometry, Theory of computation → Streaming, sublinear and near linear time algorithms, WG: Observable, clustering, diameter, sampling, sliding window, streaming","pages":"37:1–37:24","bibtex":"@inproceedings{blank_expiration_2026,\n\ttitle = {The {Expiration} {Streaming} {Model}: {Diameter}, k-{Center}, {Counting}, {Sampling}, and {Friends}},\n\tvolume = {374},\n\tcopyright = {Creative Commons Attribution 4.0 International license, info:eu-repo/semantics/openAccess},\n\tissn = {1868-8969},\n\tshorttitle = {The {Expiration} {Streaming} {Model}},\n\turl = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37},\n\tdoi = {10.4230/LIPICS.ICALP.2026.37},\n\tabstract = {An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting.},\n\tlanguage = {en},\n\turldate = {2026-07-15},\n\tbooktitle = {53rd {International} {Colloquium} on {Automata}, {Languages}, and {Programming} ({ICALP} 2026).},\n\tpublisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},\n\tauthor = {Blank, Lotte and Cabello, Sergio and Hajiaghayi, Mohammad Taghi and Krauthgamer, Robert and Mahabadi, Sepideh and Nusser, André and Phillips, Jeff M. and Sauer, Jonas},\n\teditor = {Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},\n\tyear = {2026},\n\tnote = {Artwork Size: 24 pages, 1216331 bytes\nISBN: 9783959774284\nMedium: application/pdf},\n\tkeywords = {Theory of computation → Computational geometry, Theory of computation → Streaming, sublinear and near linear time algorithms, WG: Observable, clustering, diameter, sampling, sliding window, streaming},\n\tpages = {37:1--37:24},\n}\n\n\n\n","author_short":["Blank, L.","Cabello, S.","Hajiaghayi, M. T.","Krauthgamer, R.","Mahabadi, S.","Nusser, A.","Phillips, J. M.","Sauer, J."],"editor_short":["Bhattacharya, S.","Nanongkai, D.","Benedikt, M.","Puppis, G."],"key":"blank_expiration_2026","id":"blank_expiration_2026","bibbaseid":"blank-cabello-hajiaghayi-krauthgamer-mahabadi-nusser-phillips-sauer-theexpirationstreamingmodeldiameterkcentercountingsamplingandfriends-2026","role":"author","urls":{"Paper":"https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37"},"keyword":["Theory of computation → Computational geometry","Theory of computation → Streaming","sublinear and near linear time algorithms","WG: Observable","clustering","diameter","sampling","sliding window","streaming"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero-group/pratikmhatre/5933976","dataSources":["yJr5AAtJ5Sz3Q4WT4"],"keywords":["theory of computation → computational geometry","theory of computation → streaming","sublinear and near linear time algorithms","wg: observable","clustering","diameter","sampling","sliding window","streaming"],"search_terms":["expiration","streaming","model","diameter","center","counting","sampling","friends","blank","cabello","hajiaghayi","krauthgamer","mahabadi","nusser","phillips","sauer"],"title":"The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends","year":2026}