Стриминговые алгоритмы

Слайд 1

В 1980 - ых годах, на волне развития инфраструктуры и увеличения объемов обрабатываемых данных встала проблема анализа потока данных. Поток содержит в себе так много данных, что его не возможно сохранить в памяти компьютера, и поэтому для потоковых алгоритмов выработался неформальный прицнип - уложиться в пропорциональую логарифму от числа входных данных память

На сегодняшний день такие алгоритмы используются при анализе данных постоянно включенных систем (например роутер, веб-сервер и тд), составлении планов запросов к базе данных, подсчета статистик при подготовке текстовых данных в машинном обучении и тд

Слайд 2

Скетч(дословно набросок) - алгоритм вычисляющий некоторую статистику при помощи оценки данных, а не самих данных.

Для того что бы получать контроллируемую погрешность в этой оценке, нам необходимо формализовать подход к определению того, чего мы ожидаем от алгоритма.

Предлагается использовать (ε,δ)- модель. В которой ε отмечает относительную границу точности (те, насколько далеко мы можем отступить от ответа что бы ответ нас все еще устраивал) а δ - максимальная вероятность ошибиться(те все таки выйти за интервал [x-ε,x+ε])

Count-min sketch

https://warwick.ac.uk/news/knowledge-centre-archive/science/computer-science/grahamcormode/graham_cormode_profile_pic.jpg

Для второго создателя не знаю какое фото лучше)

https://www.google.com/search?q=S.+Muthu+Muthukrishnan&sca_esv=d50a49532b9b8e2e&udm=2&biw=1920&bih=919&aic=0&ei=rOtjaYyOK-eJ9u8PzP_0MQ&ved=0ahUKEwiMlPDWjoSSAxXnhP0HHcw_PQYQ4dUDCBI&uact=5&oq=S.+Muthu+Muthukrishnan&gs_lp=Egtnd3Mtd2l6LWltZyIWUy4gTXV0aHUgTXV0aHVrcmlzaG5hbjIEEAAYHkijBVCVBFiVBHABeACQAQCYAWigAWiqAQMwLjG4AQPIAQD4AQGYAgKgAm6YAwCIBgGSBwMxLjGgByyyBwMwLjG4B2rCBwMxLjHIBwKACAE&sclient=gws-wiz-img

Идея моментов и гарантии независимости

Слайд 1

Ранее мы определяли универсальное семейство хэш-функций(recall)

Однако для гарантирования корректности следующих алгоритмов нам потербуется более сильный вариант этого свойства, называемый k-независимостью.

Пусть (ℐ_k)={h:U→M} - семейство хэш-функций. Такое семейство называется k - независимым если для любого набора различных объектов (x_1),⋯,(x_k)∈Uk и любого набора значений (y_1),⋯,(y_k)∈Mk должно быть выполнено:

ℙ[(⋀_j=1^k)(h((x_j))=(y_j))]=1/(Mk)

для любой функции h из семейства.

Слайд 2

Это эквивалентно обладанию 2- умя свойствами для семейства (ℐ_k):

1. Для фиксированного хэшируемого объекта x значения хэш-функций h(x) равномерно распределены над M

2. Для k различных объектов (x_1),⋯,(x_k), для любой хэш-функции h значения h((x_1)),⋯,h((x_k)) являются независимыми случайными величинами

Второе свойство является принципиально важным для многих алгоритмов при анализе смещения оценки

Слайд 3

Если для универсального семейства мы рассматривали линейные функции над конечным полем, то теперь рассмотрим полиномы

1. Выберем некоторое простое число M

2. Сгенерируем равномерно случайные коэффиценты многочлена из диапазона [0,M)-(a_0),⋯,(a_k-1)

3. В качестве функции вернем h(x)=mod((a_k-1)*x(k-1)+⋯+(a_1)*x+(a_0),M)

Интуитивно понятно почему этот алгоритм верен:

