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

Слайд 1

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

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

Слайд 2

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

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

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

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)

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

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

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

Слайд 2

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

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

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

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

Слайд 3

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

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

2. Сгенерируем равномерно случайные коэффиценты многочлена из диапазона

3. В качестве функции вернем

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

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

А вероятность правильно выбрать все такие пары точек для фиксированной функции равна , так как каждый коэффицент выбирался с одинаковой вероятностью

Слайд 4

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

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

При этом определяются специальных момента: и

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

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

"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

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

Слайд 2

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

Слайд 3

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

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

   • Запрос добавление элемента :

   • Запрос удаления элемента :

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

Слайд 4

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

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

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

-потому что

Но , тогда

Слайд 5

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

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

Слайд 6

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

-

Слайд 7

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

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

Те что бы получить точность ответа не хуже с вероятностью не менее нужно независимо повторить алгоритм раз

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

Слайд 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

Пример

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

Мы имеем вектор и

Возьмем произвольную хэш-функцию из семейства

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

,

Теперь определим итоговый хэш таким образом:

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

, , что не сильно далеко от истинного значения.

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

, 2,

5 и посчитаем для входных типов их значения:

,

Flajolet-Martin sketch (F0 estimator)

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

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

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

Слайд 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)

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

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

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

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

Мы получим исходы которые описываются геометрическим распределением, а всего в среднем нам придется провести: экспериментов.

Слайд 3

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

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

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

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

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

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

5. Если нужно предъявить ответ, то вывести , где а - наименьший такой индекс что

Слайд 4н

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

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

Что бы проставить бит в равным , требуется что бы число заканчивалось на нулей. Вероятность этого

Ожидать такого события можно раз в:

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

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

Слайд 5

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

Слайд 6

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

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

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

Можно обратиться к подходу усреднения ответов как в AMS скетче, и тем самым уменьшить разборс, но проблема состоит в том среднее арифметическое чувствительно к выбросам, и разброс ошибки снижается довольно медленно

Слайд 7

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

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

В такой конфигурации алгоритма сложность по памяти составит а ошибка будет убывать со скоростью:

Слайд 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 предложенный в году. Вместо того что бы проводить подсчет на потоке целиком несколько раз, выбирая независимые хэш-функции, и усреднять уже готовые ответы, предлагается разделить поток на несколько субпотоков используя информацию которая поступает во время считывания новых чисел(те использовать случайность хэш-функции)

Слайд 2

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

Например, пусть: и Тогда индексом субпотока будет число , а ранг мы будем вычислять для числа: :

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

1. Завести несколько счетчиков , где пробегает от до

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

3. Определить индекс по первым битам и ранг по остатку

4. В случае если превышает то обновить значением .

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

   , где это среднее арифметическое по всем субпотокам, а - сложная константа которая определяется в зависимости от числа субпотоков:

Слайд 3

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

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

Хотя FM-sketch имеет лучшую дисперсию: против его недостатоком является то, что для достижения этой оценки требуется усреднить большое число независимых прогонов алгоритма, что приводит к повышенному потреблению памяти. Сниженное потребление памяти стало ключевым преимуществом алгоритма LogLog, по сравнению с FM-sketch которому надо хранить битов (где в то время как LogLog алгоритм потребляет только памяти засчет вычисления

Слайд 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 алгоритм. Разработан в году в Филлипом Флажелетом в соавторстве с коллегами.

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

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

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

Слайд 2

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

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

Предлагается формула , коэффицент не изменяется.

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

Тогда:

Откуда

Слайд 3

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

• : Пусть - число субпотоков в которых не попал ни один элемент.

  Если , что в качестве корректировки результата будем использовать Linear Counting метод, вместо нашего исходного метода:

• : Если мы практически исчерпали мощность хэш-функции, то алгоритм будет давать все больше коллизий, что искажает оценку. Поэтому есть смысл так же внести поправку:

• Иначе

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

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

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

Слайд 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);
        }
    }
}

Заключение