هايبرلوغ لوج

الموسوعة الحرة

خوارزمية HyperLogLog هي خوارزمية لحل مشكلة عدّ العناصر المميزة ، حيث تُقارب عدد العناصر المميزة في مجموعة متعددة . [ 1 ] يتطلب حساب العدد الدقيق للعناصر المميزة في مجموعة متعددة مقدارًا من الذاكرة يتناسب مع هذا العدد، وهو أمر غير عملي لمجموعات البيانات الضخمة جدًا. تستخدم مُقدِّرات العدد الاحتمالية، مثل خوارزمية HyperLogLog، ذاكرة أقل بكثير من ذلك، ولكنها لا تستطيع سوى تقريب العدد. تستطيع خوارزمية HyperLogLog تقدير أعداد تزيد عن 10⁹ بدقة نموذجية (خطأ معياري) تبلغ 2%، باستخدام 1.5 كيلوبايت من الذاكرة. [ 1 ] تُعد HyperLogLog امتدادًا لخوارزمية LogLog السابقة، [ 2 ] والتي بدورها مشتقة من خوارزمية Flajolet–Martin لعام 1984. [ 3 ]   

مصطلحات

في الورقة البحثية الأصلية لفلاويوليت وآخرون [ 1 ] ، وفي الدراسات ذات الصلة بمسألة عدّ العناصر المتميزة ، يُستخدم مصطلح "العددية" للدلالة على عدد العناصر المتميزة في سلسلة بيانات تحتوي على عناصر متكررة. مع ذلك، في نظرية المجموعات المتعددة، يشير المصطلح إلى مجموع تعددية كل عنصر من عناصر المجموعة المتعددة. وقد اختارت هذه المقالة استخدام تعريف فلايوليت حرصًا على التوافق مع المصادر.

الخوارزمية

تعتمد خوارزمية HyperLogLog على ملاحظة أنه يمكن تقدير عدد عناصر مجموعة متعددة من الأعداد العشوائية الموزعة توزيعًا منتظمًا عن طريق حساب الحد الأقصى لعدد الأصفار البادئة في التمثيل الثنائي لكل عدد في المجموعة. إذا كان الحد الأقصى لعدد الأصفار البادئة الملاحظة هو n ، فإن تقدير عدد العناصر المختلفة في المجموعة هو 2^ n . [ 1 ]  

في خوارزمية HyperLogLog، تُطبَّق دالة تجزئة على كل عنصر في المجموعة المتعددة الأصلية للحصول على مجموعة متعددة من الأرقام العشوائية الموزعة توزيعًا منتظمًا، ولها نفس عدد عناصر المجموعة الأصلية. ويمكن بعد ذلك تقدير عدد عناصر هذه المجموعة الموزعة عشوائيًا باستخدام الخوارزمية المذكورة أعلاه.

يُعاب على التقدير البسيط لعدد العناصر باستخدام الخوارزمية المذكورة أعلاه تباينه الكبير . في خوارزمية HyperLogLog، يُقلل التباين بتقسيم المجموعة المتعددة إلى مجموعات فرعية عديدة، وحساب الحد الأقصى لعدد الأصفار البادئة في أعداد كل مجموعة فرعية، واستخدام المتوسط ​​التوافقي لدمج هذه التقديرات لكل مجموعة فرعية في تقدير لعدد عناصر المجموعة الكاملة. [ 4 ]

العمليات

تتضمن دالة HyperLogLog ثلاث عمليات رئيسية: الإضافة لإضافة عنصر جديد إلى المجموعة، والعد لحساب عدد عناصر المجموعة، والدمج للحصول على اتحاد مجموعتين. ويمكن حساب بعض العمليات المشتقة باستخدام مبدأ الإدراج والاستبعاد، مثل حساب عدد عناصر التقاطع أو الفرق بين مجموعتين من HyperLogLog، وذلك بدمج عمليتي الدمج والعد.

