Стриминговые алгоритмы
Слайд 1
В
На сегодняшний день такие алгоритмы используются при анализе данных постоянно включенных систем (например роутер, веб-сервер и тд), составлении планов запросов к базе данных, подсчета статистик при подготовке текстовых данных в машинном обучении и тд
Слайд 2
Скетч(дословно набросок) - алгоритм вычисляющий некоторую статистику при помощи оценки данных, а не самих данных.
Для того что бы получать контроллируемую погрешность в этой оценке, нам необходимо формализовать подход к определению того, чего мы ожидаем от алгоритма.
Предлагается использовать
Count-min sketch
Для второго создателя не знаю какое фото лучше)
Идея моментов и гарантии независимости
Слайд 1
Ранее мы определяли универсальное семейство хэш-функций(recall)
Однако для гарантирования корректности следующих алгоритмов нам потербуется более сильный вариант этого свойства, называемый
Пусть
для любой функции
Слайд 2
Это эквивалентно обладанию
Для фиксированного хэшируемого объекта
значения хэш-функций равномерно распределены над Для
различных объектов , для любой хэш-функции значения являются независимыми случайными величинами
Второе свойство является принципиально важным для многих алгоритмов при анализе смещения оценки
Слайд 3
Если для универсального семейства мы рассматривали линейные функции над конечным полем, то теперь рассмотрим полиномы
Выберем некоторое простое число
Сгенерируем равномерно случайные коэффиценты многочлена из диапазона
В качестве функции вернем
Интуитивно понятно почему этот алгоритм верен:
Согласно теореме Лагранжа чере
А вероятность правильно выбрать все такие пары точек для фиксированной функции
Слайд 4
Так как далее мы будем решать задачи связанные с оценками частотности, то давайте зафиксируем, что мы работаем с векторами из
При этом определяются
"Tug-of-war" AMS sketch (F2 estimator)
Слайд 1
https://www.alibabanews.com/wp-content/uploads/sites/default/files/inline-images/suzhou1.jpeg
Авторы с этим алгоритмом получили премию Гёделя в
Слайд 2
Задача состоит в том, что бы найти приблизительную оценкую join запросов в базу данных, источников DDOS атак, а так же имеет приложение в машинном обучении, так как оценка при помощи этого алгоритма оказывается создает случайную проекцию исходных данных в пространство меньшей размерности, при этом сохраняя ее внутреннюю структуру
Слайд 3
Пусть у нас имеется семейство хэш-функций
. Выберем оттуда случайную хэш-функцию функцию Пока поступают данные будем поддерживать счетчик
: Запрос добавление элемента
: Запрос удаления элемента
: Узнать текущую оценку: вернуть
Слайд 4
Нам нужно показать что этот скетч возвращает несмещенную оценку момента
В любой момент времени алгоритма
Так как семейство
Но
Слайд 5
Что бы получить
Опять воспользовавшись
Слайд 6
Очевидно что такое ожидание будет ненулевым только если
Слайд 7
Исходя из ограничения на дисперсию оценки, которое мы получили на предыдущем шаге - само по себе оно может быть достаточно большим. Довольно распространненая техника уменьшения разброса оценки состоит в том что бы сделать несколько независимых счетчиков(те случайным образом равномерно сгенерировать
Теперь мы можем записать неравенство Чебышёва для средней оценки:
Те что бы получить точность ответа не хуже
Слайд 8
Тем самым мы можем достичь приемлемой точности, храня всего лишь набор счетчиков счетчик, а не сам вектор частот из чего финальная оценка по памяти равна
Выше представленная техника часто используется что бы уменьшить разброс при фиксированном смещении. Однако как можно заметить из формулы для
Для того что бы побороть этот недостаток и получить зависимость порядка
Flajolet-Martin sketch (F0 estimator)
https://en.wikipedia.org/wiki/Philippe_Flajolet#/media/File:PhilippeFlajolet.jpg
У второго нет подтвержденных фотографий
Слайд 1
Другой важной метрикой является число уникальных элементов в последовательности. Наивный алгоритм при помощи сортировки подсчетом или множества имеет рост памяти пропорциональный росту числа объектов в пространстве те
При рассмотрении алгоритмов для решения этой задачи ограничимся формулировкой, в которой в потоке происходят только операции добавления элементов.
Слайд 2
Идея состоит в том, что если у вас есть какое-то маловероятное событие, то что бы получить этот исход на практике, вам потребуется провести очень много экспериментов.
Например пусть вы подбрасываете монетку и хотите получить ровно
Будем проводить эксперименты по подбрасыванию монетки пока нам не выпадет решка, и считать сколько до этого было орлов. Теперь можно обозначить в качестве успешного эксперимента тот, в котором этот исход реализовался - выпало
Мы получим исходы которые описываются геометрическим распределением, а всего в среднем нам придется провести:
Слайд 3
Нетрудно заметить, что эксперимент с монеткой легко перенести на реальные данные. Пусть у нас есть универсальное семейство хэш-функций
Алгоритм состоит из следующих шагов:
Для нового добавленного объекта
получить хэш Найти первую единицу в бинарном представлении числа
справа. Обозначим эту функцию за . Например: а Сравнить с
который был посчитан по предыдущим элементам Если нужно предъявить ответ, то вывести
, где
Слайд 4
Интуиция доказательства строится похожим образом с экспериментом с монеткой(вообще говоря это и есть он). Так как хэш-функция получена из универсального семейства, то вероятность поставить каждый бит на своем месте равна