<p>Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm.
There are algorithms for calculating the number of 1s in a binary stream in a fixed-length window, such as the well-known Datar-Gionis-Indyk-Motwani algorithm.</p>
<p>Suppose we have a stream with expiration: every element in the stream is assumed to have expiration time. The question is to estimate the number of distinct elements in the stream which haven't yet expired.</p>
<p>Is there any known algorithm for this?</p>

CC BY-SA 4.0
2020-11-29T00:40:30.757Z
Distinct elements can be estimated with arbitrary deletions allowed which captures your setting (you can delete an element at the expiration time). There is a lot of literature on this topic. See for instance this paper and references. https://arxiv.org/abs/1012.4889
Chandra Chekuri
CC BY-SA 4.0
2020-12-01T21:03:26.963Z
One issue with what I suggested is that we cannot store all elements that need to be deleted so one cannot simply use deletion based algorithms. There are sliding window based results that may be relevant to look at.
Chandra Chekuri
<data-streams><streaming-algorithms>
Counting distinct elements in a stream with expiration
Dmitry Ushanov
# Counting distinct elements in a stream with expiration

(Asked by: username_0 on 2020-11-27)

Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm.
There are algorithms for calculating the number of 1s in a binary stream in a fixed-length window, such as the well-known Datar-Gionis-Indyk-Motwani algorithm.

Suppose we have a stream with expiration: every element in the stream is assumed to have expiration time. The question is to estimate the number of distinct elements in the stream which haven't yet expired.

Is there any known algorithm for this?

**Tags:** data-streams, streaming-algorithms
> **Comments:**
> **username_1**: Distinct elements can be estimated with arbitrary deletions allowed which captures your setting (you can delete an element at the expiration time). There is a lot of literature on this topic. See for instance this paper and references. https://arxiv.org/abs/1012.4889  
> **username_1**: One issue with what I suggested is that we cannot store all elements that need to be deleted so one cannot simply use deletion based algorithms. There are sliding window based results that may be relevant to look at.  

---

## 0 answers