Согласно теореме Лагранжа чере k точек можно провести только 1 многочлен степени k-1. Но в формулировке k- независимости мы буквально требуем что бы хэш-функция "проходила" через k точек ((x_j),(y_j)).

А вероятность правильно выбрать все такие пары точек для фиксированной функции h равна 1/(Mk), так как каждый коэффицент выбирался с одинаковой вероятностью 1/M

Слайд 4

Так как далее мы будем решать задачи связанные с оценками частотности, то давайте зафиксируем, что мы работаем с векторами x∈ℤ|U| которые отображают частоту появления до сих пор(на момент t) некоторого объекта из множества.

k- ым моментом называют:

(F_k)((x^t))=(∑_i=1^n)((x_i^t)k)

При этом определяются 2 специальных момента: (F_0) и (F_∞)

(F_0) - равен числу ненулевых компонентов вектора x (число уникальных значений в потоке)

(F_∞) - равен частоте самого часто встречающегося элемента в потоке

"Tug-of-war" AMS sketch (F2 estimator)

Слайд 1

https://cdn.ruwiki.ru/commonswiki/files/thumb/f/f7/Noga_Alon_%2822-03-2008%29.jpg/1200px-Noga_Alon_%2822-03-2008%29.jpg

https://ynet-pic1.yit.co.il/picserver5/crop_images/2023/09/13/rJzjxBuyJp/rJzjxBuyJp_0_0_1300_867_0_x-large.jpg

https://www.alibabanews.com/wp-content/uploads/sites/default/files/inline-images/suzhou1.jpeg

Авторы с этим алгоритмом получили премию Гёделя в 2005 году за его широкий спектр применимости и простоту и элегантность

Слайд 2

Задача состоит в том, что бы найти приблизительную оценкую (F_2) момента. Этот момент можно интерпретировать как показатель разброса данных относительно средней частоты, и используется при анализе сложности join запросов в базу данных, источников DDOS атак, а так же имеет приложение в машинном обучении, так как оценка при помощи этого алгоритма оказывается создает случайную проекцию исходных данных в пространство меньшей размерности, при этом сохраняя ее внутреннюю структуру

Слайд 3

1. Пусть у нас имеется семейство хэш-функций ℋ={h:U→{1,-1}}. Выберем оттуда случайную хэш-функцию функцию h

2. Пока поступают данные будем поддерживать счетчик C:

   • Запрос добавление элемента 𝓊∈U: C⟼C+h(𝓊)

   • Запрос удаления элемента 𝓊: C⟼C-h(𝓊)

   • Узнать текущую оценку: вернуть C2

Слайд 4

Нам нужно показать что этот скетч возвращает несмещенную оценку момента (F_2). Оценка называется несмещенной если ее матожидаение равно истинному параметру, те:

𝔼(C2)=(F_2)

В любой момент времени алгоритма C выражается как:

C=(∑_i=1^|U|)((x_i)*h((𝓊_i)))

𝔼(C2)=𝔼[(∑_i,j)((x_i)*h((𝓊_i))⋅(x_j)*h((𝓊_j)))]=

=(∑_i=1^|U|)((x_i)2*𝔼[h((𝓊_i))2])+2*(∑_i,j:i<j)((x_i)*(x_j)*𝔼[h((𝓊_i))*h((𝓊_j))])=

Так как семейство ℋ 4- независимое, то:

𝔼[h((𝓊_i))*h((𝓊_j))]=𝔼[h((𝓊_i))]*𝔼[h((𝓊_j))]=0-потому что 𝔼[h(𝓊)]=1/2-1/2=0

Но 𝔼[h(𝓊)2]=1/2+(-1)21/2=1, тогда

=(∑_i=1^|U|)((x_i)2)=(F_2)

Слайд 5

Что бы получить (ε,δ) - оценку точности нам нужно будет применить неравенство Чебышева. Для этого нужно оценить дисперсию оценки:

𝕍[C2]=𝔼[C(22)]-𝔼[C2]2

