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?

$\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 '20 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 '20 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.