Задачи по стримингу

Семинарские задачи

CMS

HLL

Пример $+$ задача

Рассмотрим пример следующего потока:

$S=\{1,3,2,1,2,3,4,3,1,2,3,1\}$

Точная оценка для него составляет: $F_0=4.$ Попробуем использовать HLL для аппроксимации этого значения:

Определим хэш-функцию явно:

Пример - подсчет HLL с отсечением первых $2$ битов для индексирования $(m=4)$

Так как все индексы различны, то вектор ${\rho }_{\text{max}}$ после обработки потока будет выглядеть как:

${\rho }_{\text{max}}=\{1,1,5,6\}$

Посчитаем среднее гармоническое из оценок:

$E=2^{-1}+2^{-1}+2^{-5}+2^{-6}=\frac{67}{64}=1.046875\Rightarrow \frac{m}{1.046875}\approx$

$\approx 4\cdot 0.955=3.821$

${\hat{F}}_0={\alpha }_m\cdot m\cdot E$, где ${\alpha }_m\approx 0.5324$

${\hat{F}}_0\approx 0.5324\cdot 4\cdot 3.821=8.137$

Задача - подсчет HLL с отсечение $1$ бита для индексирования$(m=2)$

В потоке встречаются все элементы из этих $4$, значит итоговый вектор ${\rho }_{\text{max}}$ выглядт как:

${\rho }_{\text{max}}=\{\max (2,1),\max (6,1)\}=\{2,6\}$

$E=2^{-2}+2^{-6}=\frac{17}{64}=0.265625\Rightarrow \frac{m}{0.265625}\approx 7.529$

${\alpha }_m\approx 0.3512$

${\hat{F}}_0\approx 0.3512\cdot 2\cdot 7.529\approx 5.288$

Объяснить результат

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

Задачи для SET

Задача A2. HyperMegaLogLog ProMax++

Разбалловка:

1. Инфрастуктура тестирования - $5$ баллов

2. Реализация HLL и наивного алгоритма - $2$ балла

3. Проведение тестирования, подбор констант - 3 балла

4. Анализ результатов, составление графиков - 4 балла

5. Исследование потенциала улучшения и последующие тестирование - $5$ баллов

6. За реализацию доп алгоритма, пункты $2$ $3$ $4$ получают $+1$ балл сверху, в случае если для доп алгоритма были выполнены корректно

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

1. Вам предлагается исследовать один из таких алгоритмов HyperLogLog, который находит оценку для момента $F_0$. Что бы провести успешное исследование нужно выполнить несколько важных этапов:

   Этап $1$ - Создание инфраструктуры:

   Напишите реализацию класса RandomStreamGen . Он должен уметь возвращать массив случайных строк(состоящих из больших и маленьких латинских букв, тире и цифр от $0$ до $9$) длиной до $30$ символов.

   Напишите свой генератор хэш-функций из некоторого семейства, или используйте общедоступный. Учитывайте, что вам нужно взять не любую хэш-функцию, а такую которая может выдать произвольное значение из множества значений приблизительно равновероятно(те в битовой строке данного числа можно ожидать каждое значение для каждого регистра с вероятностью $\frac{1}{2}$). Ограничьте множество выдаваемых значений $2^{32}$

   Этап $2$ - Реализация алгоритмов:

   Реализуйте алгоритм HyperLogLog любым удобным способом, а так же напишите алгоритм вычисляющий точное значение $F_0$. Для алгоритма HLL нужно выбрать размер индекса, который определяется первыми $L$ регистрами числа. Самостоятельно подберите константу $L$ и обоснуйте, почему вы выбрали именно такое число. Для этого может потребоваться провести несколько запусков с разными значениями $L$.

   Так же на ваш выбор можете добавить еще $1$ алгоритм в сравнение(например таким может быть k - min values, или Linear counting или какой-нибудь другой), если решите его добавить в отчете кратко опишите принцип его работы

   Этап $3$ - Запуск:

   Проведите серию тестов при помощи написанных вами классов и алгоритмов. Оцените как изменяется точность ответа алгоритма HLL, насколько она близка к истинному значению, укладывается ли ваша реализация в рамки заявленных отклонений(проверьте для $\frac{1.04}{\sqrt{B}}$ и
   $\frac{1.3}{\sqrt{B}}$ где $B=2^L$ ). Так же зафиксируйте, сколько памяти потребляет алгоритм.

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

   Сгенерируйте несколько потоков и посчитайте для результатов каждого из них выборочные статистики: $𝔼\left({\hat{N}}_t\right)$ и $\sigma \left({\hat{N}}_t\right)$ - где ${\hat{N}}_t$ оценка полученная HLL $F_0$ в потоке, в моменте времени $t$ (те на момент когда прошло $t$ шагов).

   Этап $4$ - анализ:

   Постройте график среднего потребления памяти алгоритмами, сравнения истинной $F_0$ и ее оценки${\hat{N}}_t$, и выборочных статистик(для отображения дисперсии параллельно перенестие график $𝔼\left({\hat{N}}_t\right)$ вверх и вниз на $\sigma \left({\hat{N}}_t\right)$ и закрасти получившуюся область)

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

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

2. Теперь когда вы проверили эффективность оригинального алгоритма, время внести в него что-то новое.

   Разработайте или внедрите сторонние улучшения для алгоритма. Улучшения могут быть как технического плана(например заменить vector на bitset и сократить потребление памяти в $8$ раз, и тд), так и статистического(скорректировать алгоритм, так что бы он выдавал более точную оценку, или имел меньшую дисперсию и тд).

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

   Прикрепите вместе с кодом оригинального алгоритма, модифицированный и протестируйте его тоже. Проведите сравнительный анализ(такой же как и в первом пункте задания)