𝔼(C4)=(∑_([p,q,r,s],[i,j,k,l],[i+j+k+l=4]))[(x_p)i*(x_q)j*(x_r)k*(x_s)l⋅𝔼[h((𝓊_p))i*h((𝓊_q))j*h((𝓊_r))k*h((𝓊_s))l]]

Опять воспользовавшись 4- независимостью получим

𝔼[h((𝓊_p))i*h((𝓊_q))j*h((𝓊_r))k*h((𝓊_s))l]=𝔼[h((𝓊_p))i]*𝔼[h((𝓊_q))j]*𝔼[h((𝓊_r))k]⋅⋅𝔼[h((𝓊_s))l]

Слайд 6

Очевидно что такое ожидание будет ненулевым только если i,j,k,l- четные, а значит выживут лишь 2 суммы:

𝔼[C4]=(∑_p)((x_p)4)+6*(∑_p<q)((x_p)2*(x_q)2)

𝕍[C2]=(∑_p)((x_p)4)+6*(∑_p<q)((x_p)2*(x_q)2)- 𝔼[C2]2=

=(∑_p)((x_p)4)+6*(∑_p<q)((x_p)2*(x_q)2)-((∑_p)((x_p)4)+2*(∑_p<q)((x_p)2*(x_q)2))=

=4*(∑_p<q)((x_p)2*(x_q)2)⩽2*𝔼[C2]2

Слайд 7

Исходя из ограничения на дисперсию оценки, которое мы получили на предыдущем шаге - само по себе оно может быть достаточно большим. Довольно распространненая техника уменьшения разброса оценки состоит в том что бы сделать несколько независимых счетчиков(те случайным образом равномерно сгенерировать k хэш-функций из семейства ℋ), после чего усреднить их результат, ведь:

(𝕍^)[(C^2)]=𝕍[1/k*(∑_i=1^k)((C_i)2)]=1/(k2)*𝕍[(∑_i=1^k)((C_i)2)]=(∑_i=1^k)(𝕍[(C_i)2])/(k2)

Теперь мы можем записать неравенство Чебышёва для средней оценки:

ℙ[|(C^2)-𝔼((C^2))|>ε*𝔼((C^2))]⩽𝕍[(C^2)]/((ε*𝔼((C^2)))2)=(∑_i=1^k)(𝕍[(C_i)2])/(k2*ε2*𝔼((C^2))2)⩽

⩽(2*k*𝔼[C2]2)/(k2*ε2*𝔼[C2]2)=2/(k*ε2)

Те что бы получить точность ответа не хуже ε с вероятностью не менее δ нужно независимо повторить алгоритм k=2/(ε2*δ) раз

Тем самым мы можем достичь приемлемой точности, храня всего лишь набор счетчиков счетчик, а не сам вектор частот из чего финальная оценка по памяти равна 𝒪(1/(ε2)*log|U|)

Слайд 8

void AMS(std::istream& is, std::ostream& os, double eps, double delta) {
  int k = 2. / (eps * eps * delta);
  
  std::vector<std::hash<element_t>> h(k);
  std::vector<ll> c(k);

  for (auto& i : h) {
    h = get_4_independent_hash({1, -1});
  }

  while (!is.eof()) {
    char type;
    is >> type;
        
    if (type == '?') {
      double c_avg = 0.0;
      for (const auto& i : c) {
        c_avg += i * i;
      }

      c_avg /= k * 1.0;
      os << c_avg << "\n";
    } 
    else {
      element_t x;
      is >> x;
      
      for (ll i = 0; i < k; ++i) {
        auto hash = h[i](x);
        
        if (type == '+') {
          c[i] += hash;
        } else {
          c[i] -= hash;
        }
      }
    }
  }
}

Слайд 9

Пример

Пусть мы имеем поток вида: {1,1,2,3,2,1}, где различные числа обозначают различные добавляемые элементы в поток

Мы имеем вектор x=(3,2,1) и (F_2)(x)=9+4+1=14

