Изменения

Задача о '''приблизительном подсчете числа вхождений''': пусть дан некоторый поток данных <math>S = s_1, s_2, \dots, s_i, \dots, \: s_j \in U</math>. Необходимо подсчитать, сколько раз элемент <math>x \in U</math> встретился в потоке <math>S</math> на момент времени <math>t</math>, т.е. <math>\sum_{j=1}^{t} I_{s_j = x}</math>. В данной статье рассмотрены две структуры данных, позволяющие решить эту задачу: Count-Min Sketch и Count Sketch. Обе структуры данных были предложены в начале 00-х в ответ на необходимость сбора информации об увеличившемся потоке интернет-трафика.