6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. arxiv.org/abs/1012.4889 $\endgroup$
    – Chandra Chekuri
    Nov 29, 2020 at 0:40
  • $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Dec 1, 2020 at 21:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.