Возьмем произвольную хэш-функцию из семейства ℋ={[mod((a_0)*x3+(a_1)*x2+(a_2)*x+(a_3),7),(a_i)∈[0,6]]}

h(x)=x3+3*x+2

В качестве хэшируемых значений будем брать номера типов элементов:

h(1)=1+3+2=6, h(2)=8+6+2≡2,h(3)=81+9+2=1

Теперь определим итоговый хэш таким образом: h(x)={[1,,*h(x)*четный],[-*1,,*h(x)*нечетный])

Тогда оценка для этого потока при помощи алгоритма AMS будет рассчитываться как:

C=1+1+1-1+1+1=4, C2=16, что не сильно далеко от истинного значения.

Если мы сгенерируем еще несколько хэш-функций из ℋ:

g(x)=2*x3+4*x2+6, l(x)=4*x3+4*x2+5*x+2,

ƒ(x)=6*x3+4*x+5 и посчитаем для входных типов их значения:

(C_g)=-1-1-1-1-1-1=-6, (C_l)=-1-1+1+1+1-1=0

(C_ƒ)=-1-1-1+1-1-1=-4

(C^2)=(16+36+0+16)/4=17

Flajolet-Martin sketch (F0 estimator)

Слайд 1(можно вынести как общий рассказ перед count-min sketch а потом уже тогда рассказать FM)

Другой важной метрикой является число уникальных элементов N в последовательности. Наивный алгоритм при помощи сортировки подсчетом или множества имеет рост памяти пропорциональный росту числа объектов в пространстве те 𝒪(U).

Эта задача возникает тогда когда нужно оценить число уникальных действий, например таковыми могут быть число просмотров, уникальных пользователей/посетителей веб-сайта, записей в базу данных и тд

Слайд 2

https://en.wikipedia.org/wiki/Philippe_Flajolet#/media/File:PhilippeFlajolet.jpg

У второго нет подтвержденных фотографий(возможно эта https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQqtr-BI_K-d2x2eHyB03FuQ6D4mCA2rjgrqA&s)

Второй подход о котором сегодня мы поговорим, предложил Филлип Флажолет в соавторстве с Нигелем Мартином в 1984.Этот подход сейчас активно используется для приближенного вычисления (F_0) момента.

Идея состоит в том, что если у вас есть какое-то маловероятное событие, то что бы получить этот исход на практике, вам потребуется провести очень много экспериментов.

Например пусть вы подбрасываете монетку и хотите получить ровно 10 орлов подряд. Вероятность этого события ℙ[00000000001]=1/(211)=p.

Будем проводить эксперименты по подбрасыванию монетки пока нам не выпадет решка, и считать сколько до этого было орлов. Теперь можно обозначить в качестве успешного эксперимента тот, в котором этот исход реализовался - выпало 10 орлов подряд, а не успешного тот в котором реализовался другой исход.

Мы получим исходы которые описываются геометрическим распределением, а всего в среднем нам придется провести: 𝔼[00000000001]=(1-p)/p=(211-1)/(211)/1/(211)=2047 экспериментов.

Слайд 3

Нетрудно заметить, что эксперимент с монеткой легко перенести на реальные данные. Пусть у нас есть достаточно хорошее семейство хэш-функций ℋ которое содержит в себе хэш-функции h:U→M=2L. Тогда поступающие объекты можно просто кодировать как бинарные строки.

У алгоритма существует множество вариантов, приведем одну из них:

1. Перед обработкой потока заведем битовый вектор bitmap длины L и проинициализируем его нулями

2. Для нового добавленного объекта x получить хэш h(x)

3. Найти индекс первой единицы в бинарном представлении числа h(x) справа. Обозначим эту функцию за ρ. Например: ρ(1101012)=0 а ρ(10010002)=3.Обратите внимание что тут нумерация битов происходит в порядке LittleEndian(от младшего к старешму биту)

4. Установим значение (bitmap_ρ) равным 1

