2026-09-08T02:21:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26426 2026-09-05T19:42:59Z ddc:004 open_access

The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends Blank, Lotte Cabello, Sergio Hajiaghayi, Mohammad Taghi Krauthgamer, Robert Mahabadi, Sepideh Nusser, André Phillips, Jeff M. Sauer, Jonas clustering diameter streaming sliding window sampling 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. Our second and main set of results for the expiration model designs algorithms for the diameter and k-center problems, where items are points in a metric space. Our results significantly extend those known for the special case of sliding-window streams by Cohen-Addad, Schwiegelshohn, and Sohler [ICALP 2016], and obtain a strictly better approximation factor for the diameter in the important special case of high-dimensional Euclidean metrics. We develop new decomposition and coordination techniques along with a geometric dominance framework to filter out redundant points based on both temporal and spatial proximity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lotte Blank and Sergio Cabello and Mohammad Taghi Hajiaghayi and Robert Krauthgamer and Sepideh Mahabadi and André Nusser and Jeff M. Phillips and Jonas Sauer 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.37 urn:nbn:de:0030-drops-264269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37 eng https://creativecommons.org/licenses/by/4.0/legalcode