Лучший метод пересечения огромных HyperLogLogs в Redis
Проблема проста: мне нужно найти оптимальную стратегию для реализации точных объединений HyperLogLog на основе их представления Redis - это включает обработку их разреженных / плотных представлений, если структура данных экспортируется для использования в другом месте.
Две стратегии
Есть две стратегии, одна из которых кажется намного проще. Я посмотрел на реальный источник Redis, и у меня возникли небольшие проблемы (не большие в C, я сам), выясняющие, лучше ли с точки зрения точности и эффективности использовать их встроенные структуры / процедуры или разрабатывать свои собственные, Для чего бы это ни стоило, я готов пожертвовать пространством и в некоторой степени ошибками (stdev +-2%) в погоне за эффективностью с чрезвычайно большими сетами.
1. Принцип включения
Безусловно, самый простой из двух - по сути, я бы просто использовал объединение без потерь (PFMERGE) в сочетании с этим принципом для вычисления оценки перекрытия. Похоже, что во многих случаях тесты показывают, что это работает надежно, хотя у меня возникают проблемы с получением точного контроля эффективности и точности в дикой природе (в некоторых случаях могут возникать ошибки в 20-40%, что недопустимо в этом случае использования).
В принципе:
aCardinality + bCardinality - intersectionCardinality
или, в случае нескольких наборов...
aCardinality + (bCardinality x cCardinality) - intersectionCardinality
кажется, работает во многих случаях с хорошей точностью, но я не знаю, доверяю ли я этому. Несмотря на то, что в Redis есть много встроенных модификаторов с низким уровнем мощности, предназначенных для обхода известных проблем с HLL, я не знаю, сохраняется ли проблема дикой неточности (с использованием включения / исключения) с наборами высокой несоответствия по размеру...
2. Пересечение индекса Джакарта /MinHash
Этот способ кажется более интересным, но часть меня чувствует, что он может в вычислительном отношении перекрываться с некоторыми из существующих оптимизаций Redis (то есть я не реализую свой собственный алгоритм HLL с нуля).
При таком подходе я использовал бы случайную выборку бинов с алгоритмом MinHash (я не думаю, что реализация LSH стоит проблем). Это будет отдельная структура, но, используя minhash для получения индекса множеств Жакара, вы можете эффективно умножить мощность объединения на этот индекс для более точного подсчета.
Проблема в том, что я не очень хорошо разбираюсь в HLL, и хотя я хотел бы покопаться в статье Google, мне нужна жизнеспособная реализация в короткие сроки. Скорее всего, я пропускаю некоторые основные соображения либо о существующих оптимизациях Redis, либо о самом алгоритме, который допускает вычислительно-дешевые оценки пересечений с довольно слабыми доверительными границами.
Итак, мой вопрос:
Как мне наиболее эффективно получить вычислительно-дешевую оценку пересечения N огромных (миллиардов) множеств, используя redis, если я готов пожертвовать пространством (и в небольшой степени- точностью)?
2 ответа
Прочитайте эту статью некоторое время назад. Вероятно, ответит на большинство ваших вопросов. Принцип включения неизбежно усугубляет погрешность полей большого количества множеств. Мин-Хэш подход будет путь.
Существует третья стратегия для оценки размера пересечения любых двух наборов, представленных в виде эскизов HyperLogLog: оценка максимального правдоподобия.
Для получения более подробной информации см. Документ, доступный по адресу http://oertl.github.io/hyperloglog-sketch-estimation-paper/.