5. Если нужно предъявить ответ, то вывести N=(2l)/𝜑, где 𝜑≈0.77351 а l - наименьший такой индекс что (bitmap_l)=0

Слайд 4н

Строгое доказательство довольно сложно, поэтому здесь посмотрим на основную идею.

Так как мы сказали что наше семейство ℋ достаточно хорошее, то вероятность получить каждый конкретный бит в хэше будет равна 1/2.

Что бы проставить k бит в bitmap равным 1, требуется что бы число заканчивалось на k нулей. Вероятность этого p=1/(2(k+1))

Ожидать такого события можно раз в: 𝔼[{(bitmap_k)=1}]=(1-p)/p=(2(k+1)-1)/(2(k+1))/1/(2(k+1))=2(k+1)-1

Если N ≫ 2k то скорее всего k- ый бит равен 1, если N ≪ 2k то равен 0.Иначе оба исхода примерно равновероятны. Значит выбирая в качестве k индекс первого 0 в битовом векторе, мы как минимум ошибемся не сильно.

Так же отметим, что для идеальных гарантий что у этого алгоритма, что у его модификаций нужно потребовать что бы ℋ было 𝒪(L)- незавимым, но на практике зачастую выбирают семейство с достаточно большим L и приемлемой гарантией независимости исходов(например с попарной независимостью) в силу дороговизны вычислений для "идеального" варианта.

Слайд 5

Тут пример подсчета

Слайд 6

Нетрудно заметить какие у такого подхода имеются минусы.

Во-первых константу 𝜑 в качестве поправки авторы предлагают не просто так. Оказывается что такая оценка является несмещенной только асимптотически, те 𝔼[N]≈𝜑*(F_0), но (lim_(ρ_max)→+∞)(𝔼[N])=(F_0)

Во-вторых алгоритм имеет тендецию завышать оценку. Обновляя N новым, большим значением, мы предполагаем что число уникальных элементов в потоке как минимум в 2 раза больше чем наша оценка на предыдущем этапе, хотя нам мог вполне мог случайно выпать 1 хэш с длинной последовательностью нулей в конце

Можно обратиться к подходу усреднения ответов как в AMS скетче, и тем самым уменьшить разборс, но проблема состоит в том среднее арифметическое чувствительно к выбросам, и ε=𝒪(1/√(,k*δ)) разброс ошибки снижается довольно медленно

Слайд 7

Брать медиану нескольких независимых оценок оказывается тоже неэффективно, так как в одной и той же степенью двойки может оцениваться довольно широкий промежуток разных значений (F_0).

Для решения подобных проблем используют технику Median of means. Пусть у нас есть d⋅q независимых хэш-функций. Сгруппируем результаты в группы по q и для каждой группы вычислим среднее из оценок. Далее выберем медиану из d усредненных оценок. Это позволяет и сглаживать влияние выбросов, и получать заметное приближение к истинному параметру. Рекомендуется брать q= 𝒪((log_2)((F_0)))

В такой конфигурации алгоритма сложность по памяти составит 𝒪((log_2)((F_0))*(log_2)|U|) а ошибка будет убывать со скоростью: ε=𝒪(√(,))

Слайд 8

void FM(std::istream& is, std::ostream& os, int d, int q) {
    const double corr = 0.77351;
    const ll L = 64;
    
    int k = d * q;
    
    std::vector<std::hash<element_t>> h(k);
    for (auto& i : h) {
        h = get_good_hash(L);
    }
    
    std::vector<std::bitset<64>> bitmap(k);
    
    while (!is.eof()) {
        char type;
        is >> type;
        
        if (type == '?') {
            std::vector<double> estimators(d, 0.0);
            
            for (ll i = 0; i < d; ++i) {
                for (ll j = i; j < k; j += d) {
                    int maxpow = find_max_2pow_index(bitmap[j]);
                    estimators[i] += std::pow(2, maxpow) / corr;
                }
                
                estimators[i] /= q;
            }
            
            std::nth_element(estimators.begin(), estimators.begin() + d / 2, estimators.end());
            os << estimators[d / 2] << "\n";
        } else {
            element_t x;
            is >> x;
            
            for (ll i = 0; i < k; ++i) {
				auto hash = h[i](x);
				
                int maxzero = find_max_2pow_index(h[i]);
                bitmap[i][maxzero] = 1;
			}
        }
    }
}