يتم تخزين بيانات HyperLogLog في مصفوفة M من m عدادات (أو "سجلات") يتم تهيئتها إلى 0. تسمى المصفوفة M التي تم تهيئتها من مجموعة متعددة S بمخطط HyperLogLog لـ S.

يضيف

تتضمن عملية الجمع حساب تجزئة بيانات الإدخال v باستخدام دالة التجزئة h ، والحصول على أول b بت (حيث b هوسجل2⁡(م){\textstyle \log _{2}(m)}ثم أضف 1 إليها للحصول على عنوان السجل المراد تعديله (بافتراض أن الفهرسة تبدأ من 1). باستخدام البتات المتبقية كـ w ، احسبρ(w){\textstyle \rho (w)}والتي تُعيد موضع الرقم 1 الأقصى يسارًا، حيث يكون الموضع الأقصى يسارًا هو 1 (بمعنى آخر: عدد الأصفار البادئة زائد 1). ستكون القيمة الجديدة للسجل هي القيمة القصوى بين القيمة الحالية للسجل وρ(w){\textstyle \rho (w)}.

x:=ح(v)ج:=1+⟨x1x2...xب⟩2w:=xب+1xب+2...م[ج]:=الأعلى(م[ج]،ρ(w)){\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}}

عدد

تتألف خوارزمية العد من حساب المتوسط ​​التوافقي للسجلات m ، واستخدام ثابت لاستخلاص تقدير.هـ{\textstyle E}من العدد:

Z=(∑ج=1م2-م[ج])-1{\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}
αم=(م∫0∞(سجل2⁡(2+u1+u))مدu)-1{\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}
هـ=αمم2Z{\displaystyle E=\alpha _{m}m^{2}Z}

الحدس هو أن n هو العدد غير المعروف لعناصر M ، كل مجموعة جزئيةمج{\textstyle M_{j}}سوف يكونن/م{\textstyle n/m}العناصر. ثم الأعلىx∈مجρ(x){\textstyle \max _{x\in M_{j}}\rho (x)}ينبغي أن يكون قريباً منسجل2⁡(ن/م){\textstyle \log _{2}(n/m)}المتوسط ​​التوافقي للعدد 2 لهذه الكميات هومZ{\textstyle mZ}والذي ينبغي أن يكون قريباًن/م{\textstyle n/m}. هكذا،م2Z{\textstyle m^{2}Z}ينبغي أن يكون n تقريبًا.

وأخيراً، الثابتαم{\textstyle \alpha _{m}}تم إدخالها لتصحيح تحيز ضربي منهجي موجود فيم2Z{\textstyle m^{2}Z}بسبب تصادمات التجزئة.

الاعتبارات العملية

الثابتαم{\textstyle \alpha _{m}}ليس من السهل حسابها، ويمكن تقريبها باستخدام الصيغة [ 1 ]

αم≈{0.673،ل م=16؛0.697،ل م=32؛0.709،ل م=64؛0.72131+1.079/م،ل م≥128.{\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{\text{لـ }}m=16;\\0.697,&{\text{لـ }}m=32;\\0.709,&{\text{لـ }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{لـ }}m\geq 128.\end{cases}}}

إلا أن تقنية HyperLogLog متحيزة للأعداد الصغيرة التي تقل عن عتبة معينة.52م{\textstyle {\frac {5}{2}}m}تقترح الورقة الأصلية استخدام خوارزمية مختلفة للأعداد الصغيرة تُعرف باسم العد الخطي. [ 5 ] في حالة كون التقدير المذكور أعلاه أقل من العتبةهـ<52م{\textstyle E<{\frac {5}{2}}m}، ويمكن استخدام الحساب البديل:

  1. يتركV{\textstyle V}ليكن عدد السجلات مساوياً للصفر.
  2. لوV=0{\textstyle V=0}استخدم مُقدِّر HyperLogLog القياسيهـ{\textstyle E}فوق.
  3. وإلا، فاستخدم العد الخطي:هـ⋆=مسجل⁡(مV){\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}

