2026-07-23T16:36:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11242 2024-03-06T10:47:47Z ddc:004 open_access

Improved Algorithms for Time Decay Streams Braverman, Vladimir Lang, Harry Ullah, Enayat Zhou, Samson Streaming algorithms approximation algorithms facility location and clustering In the time-decay model for data streams, elements of an underlying data set arrive sequentially with the recently arrived elements being more important. A common approach for handling large data sets is to maintain a coreset, a succinct summary of the processed data that allows approximate recovery of a predetermined query. We provide a general framework that takes any offline-coreset and gives a time-decay coreset for polynomial time decay functions. We also consider the exponential time decay model for k-median clustering, where we provide a constant factor approximation algorithm that utilizes the online facility location algorithm. Our algorithm stores O(k log(h Delta)+h) points where h is the half-life of the decay function and Delta is the aspect ratio of the dataset. Our techniques extend to k-means clustering and M-estimators as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Braverman and Harry Lang and Enayat Ullah and Samson Zhou 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.27 urn:nbn:de:0030-drops-112429 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.27 eng https://creativecommons.org/licenses/by/3.0/legalcode