KMV sketch (F0 estimator)

LogLog algorithm

Слайд 1

Развитием идеи FM-скетча стал алгоритм LogLog предложенный в 2003 году. Вместо того что бы проводить подсчет на потоке целиком несколько раз, выбирая независимые хэш-функции, и усреднять уже готовые ответы, предлагается разделить поток на несколько субпотоков используя информацию которая поступает во время считывания новых чисел(те использовать случайность хэш-функции)

Слайд 2

Идея состоит в том, что бы разделить значение хэш-функции h(x) на 2 части: первые B битов использовать для того что бы определять индекс субпотока(всего субпотоков будет q=2B ), а оставшиеся биты использовать для подсчета ранга числа h(x). Ранг ρ определим как индекс первой единицы +1, если нумеровать биты в порядке BigEndian(от старшего к младшему).

Например, пусть: h(x)=11010000100102 и B=4. Тогда индексом субпотока будет число 11012=1310 , а ранг мы будем вычислять для числа: 0000100102 : ρ(0000100102)=5

Сам алгоритм строится следующим образом:

1. Завести несколько счетчиков (ρ_max^j), где j пробегает от 0 до 2B-1

2. Далее начать обработку поступающих элементов. Получая новый объект x вычислить его хэш h(x)

3. Определить индекс (j_h(x)) по первым B битам и ранг (ρ_h(x)) по остатку

4. В случае если (ρ_h(x)) превышает (ρ_max^(j_h(x))) то обновить (ρ_max^(j_h(x))) значением (ρ_h(x)).

5. Если поступает запрос вывести оценку то предъявить

   N=(α_q)⋅q⋅2(ρ_max), где (ρ_max) это среднее арифметическое по всем субпотокам, а (α_q) - сложная константа которая определяется в зависимости от числа субпотоков:

   (α_q)={[0.673,,,q=16],[0.697,,,q=32],[0.709,,,q=64],[0.7213/(1+1.079/q),,,q⩾128])

Слайд 3

Алгоритм по-прежнему опирается на ожидаемую редкость события, когда у числа подряд идет несколько одинаковых битов, но тепрь меняется то, что для стохастического усреднения мы используем сами значения хэш-функции

Здесь уместно отметить почему алгоритм называется LogLog: мы храним лишь ранги чисел. Ранг это индекс первой единицы + 1 в битовом представлении значит ρ(z)⩽(log_2)(z)+1Но что бы сохранить число (log_2)(z) нужно всего лишь (log_2)((log_2)(z)) битов.

