Как работает алгоритм LogLog с одиночной хэш-функцией
Я нашел несколько десятков объяснений основной идеи алгоритмов LogLog, но у них не хватает подробностей о как работает разделение результатов хеш-функции? Я имею в виду, что использование одной хэш-функции не является точной при использовании многих функция слишком дорога. Как они преодолевают проблему с помощью одиночной хэш-функции?
Этот ответ является лучшим объяснением, которое я нашел, но до сих пор не имеет смысла для меня:
Они использовали один хэш, но разделили его на две части. Один из них называется ведро (общее количество ведер составляет 2 ^ х), а другое - это в основном так же, как и наш хеш. Мне было трудно получить то, что происходило, поэтому я приведут пример. Предположим, у вас есть два элемента и ваш хэш функция, которая дает значения от 0 до 2 ^ 10, дает 2 значения: 344 и 387. Вы решили иметь 16 ведер. Итак, у вас есть:
0101 011000 bucket 5 will store 1
0110 000011 bucket 6 will store 4
Не могли бы вы объяснить пример выше PLS? У вас должно быть 16 ведер, потому что у вас заголовок длиной 4, верно? Итак, как вы можете иметь 16 ведер с двумя хэшами? Мы оцениваем только ведра, не так ли? Итак, первое ведро имеет размер 1, а второе - размер 4, верно? Как объединить результаты?
Ответы
Ответ 1
Разделение функции хэш-функции: наша цель состоит в том, чтобы использовать многие структуры гиперлоголога (например, предположим, что 16 структур гиперлога, каждый из которых использует 64-битную хеш-функцию) вместо одного, чтобы уменьшить ошибку оценки. Интуитивным подходом может быть обработка каждого из входных данных в каждой из этих структур гиперлога. Однако в этом случае нам нужно было бы убедиться, что гиперлоги являются независимыми друг от друга, то есть нам понадобится набор из 16 хэш-функций, которые независимы друг от друга - это трудно найти!
Таким образом, мы используем альтернативный подход. Вместо использования семейства 64-битных хеш-функций мы будем использовать 16 отдельных структур гиперлога, каждый из которых использует только 60-битную хеш-функцию. Как мы это делаем? Легко, мы берем нашу 64-битную хэш-функцию и просто игнорируем первые 4 бита, создавая 60-битную хеш-функцию. Что мы делаем с первыми 4 битами? Мы используем их для выбора одного из 16 "ведер" (каждое "ведро" - это просто структура гиперлога. Обратите внимание, что 2 ^ 4 бита = 16 ведер). Теперь каждый из входов назначается точно одному из 16 ведер, где 60-битовая хеш-функция используется для вычисления значения гиперлога. Таким образом, у нас есть 16 структур hyperloglog, каждый из которых использует 60-битную хеш-функцию. Предполагая, что мы выбрали достойную хеш-функцию (это означает, что первые 4 бита распределены равномерно и что они не коррелируют с остальными 60 битами), теперь у нас есть 16 независимых структур гиперлога. Мы принимаем гармоническое среднее из их 16 оценок, чтобы получить гораздо меньшую погрешность оценки мощности.
Надеюсь, что это очистит!
Ответ 2
оригинальная статья HyperLogLog, упомянутая OronNavon, является довольно теоретической. Если вы ищете объяснение оценки мощности без необходимости сложного анализа, вы можете взглянуть на документ, над которым я сейчас работаю: http://oertl.github.io/hyperloglog-sketch-estimation-paper. Он также представляет обобщение исходной оценки, которая не требует специальной обработки для малых или больших мощностей.
