Redis Hyperloglog sınırlamaları

Question

Redis Hyperloglog kullanarak hatayı bir şekilde çözmeye çalışıyorum ama anlamaya çalıştığım şey, Hyperloglog tarafından verilere veya dağıtıma ilişkin sınırlamalar ve varsayımlar.

Count-min ve bloom filtresinin kendi sınırlamaları vardır, ancak Google, Hyperloglog'un uygulamalarına ve sınırlamalarına ilişkin fazla bilgi sağlama konusunda yardımcı olmaz.

Ben Redis Hyperloglog kullanarak ve Antirez olarak there are no practical limits to the cardinality of the sets we can count. açıklanır Ama bir teori açısından bakıldığında, Hyperloglog veri veya dağılımı hakkında herhangi varsayımlar/kısıtlamaları yapar ki?

Answer 1

HyperLogLog algoritması, güçlü bir evrensel karma işlevinin kullanıldığını varsayar. Redis pratik bir bakış açısından yeterince iyi olması gereken MurmurHash64A kullanır. Redis HyperLogLog uygulaması, 64bit karma değerler içindeki herhangi bir bit çalışma uzunluğunu temsil etmeyi sağlayan yazmaç başına 6 bit kullanır. Dolayısıyla, gördüğüm tek sınırlama 64bit karma değerin kendisidir. Eğer kardinalite 2^64 mertebesinde ise, büyük tahmin hatalarına yol açacak birçok karma çarpışma olacaktır. Bununla birlikte, bu büyüklük sırasının belirleyicileri uygulamada asla gerçekleşmez.