Хотя FM-sketch имеет лучшую дисперсию: 0.78/√(,q) против 1.30/√(,q) его недостатоком является то, что для достижения этой оценки требуется усреднить большое число независимых прогонов алгоритма, что приводит к повышенному потреблению памяти. Сниженное потребление памяти стало ключевым преимуществом алгоритма LogLog, по сравнению с FM-sketch которому надо хранить 𝒪(k*L) битов (где (L=(log_2)(N)) в то время как LogLog алгоритм потребляет только 𝒪(L) памяти засчет вычисления h(x)

Слайд 4

Пример

HyperLogLog algorithm

Éric Fusy - https://www.cnrs.fr/sites/default/files/image/Fusy_0.jpg
Oliver Gandoulet - https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQloXxv0GHew7mjpJbONradm5O5ufknla6kCQ&s

Frédéric Meunier - https://dimag.ibs.re.kr/cms/wp-content/uploads/2019/11/frederic-2000x1200.jpg

Слайд 1

Наконец финальной модификацией которую мы рассмотрим будет HyperLogLog алгоритм. Разработан в 2007 году в Филлипом Флажелетом в соавторстве с 3 коллегами.

Этот алгоритм сейчас наиболее активно используется в продуктовых решениях.

Его используют крупные компании для анализа потока данных(числа уникальных пользователей / действий): Google BigQuery, Meta, Reddit и др

Он интегрирован во многие базы, компьют-енджины, и аналитические фреймворки: Redis, Amazon Redshift, Elasticsearch, Apache Spark и др

Слайд 2

В структуре алгоритма LogLog предлагается сделать 2 изменения.

Первое заключается в замене первоначальной оценки(или сырой оценки) N.

Предлагается формула N=((α_q)⋅q2)/(∑_j=1^q)(2(-(ρ_max^j))), коэффицент (α_q) не изменяется.

Тут мы перешли от оценки через среднее геометрическое, к оценке через среднее гармоническое, которое более устойчиво к выбросам. Как уже мы ранее выяснили (ρ_max^j) оценивается как логарифм от числа уникальных элементов в субпотоке, которых всего N/q в каждом, тк распредление значений по потокам равномерное.

Тогда: (∑_j=1^q)(2(-(ρ_max^j)))≈(∑_j=1^q)(q/N)=(q2)/N

Откуда 1/(∑_j=1^q)(2(-(ρ_max^j)))

Слайд 3

Второе важное отличие - работа с граничными кейсами:

• N<5/2*q: Пусть V - число субпотоков в которых не попал ни один элемент.

  Если V≠0, что в качестве корректировки результата будем использовать Linear Counting метод, вместо нашего исходного метода: N=q*log(q/V)

• N>M/L: Если мы практически исчерпали мощность хэш-функции, то алгоритм будет давать все больше коллизий, что искажает оценку. Поэтому есть смысл так же внести поправку: N=-M*log(1-N/M)

• Иначе N=N

Изначальные оценки(как было показано в секции с FM алгоритмом) для ответа являются несмещенными только асимптотически, поэтому при небольших значениях N алгоритм может выдавать бОльшую погрешность.

В тоже время так как, хэш-функция у нас в любом случае не идеальная, то будут возникать коллизии, и чем ближе N к пределу уникальных значений функции тем больше будет случаться коллизий.

Поэтому мы заменяем для этих случаев оценки на более точные, и возвращаем N. Таким образом общая погрешность для этого алгоритма укладывается в рамки 1.04/√(,q)

Слайд 4

Рассказать про Linear Counting(?)

Слайд 5

void HLL(std::istream& is, std::ostream& os, int b) {
    ll q = std::pow(2, q);
    const ll m = std::pow(2, 64);
    
    std::hash<element_t> h = get_good_hash(m);
    std::vector<int> subs_rho(q, 0);
    
    while (!is.eof()) {
        char type;
        is >> type;
        
        if (type == '?') {
            double n_raw = 0.0;
            
            for (const auto& i : subs_rho) {
                n_raw += std::pow(2.0, -i);
            }
            
            n_raw = 1.0 / n_raw;
            n_raw *= alpha(q) * q * q;
            
            double n_good = n_raw;
            
            if (2 * n_raw < 5 * q) {
                ll v = 0;
                for (const auto& i : subs_rho) {
                    if (i > 0) {
                        ++v;
                    }
                }
                
                if (v != 0) {
                    n_good = q * std::log(q / v);
                }
            } else if (n_raw > m / 64) {
                n_good = -m * std::log(1.0 - n_raw / m);
            }
            
            os << n_good << "\n";
        } else {
            element_t x;
            is >> x;
            
            ll hash = h(x);
            ll index = get_index(h(x));
            
            ll first_one = find_max_2pow_index(bitstring_reverse(hash) >> index);
            
            subs_rho[index] = std::max(subs_rho[index], first_one + 1);
        }
    }
}

Заключение