Проблемът е прост: трябва да намеря оптималната стратегия за внедряване на точни HyperLogLog обединения въз основа на тяхното представяне на Redis - това включва обработка на техните разредени/плътни представяния, ако структурата на данните се експортира за използване другаде.
Две стратегии
Има две стратегии, едната от които изглежда много по-проста. Разгледах действителния източник на Redis и имам малко проблеми (аз самият не съм голям в C) да разбера дали е по-добре от гледна точка на прецизност и ефективност да използвам техните вградени структури/програми или да разработя свои собствени . Колкото и да си струва, готов съм да пожертвам пространство и до известна степен грешки (стандартно отклонение +-2%) в преследване на ефективност с изключително големи комплекти.
1. Принцип на включване
Досега най-простият от двата - по същество бих използвал обединението без загуби (PFMERGE) в комбинация с този принцип, за да изчисля оценка на припокриването. Тестовете изглежда показват, че това работи надеждно в много случаи, въпреки че имам проблеми с получаването на точна оценка на ефективността и точността в природата (някои случаи могат да доведат до грешки от 20-40%, което е неприемливо в този случай на употреба).
По принцип:
aCardinality + bCardinality - intersectionCardinality
или, в случай на множество комплекти...
aCardinality + (bCardinality x cCardinality) - intersectionCardinality
изглежда работи в много случаи с добра точност, но не знам дали му вярвам. Въпреки че Redis има много вградени модификатори с ниска кардиналност, предназначени да заобикалят известни проблеми с HLL, не знам дали проблемът с дивата неточност (използване на включване/изключване) все още присъства при набори с голямо несъответствие в размера...
2. Пресичане на индекса на Jaccard/MinHash
Този начин изглежда по-интересен, но част от мен има чувството, че може изчислително да се припокрива с някои от съществуващите оптимизации на Redis (т.е. не внедрявам собствен HLL алгоритъм от нулата).
С този подход бих използвал произволна извадка от контейнери с алгоритъм MinHash (не мисля, че внедряването на LSH си струва труда). Това би било отделна структура, но като използвате minhash, за да получите индекса на Jaccard на наборите, след това можете ефективно да умножите кардиналността на обединението по този индекс за по-точно преброяване.
Проблемът е, че не съм много добре запознат с HLL и макар че бих искал да се разровя в документа на Google, имам нужда от жизнеспособна реализация в кратки срокове. Вероятно пренебрегвам някои основни съображения или на съществуващите оптимизации на Redis, или в самия алгоритъм, който позволява изчислително евтини пресечни оценки с доста слаби граници на доверие.
И така, моят въпрос:
Как най-ефективно да получа изчислително евтина оценка на пресичане на N огромни (милиарди) комплекта, използвайки redis, ако съм готов да жертвам пространство (и в малка степен, точност)?
