Лучший способ пересечь огромные журналы HyperLogLog в 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, если я готов пожертвовать пространством (и в небольшой степени точностью)?


redis hash hyperloglog hashtable minhash
person Julian    schedule 07.05.2015    source источник
comment
Каковы критерии «наилучшего метода», чтобы мы знали, какие ответы давать? то есть как бы вы решили, что является «лучшим ответом»? Вам нужно установить некоторые ограничения — какие ресурсы доступны вам для решения этой проблемы?   -  person Ryan Vincent    schedule 07.05.2015
comment
Является ли «redis» лучшим инструментом для решения проблемы «совпадения», которая у вас есть? «redis» требует, чтобы все хранилось в «памяти». Это может быть «интересно» для «миллиардов» записей.   -  person Ryan Vincent    schedule 07.05.2015
comment
Что ж, «лучший» в этом случае — это, по сути, порядок, который я описал @Ryan, пространство не имеет значения; точность будет следующей жертвой в заданных пределах отклонения, а вычислительная эффективность — мой приоритет №1.   -  person Julian    schedule 08.05.2015
comment
Я также не совсем уверен, что это так, но я чувствую, что не хочу выходить за рамки решения в памяти, учитывая мои потребности в доступе к этим данным и выполнении этих запросов в динамическом стеке - ресурсы для поддержки этого по существу не ограничены, однако имейте в виду, что мне не обязательно пересекать точные ЗНАЧЕНИЯ из N наборов миллиардов, просто есть точное/дешевое кардинальное решение, основанное на HLL, где я могу пересекаться по желанию... опять же, когда вы есть молоток...   -  person Julian    schedule 08.05.2015
comment
Спасибо за ответ, если честно, это «выходит за рамки моей компетенции», но похоже, что это забавная проблема, над которой стоит поработать. :-)   -  person Ryan Vincent    schedule 08.05.2015
comment
Это круто! Я пытаюсь решить что-то очень похожее. Можете ли вы поделиться тем, как вы реализовали minhash в сочетании с Redis HLL? Это может быть очень полезно для других, пытающихся решить, что должно быть, очень распространенную проблему.   -  person Sid    schedule 29.08.2015

Ответы (2)


arrow_upward
4
arrow_downward

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

http://tech.adroll.com/media/hllminhash.pdf

person frugalcoder    schedule 21.08.2015
comment
На самом деле уже построил это :). Этот документ определенно помог, но он действительно начал работать, когда я заменил пользовательское расширение murmurhash3. Сильный холдинг @ 4 млн запросов/мин. - person Julian; 21.08.2015
comment
Добавьте ответ на свой вопрос, если вы нашли правильный способ об этом. И отметьте его как принятый. - person frugalcoder; 12.01.2016

arrow_upward
2
arrow_downward

Существует третья стратегия оценки размера пересечения любых двух наборов данных в виде эскизов HyperLogLog: оценка максимального правдоподобия.

Дополнительные сведения см. в статье, доступной по адресу http://oertl.github.io/hyperloglog-sketch-estimation-paper/.

person otmar    schedule 02.11.2016