بالإضافة إلى ذلك، بالنسبة للأعداد الكبيرة جدًا التي تقترب من الحد الأقصى لحجم السجلات (هـ>23230{\textstyle E>{\frac {2^{32}}{30}}}بالنسبة للسجلات ذات 32 بت)، يمكن تقدير عدد العناصر باستخدام:

هـ⋆=-232سجل⁡(1-هـ232){\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)}

مع إجراء التصحيحات المذكورة أعلاه للحدود الدنيا والعليا، يمكن تقدير الخطأ على النحو التالي:σ=1.04/م{\textstyle \sigma =1.04/{\sqrt {m}}}.

دمج

عملية دمج نظامي HLL (حلل1،حلل2{\textstyle {\mathit {hll}}_{1}،{\mathit {hll}}_{2}}تتمثل هذه العملية في الحصول على القيمة القصوى لكل زوج من السجلات.ج:1..م{\textstyle j:1..m}

حللالاتحاد[ج]=الأعلى(حلل1[ج]،حلل2[ج]){\displaystyle {\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}

تعقيد

لتحليل التعقيد، يتم استخدام تدفق البيانات(ϵ،دلتا){\displaystyle (\epsilon ,\delta )}يتم استخدام النموذج [ 6 ] ، الذي يحلل المساحة اللازمة للحصول على1±ϵ{\displaystyle 1\pm \epsilon }التقريب باحتمالية نجاح ثابتة1-دلتا{\displaystyle 1-\delta }الخطأ النسبي لـ HLL هو1.04/م{\displaystyle 1.04/{\sqrt {m}}}وهو يحتاجيا(ϵ-2سجل⁡سجل⁡ن+سجل⁡ن){\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}المساحة، حيث n هي عدد عناصر المجموعة و m هو عدد السجلات (عادةً ما يكون أقل من حجم بايت واحد).

تعتمد عملية الجمع على حجم ناتج دالة التجزئة. وبما أن هذا الحجم ثابت، يمكننا اعتبار وقت تشغيل عملية الجمع هويا(1){\displaystyle O(1)}.

تعتمد عمليات العد والدمج على عدد السجلات m، وتبلغ تكلفتها النظرية 10000 .يا(م){\displaystyle O(m)}في بعض التطبيقات ( مثل Redis ) [ 7 ] ، يكون عدد السجلات ثابتًا وتُعتبر التكلفة ثابتة.يا(1){\displaystyle O(1)}في الوثائق.

HLL++

يقترح خوارزمية HyperLogLog++ العديد من التحسينات في خوارزمية HyperLogLog لتقليل متطلبات الذاكرة وزيادة الدقة في بعض نطاقات الأعداد: [ 6 ]

  • تم استخدام دالة تجزئة 64 بت بدلاً من دالة 32 بت المستخدمة في الورقة البحثية الأصلية. هذا يقلل من تصادمات التجزئة للأعداد الكبيرة، مما يسمح بإزالة تصحيح النطاق الكبير.
  • لوحظ وجود بعض التحيز عند التعامل مع أعداد صغيرة من العناصر عند الانتقال من العد الخطي إلى عد HLL. لذا، تم اقتراح تصحيح تجريبي للتحيز للتخفيف من هذه المشكلة.
  • تم اقتراح تمثيل متفرق للسجلات لتقليل متطلبات الذاكرة للأعداد الصغيرة، والتي يمكن تحويلها لاحقًا إلى تمثيل كثيف إذا زاد عدد العناصر.

بث HLL

عندما تصل البيانات في تدفق واحد، يُحسّن مُقدِّر الاحتمال العكسي التاريخي أو مُقدِّر المارتينجال [ 8 ] [ 9 ] دقة رسم HLL بشكل ملحوظ، ويستخدم ذاكرة أقل بنسبة 36% لتحقيق مستوى خطأ مُحدد. ويُثبت أن هذا المُقدِّر هو الأمثل لأي رسم تقريبي للعدّ المُميز غير حساس للتكرار على تدفق واحد.

يؤدي سيناريو التدفق الأحادي أيضًا إلى اختلافات في بنية مخططات لغة البرمجة عالية المستوى (HLL). يستخدم HLL-TailCut+ ذاكرة أقل بنسبة 45% من مخطط HLL الأصلي، ولكن على حساب الاعتماد على ترتيب إدخال البيانات وعدم القدرة على دمج المخططات. [ 10 ]

للمزيد من القراءة

مراجع

  1. 1 2 3 4 5 فلاجو، فيليب؛ فوسي، إريك؛ غاندويه، أوليفييه؛ مونييه، فريدريك (2007). "هايبرلولوج: تحليل خوارزمية تقدير عدد العناصر شبه المثلى" (ملف PDF) . وقائع مؤتمر الرياضيات المتقطعة وعلوم الحاسوب النظرية . AH . نانسي، فرنسا : 137-156 . CiteSeerX 10.1.1.76.4286 . تاريخ الاسترجاع : 11 ديسمبر 2016 . 
  2. ↑ دوراند، م.؛ فلاجو، ب. (2003). "حساب لوغاريتمي لوغاريتمي للأعداد الكبيرة." (ملف PDF) . في: ج. دي باتيستا ويو. زويك (محرران). سلسلة محاضرات في علوم الحاسوب . الندوة الأوروبية السنوية حول الخوارزميات (ESA03). المجلد 2832. سبرينغر. الصفحات 605-617 .  
  3. ↑ فلاجو، فيليب؛ مارتن، جي. نايجل (1985). "خوارزميات العد الاحتمالية لتطبيقات قواعد البيانات" (ملف PDF) . مجلة علوم الحاسوب والنظم . 31 (2): 182-209 . doi : 10.1016/0022-0000(85)90041-8 .
  4. ↑ إس هيول؛ إم نونكيسر؛ إيه هول (2013). "هايبرلوجلوج عمليًا: الهندسة الخوارزمية لخوارزمية تقدير عدد العناصر المتطورة" (ملف PDF) . القسم 4.
  5. ↑ وانغ، كيو-يونغ؛ فاندر-زاندن، براد ت؛ تايلور، هوارد م (1990). "خوارزمية عد احتمالية خطية الزمن لتطبيقات قواعد البيانات" . معاملات ACM لأنظمة قواعد البيانات . 15 (2): 208-229 . doi : 10.1145/78922.78925 . S2CID 2939101 . 
  6. 1 2 "HyperLogLog في الممارسة العملية: الهندسة الخوارزمية لخوارزمية تقدير عدد العناصر المتطورة" . تم الاسترجاع في 19-04-2014 .
  7. ↑ "PFCOUNT – Redis" .
  8. ↑ كوهين، إي. (مارس 2015). "إعادة النظر في رسومات المسافات الكاملة: مُقدِّرات HIP لتحليل الرسوم البيانية الضخمة". معاملات IEEE في هندسة المعرفة والبيانات . 27 (9): 2320-2334 . arXiv : 1306.3284 . doi : 10.1109/TKDE.2015.2411606 .
  9. ↑ تينغ، د. (أغسطس 2014). "العد التقريبي المتدفق للعناصر المتميزة" . وقائع المؤتمر الدولي العشرين لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات . الصفحات 442-451 . doi : 10.1145/2623330.2623669 . ISBN  978-1-4503-2956-9. S2CID 13179875 . 
  10. ↑ شياو، كيو؛ تشو، واي؛ تشين، إس. (مايو 2017). "أداء أفضل مع عدد أقل من البتات: تحسين أداء تقدير عدد العناصر في تدفقات البيانات الكبيرة". مؤتمر IEEE INFOCOM 2017 - مؤتمر IEEE للاتصالات الحاسوبية . الصفحات 1-9 . doi : 10.1109/INFOCOM.2017.8057088 . ISBN  978-1-5090-5336-0. S2CID 27159273 .