مينهاش

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 23 صور
الموسوعة الحرة

في علوم الحاسوب واستخراج البيانات ، تُعدّ MinHash (أو خوارزمية التجزئة الحساسة للموقع باستخدام التبديلات المستقلة الدنيا ) تقنيةً لتقدير مدى تشابه مجموعتين من البيانات بسرعة. نُشرت هذه الخوارزمية بواسطة أندريه برودر في مؤتمر عام 1997، [ 1 ] واستُخدمت في البداية في محرك البحث AltaVista لاكتشاف صفحات الويب المكررة واستبعادها من نتائج البحث. [ 2 ] كما طُبّقت في مسائل التجميع واسعة النطاق ، مثل تجميع المستندات بناءً على تشابه مجموعات الكلمات فيها. [ 1 ]

تشابه جاكارد وقيم التجزئة الدنيا

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

ج(أ،ب)=|أ∩ب||أ∪ب|.{\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}.}

تكون هذه القيمة صفرًا عندما تكون المجموعتان منفصلتين ، وواحدًا عندما تكونان متساويتين، وقيمة بين صفر وواحد فيما عدا ذلك. تكون المجموعتان أكثر تشابهًا (أي تحتويان على عدد أكبر نسبيًا من العناصر المشتركة) عندما يكون مؤشر جاكارد الخاص بهما أقرب إلى 1. يهدف MinHash إلى تقدير J ( A , B ) بسرعة، دون حساب التقاطع والاتحاد بشكل صريح.

لتكن h دالة تجزئة تربط عناصر المجموعة U بأعداد صحيحة مختلفة، ولتكن perm تبديلاً عشوائياً لعناصر المجموعة U ، ولأي مجموعة جزئية S من U ، عرّف h min ( S ) على أنها أصغر عنصر في S بالنسبة إلى h ∘ perm ، أي العنصر x في S الذي يحقق أصغر قيمة لـ h ( perm ( x )) . (في الحالات التي يُفترض فيها أن دالة التجزئة المستخدمة لها خصائص شبه عشوائية، لا يُستخدم التبديل العشوائي).

الآن، بتطبيق h min على كل من A و B ، وبافتراض عدم وجود تصادمات تجزئة، نرى أن القيم متساوية ( h min ( A ) = h min ( B ) ) إذا وفقط إذا كان ذلك بين جميع عناصرأ∪ب{\displaystyle A\cup B}، العنصر ذو أقل قيمة تجزئة يقع في التقاطعأ∩ب{\displaystyle A\cap B}وبالتالي، فإن احتمال صحة هذا الأمر هو بالضبط مؤشر جاكارد:

برو[حمين(أ)=حمين(ب)]=ج(أ،ب)،{\displaystyle {\text{Pr}}[h_{\text{min}}(A)=h_{\text{min}}(B)]=J(A,B),}

أي أن احتمال تحقق المعادلة h min ( A ) = h min ( B ) يساوي قيمة التشابه J ( A , B ) ، بافتراض سحب العينات من توزيع منتظم. بعبارة أخرى، إذا كان r هو المتغير العشوائي الذي يساوي واحدًا عندما h min ( A ) = h min ( B ) وصفرًا فيما عدا ذلك، فإن r يُعدّ مُقدِّرًا غير متحيز لـ J ( A , B ) . يتميز r بتباين عالٍ جدًا يجعله غير مناسب كمُقدِّر لتشابه جاكارد بمفرده، لأنر{\displaystyle r}تكون القيمة دائمًا إما صفرًا أو واحدًا. وتتلخص فكرة مخطط MinHash في تقليل هذا التباين عن طريق حساب متوسط ​​عدة متغيرات تم إنشاؤها بنفس الطريقة.

الخوارزمية

نوع يحتوي على العديد من دوال التجزئة

تستخدم أبسط نسخة من مخطط minhash k من دوال التجزئة المختلفة، حيث k هو معلمة عددية ثابتة، وتمثل كل مجموعة S بواسطة قيم h min ( S ) لهذه الدوال k .

لتقدير J ( A , B ) باستخدام هذه النسخة من المخطط، ليكن y عدد دوال التجزئة التي تحقق hmin ( A ) = hmin ( B ) ، ولنستخدم y / k كتقدير. هذا التقدير هو متوسط ​​k من المتغيرات العشوائية 0-1 المختلفة، كل منها يساوي واحدًا عندما hmin ( A ) = hmin ( B ) وصفرًا فيما عدا ذلك، وكل منها مقدر غير متحيز لـ J ( A , B ) . لذلك، فإن متوسطها هو أيضًا مقدر غير متحيز، وبحسب الانحراف المعياري لمجموع المتغيرات العشوائية 0-1، فإن خطأه المتوقع هو O ( 1/ √k ) . [ 3 ]

لذا، لأي ثابت ε > 0، يوجد ثابت k = O(1/ ε² ) بحيث يكون الخطأ المتوقع للتقدير على الأكثر ε . على سبيل المثال، يلزم 400 عملية تجزئة لتقدير J ( A , B ) بخطأ متوقع أقل من أو يساوي 0.05. 

صيغة بديلة ذات دالة تجزئة واحدة

قد يكون حساب دوال التجزئة المتعددة مكلفًا حسابيًا، لكن نسخة مشابهة من خوارزمية MinHash تتجنب هذه التكلفة باستخدام دالة تجزئة واحدة فقط، وتستخدمها لاختيار قيم متعددة من كل مجموعة بدلًا من اختيار قيمة دنيا واحدة فقط لكل دالة تجزئة. لنفترض أن h دالة تجزئة، و k عددًا صحيحًا ثابتًا. إذا كانت S أي مجموعة من k قيمة أو أكثر في مجال h ، فإن h ( k ) ( S ) تُعرَّف بأنها المجموعة الجزئية من عناصر S التي لها أصغر قيم h . تُستخدم هذه المجموعة الجزئية h ( k ) ( S ) كتوقيع للمجموعة S ، ويتم تقدير تشابه أي مجموعتين بمقارنة توقيعيهما.

على وجه التحديد، ليكن A و B أي مجموعتين. عندئذٍ ، X = h ( k ) ( h ( k ) ( A ) ∪ h ( k ) ( B )) = h ( k ) ( A ∪ B ) هي مجموعة من k عنصرًا من A ∪ B ، وإذا كانت h دالة عشوائية، فإن أي مجموعة جزئية من k عنصرًا يكون احتمال اختيارها متساويًا؛ أي أن X عينة عشوائية بسيطة من A ∪ B. المجموعة الجزئية Y = X ∩ h ( k ) ( A ) ∩ h ( k ) ( B ) هي مجموعة عناصر X التي تنتمي إلى التقاطع A ∩ B. بالتالي، فإن | Y |/ k هو مُقدِّر غير متحيز لـ J ( A , B ) . الفرق بين هذا المُقدِّر والمُقدِّر الناتج عن دوال تجزئة متعددة هو أن X تحتوي دائمًا على k عنصرًا بالضبط، بينما قد تؤدي دوال التجزئة المتعددة إلى عدد أقل من العناصر المأخوذة عينةً نظرًا لاحتمالية أن يكون لدالتين تجزئة مختلفتين نفس القيمة الدنيا. ومع ذلك، عندما تكون قيمة k صغيرة بالنسبة لأحجام المجموعات، يكون هذا الاختلاف ضئيلاً.

وفقًا لحدود تشيرنوف القياسية لأخذ العينات بدون استبدال، فإن هذا المقدر لديه خطأ متوقع O(1/ √ k ) ، وهو ما يطابق أداء مخطط دالة التجزئة المتعددة.

تحليل الوقت

يمكن حساب المُقدِّر | Y | / k في زمن O( k ) من التوقيعين للمجموعتين المُعطاة، في أيٍّ من صيغتي المخطط. لذلك، عندما يكون كلٌّ من ε و k ثابتين، يكون زمن حساب التشابه المُقدَّر من التوقيعين ثابتًا أيضًا. يمكن حساب توقيع كل مجموعة في زمن خطي بالنسبة لحجم المجموعة، لذا عندما يلزم تقدير العديد من أوجه التشابه الثنائية، يمكن أن تؤدي هذه الطريقة إلى توفير كبير في زمن التشغيل مقارنةً بإجراء مقارنة كاملة لعناصر كل مجموعة. تحديدًا، بالنسبة لحجم المجموعة n، تستغرق صيغة التجزئة المتعددة زمن O( nk ) . أما صيغة التجزئة الفردية فهي أسرع عمومًا، إذ تتطلب زمن O( n ) للحفاظ على قائمة قيم التجزئة الدنيا بافتراض أن n >> k . [ 1 ]

دمج الأوزان

طُوِّرت تقنيات متنوعة لإدخال الأوزان في حساب MinHashes. أبسطها هو توسيعها لتشمل الأوزان الصحيحة. [ 4 ] نُوسِّع دالة التجزئة h لتقبل كلاً من عنصر مجموعة وعدد صحيح، ثم نُنشئ تجزئات متعددة لكل عنصر، وفقًا لوزنه. إذا تكرر العنصر i عدد n من المرات، نُنشئ تجزئاتح(أنا،1)،ح(أنا،2)،...،ح(أنا،ن){\displaystyle h(i,1),h(i,2),\ldots ,h(i,n)}قم بتشغيل الخوارزمية الأصلية على هذه المجموعة الموسعة من التجزئات. سيؤدي ذلك إلى الحصول على مؤشر جاكارد الموزون كاحتمالية للتصادم.

جدبليو(x،y)=∑أنامين(xأنا،yأنا)∑أناالأعلى(xأنا،yأنا){\displaystyle J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}}

تم تطوير امتدادات إضافية تحقق احتمالية التصادم هذه على الأوزان الحقيقية مع وقت تشغيل أفضل، إحداها للبيانات الكثيفة، [ 5 ] والأخرى للبيانات المتفرقة. [ 6 ]

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

ح(x)=أرزمأنانأنا-سجل⁡(ح(أنا))xأنا{\displaystyle H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}}

وهذا ينتج عنه احتمال التصادم، وهو مؤشر جاكارد [ 7 ]

جP(x،y)=∑xأنا≠0yأنا≠01∑جالأعلى(xجxأنا،yجyأنا){\displaystyle J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}}

التباديل المستقلة على مستوى الحد الأدنى

لتطبيق مخطط MinHash كما هو موضح أعلاه، نحتاج إلى دالة التجزئة h لتعريف تبديل عشوائي على n عنصرًا، حيث n هو العدد الإجمالي للعناصر المختلفة في اتحاد جميع المجموعات المراد مقارنتها. ولكن نظرًا لوجود n ! تبديلًا مختلفًا، سيتطلب الأمر Ω ( n log n ) بتًا لتحديد تبديل عشوائي حقيقي، وهو عدد كبير جدًا حتى بالنسبة للقيم المتوسطة لـ n . لهذا السبب، وبالقياس على نظرية التجزئة الشاملة ، بُذلت جهود كبيرة لإيجاد مجموعة من التبديلات "المستقلة عن الحد الأدنى"، أي أنه لأي مجموعة جزئية من المجال، يكون احتمال أن يكون أي عنصر هو الحد الأدنى متساويًا. وقد ثبت أن مجموعة التبديلات المستقلة عن الحد الأدنى يجب أن تتضمن على الأقل

المضاعف المشترك الأصغر⁡(1،2،⋯،ن)≥هـن-o(ن){\displaystyle \operatorname {lcm} (1,2,\cdots ,n)\geq e^{no(n)}}

[ 2 ] تباديل مختلفة، وبالتالي يتطلب الأمر Ω ( n ) بت لتحديد تبديل واحد، وهو عدد كبير بشكل غير عملي.

دوال التجزئة المستقلة العملية ذات الحد الأدنى

نظراً لعدم جدوى ما سبق، تم تقديم مفهومين بديلين للاستقلال الأدنى: عائلات التباديل المستقلة الأدنى المقيدة، وعائلات الاستقلال الأدنى التقريبية. الاستقلال الأدنى المقيد هو خاصية الاستقلال الأدنى المقيدة بمجموعات معينة لا يتجاوز عدد عناصرها k . [ 8 ] أما الاستقلال الأدنى التقريبي، فله احتمال ثابت ε على الأكثر للانحراف عن الاستقلال الكامل. [ 9 ]

في عام 1999، أثبت بيوتر إنديك [ 10 ] أن أي عائلة مستقلة من دوال التجزئة k-wise تكون أيضًا مستقلة تقريبًا min-wise لـك{\displaystyle k}كبيرة بما يكفي. على وجه الخصوص، هناك ثوابتج،ج′>0{\displaystyle c,c'>0}بحيث إذاك≥جسجل⁡1ϵ{\displaystyle k\geq c\log {\tfrac {1}{\epsilon }}}، ثم

بروح∈ح[ح(x)<مينح(X)]=1|X|+1(1±ϵ)،{\displaystyle \Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),}

لجميع المجموعات|X|≤ϵنج′{\displaystyle |X|\leq \epsilon nc'}وx∉X{\displaystyle x\not \in X}(ملاحظة، هنا)(1±ϵ){\displaystyle (1\pm \epsilon )}يعني أن الاحتمالية هي على الأكثر عامل1+ϵ{\displaystyle 1+\epsilon }كبير جدًا، وفي أحسن الأحوال1-ϵ{\displaystyle 1-\epsilon }صغير جدًا.)

هذا الضمان، من بين أمور أخرى، كافٍ لتوفير حد جاكارد المطلوب لخوارزمية مين هاش. أي، إذاأ{\displaystyle A}وب{\displaystyle B}إذا كانت مجموعات، فإن

بروح∈ح[مينح(أ)=مينح(ب)]=|أ∩ب||أ∪ب|±ϵ.{\displaystyle \Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .}

بما أنه يمكن تحديد دوال التجزئة المستقلة k-wise باستخدام فقطكسجل⁡ن{\displaystyle k\log n}بتات، هذا النهج أكثر عملية بكثير من استخدام التباديل المستقلة تمامًا من حيث الحد الأدنى.

هناك عائلة أخرى عملية من دوال التجزئة التي تعطي استقلالًا تقريبيًا على أساس الحد الأدنى وهي التجزئة الجدولية .

التطبيقات

تضمنت التطبيقات الأصلية لـ MinHash تجميع وإزالة التكرارات المتقاربة بين مستندات الويب، والتي تُمثل بمجموعات الكلمات الواردة في تلك المستندات. [ 1 ] [ 2 ] [ 11 ] كما استُخدمت تقنيات مماثلة لتجميع وإزالة التكرارات المتقاربة لأنواع أخرى من البيانات، مثل الصور: ففي حالة بيانات الصور، يمكن تمثيل الصورة كمجموعة من الصور الفرعية الأصغر حجمًا المُقتطعة منها، أو كمجموعات من أوصاف ميزات الصورة الأكثر تعقيدًا. [ 12 ]

في مجال استخراج البيانات ، استخدم كوهين وآخرون (2001) خوارزمية MinHash كأداة لتعلم قواعد الارتباط . فعند وجود قاعدة بيانات تحتوي كل مدخلة فيها على سمات متعددة (تُعرض كمصفوفة ثنائية الأبعاد، صف لكل مدخلة في قاعدة البيانات وعمود لكل سمة)، استخدموا تقريبات MinHash لمؤشر جاكارد لتحديد أزواج السمات المرشحة التي تتكرر معًا بشكل متكرر، ثم قاموا بحساب القيمة الدقيقة للمؤشر لتلك الأزواج فقط لتحديد تلك التي تقل ترددات تكرارها عن عتبة صارمة محددة. [ 13 ]

تم تكييف خوارزمية MinHash لعلم المعلوماتية الحيوية ، حيث تتشابه الأسس النظرية لمشكلة مقارنة تسلسلات الجينوم مع تلك الخاصة بمقارنة المستندات على الإنترنت. تتيح الأدوات القائمة على MinHash [ 14 ] [ 15 ] مقارنة سريعة لبيانات تسلسل الجينوم الكامل مع الجينومات المرجعية (حوالي 3 دقائق لمقارنة جينوم واحد مع 90000 جينوم مرجعي في RefSeq )، وهي مناسبة لتحديد الأنواع وربما لتصنيف الأنواع الفرعية الميكروبية بدرجة محدودة. كما توجد تطبيقات في علم الجينوم البيئي [ 14 ] واستخدام الخوارزميات المشتقة من MinHash لمحاذاة الجينوم وتجميعه [ 16 ] . ويمكن توليد قيم دقيقة لمتوسط ​​هوية النيوكليوتيدات (ANI) بكفاءة عالية باستخدام الخوارزميات القائمة على MinHash [ 17 ] .

استخدامات أخرى

يمكن اعتبار مخطط MinHash مثالًا على التجزئة الحساسة للموقع ، وهي مجموعة من التقنيات التي تستخدم دوال التجزئة لربط مجموعات كبيرة من الكائنات بقيم تجزئة أصغر، بحيث عندما تكون المسافة بين كائنين صغيرة، فمن المرجح أن تكون قيم التجزئة الخاصة بهما متطابقة. في هذه الحالة، يمكن اعتبار توقيع المجموعة بمثابة قيمة التجزئة الخاصة بها. توجد تقنيات تجزئة حساسة للموقع أخرى لحساب مسافة هامينغ بين المجموعات ومسافة جيب التمام بين المتجهات ؛ وللتجزئة الحساسة للموقع تطبيقات مهمة في خوارزميات البحث عن أقرب جار . [ 18 ] بالنسبة للأنظمة الموزعة الكبيرة، وخاصة MapReduce ، توجد نسخ معدلة من MinHash للمساعدة في حساب أوجه التشابه دون الاعتماد على بُعد النقطة. [ 19 ]

التقييم والمعايير

أجرت جوجل تقييمًا واسع النطاق في عام 2006 [ 20 ] لمقارنة أداء خوارزميتي Minhash و SimHash [ 21 ] . وفي عام 2007، أفادت جوجل باستخدامها خوارزمية Simhash للكشف عن المحتوى المكرر في عمليات الزحف على الويب [ 22 ] ، واستخدامها خوارزميتي Minhash و LSH لتخصيص تجربة المستخدم في أخبار جوجل [ 23 ] .

انظر أيضاً

مراجع

  1. 1 2 3 4 برودر، أندريه ز. (1998)، "حول تشابه واحتواء المستندات"، وقائع مؤتمر ضغط وتعقيد التسلسلات 1997 (رقم التصنيف 97TB100171) (ملف PDF) ، معهد مهندسي الكهرباء والإلكترونيات ، الصفحات 21-29 ، CiteSeerX 10.1.1.24.779 ، doi : 10.1109/SEQUEN.1997.666900 ، ISBN   978-0-8186-8132-5، S2CID 11748509 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 31 يناير 2015 ، تم استرجاعه بتاريخ 18 يناير 2014 .
  2. 1 2 3 برودر، أندريه ز .؛ شاريكار، موسى؛ فريز، آلان م .؛ ميتزنماخر، مايكل (1998)، "التباديل المستقلة الدنيا"، وقائع الندوة الثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '98) ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة ، الصفحات 327-336 ، CiteSeerX 10.1.1.409.9220 ، doi : 10.1145/276698.276781 ، ISBN   978-0897919623، S2CID 465847 .
  3. ↑ فاسيلفيتسكي، سيرجي (2011)، COMS 6998-12: التعامل مع البيانات الضخمة (ملاحظات محاضرة، جامعة كولومبيا) (ملف PDF) ، مؤرشف من الأصل (ملف PDF) بتاريخ 24-10-2018.
  4. ↑ تشوم، أوندري؛ فيلبين، جيمس؛ زيسرمان، أندرو (2008)، " الكشف عن الصور المتشابهة تقريبًا: ترجيح min-Hash و tf-idf." (ملف PDF) ، BMVC ، 810 : 812-815
  5. ↑ شريفاستافا، أنشومالي (2016)، "التجزئة الدقيقة الموزونة الدنيا في وقت ثابت"، arXiv : 1602.08393 [ cs.DS ]
  6. ↑ إيوف، سيرجي (2010). "تحسين أخذ العينات المتسقة، والتجزئة الموزونة، ورسم L1". المؤتمر الدولي لهندسة الكهرباء والإلكترونيات لعام 2010 حول استخراج البيانات (ملف PDF) . الصفحات 246-255 . CiteSeerX 10.1.1.227.9749 . doi : 10.1109/ICDM.2010.80 . ISBN   978-1-4244-9131-5. S2CID 9970906 . 
  7. ↑ مولتون، رايان؛ جيانغ، يونجيانغ (2018)، "أخذ العينات المتسقة إلى أقصى حد ومؤشر جاكارد لتوزيعات الاحتمالات"، المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2018 حول استخراج البيانات (ICDM) ، الصفحات 347-356 ، arXiv : 1809.04052 ، doi : 10.1109/ICDM.2018.00050 ، ISBN  978-1-5386-9159-5، S2CID 49746072 
  8. ↑ ماتوسيك، جيري ؛ Stojakovi، Miloš (2003)، “في استقلال التباديل المحدود”، الهياكل والخوارزميات العشوائية ، 23 (4): 397–408 ، CiteSeerX 10.1.1.400.6757 ، دوى : 10.1002/rsa.10101 ، S2CID 1483449  .
  9. ↑ ساكس، م .؛ سرينيفاسان، أ.؛ تشو، س.؛ زوكرمان، د. (2000)، "مجموعات التباين المنخفض تُنتج عائلات تبديل مستقلة تقريبية على مستوى الحد الأدنى"، رسائل معالجة المعلومات ، 73 ( 1-2 ): 29-32 ، CiteSeerX 10.1.1.20.8264 ، doi : 10.1016/S0020-0190(99)00163-5 .
  10. ↑ إنديك، بيوتر. "عائلة صغيرة مستقلة تقريبًا من دوال التجزئة." مجلة الخوارزميات 38.1 (2001): 84-90.
  11. ↑ ماناس، مارك (2012). حول التحديد الفعال لأقرب الجيران: حدوات الخيل، والقنابل اليدوية، والبحث عبر الإنترنت، وغيرها من المواقف التي يكون فيها القرب كافيًا . مورغان وكلايبول. ص 72. ISBN  9781608450886.
  12. ↑ تشوم، أوندريج؛ فيلبين، جيمس؛ إيسارد، مايكل؛ زيسرمان، أندرو (2007)، "كشف الصور واللقطات المتطابقة تقريبًا والقابل للتطوير"، وقائع المؤتمر الدولي السادس لجمعية الحوسبة الآلية (ACM) حول استرجاع الصور والفيديوهات (CIVR'07) ، الصفحات 549-556 ، doi : 10.1145/1282280.1282359 ، ISBN  9781595937339، S2CID 3330908 تشوم ، أوندريج؛ فيلبين، جيمس؛ زيسرمان، أندرو (2008)، "الكشف عن الصور المتشابهة تقريبًا: ترجيح التجزئة الدنيا و tf-idf"، وقائع المؤتمر البريطاني لرؤية الآلة (ملف PDF) ، المجلد 3، ص 4  .
  13. ↑ كوهين، إي .؛ داتار، م.؛ فوجيوارا، س.؛ جيونيس، أ.؛ إنديك، ب .؛ موتاني، ر .؛ أولمان، ج. د .؛ يانغ، س. (2001)، "إيجاد ارتباطات مثيرة للاهتمام دون تقليم الدعم"، معاملات IEEE في هندسة المعرفة والبيانات ، 13 (1): 64-78 ، Bibcode : 2001IDSO...13...64C ، CiteSeerX 10.1.1.192.7385 ، doi : 10.1109/69.908981 .
  14. أوندوف ، برايان د.؛ تريانجن، تود ج.؛ ميلستيد، بال؛ مالوني، آدم ب.؛ بيرغمان، نيكولاس هـ.؛ كورين، سيرجي؛ فيليبي، آدم م. (2016-06-20). "ماش: تقدير سريع للمسافة بين الجينوم والميتاجينوم باستخدام مينهاش" . علم الأحياء الجينومي . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . ISSN 1474-760X . PMC 4915045. PMID 27323842 .   
  15. ↑ "مرحباً بكم في سورماش! — وثائق سورماش 1.0" . sourmash.readthedocs.io . تم ​​الاطلاع عليه بتاريخ 13 نوفمبر 2017 .
  16. ↑ برلين، كونستانتين؛ كورين، سيرجي؛ تشين، تشين-شان؛ دريك، جيمس ب؛ لاندولين، جين م؛ فيليبي، آدم م (25-05-2015). "تجميع الجينومات الكبيرة باستخدام تسلسل الجزيء المفرد والتجزئة الحساسة للموقع". مجلة Nature Biotechnology . 33 (6): 623-630 . Bibcode : 2015NatBi..33..623B . doi : 10.1038 / nbt.3238 . ISSN 1546-1696 . PMID 26006009. S2CID 17246729 .   
  17. ↑ جاين، شيراغ؛ رودريغيز-ر، لويس م.؛ فيليبي، آدم م.؛ كونستانتينيديس، كونستانتينوس ت.؛ ألورو، سرينيفاس (ديسمبر 2018). "تحليل ANI عالي الإنتاجية لـ 90 ألف جينوم بدائي النواة يكشف عن حدود واضحة بين الأنواع" . Nature Communications . 9 (1): 5114. Bibcode : 2018NatCo...9.5114J . doi : 10.1038/ s41467-018-07641-9 . PMC 6269478. PMID 30504855 .  
  18. ↑ أندوني، ألكسندر؛ إنديك، بيوتر (2008)، "خوارزميات التجزئة شبه المثلى لإيجاد أقرب جار تقريبي في الأبعاد العالية"، مجلة اتصالات رابطة مكائن ​​الحوسبة ، 51 (1): 117-122 ، CiteSeerX 10.1.1.226.6905 ، doi : 10.1145/1327452.1327494 ، S2CID 6468963  .
  19. ↑ زاده، رضا؛ جويل، أشيش (2012)، "حساب التشابه المستقل عن الأبعاد"، arXiv : 1206.2082 [ cs.DS ].
  20. ↑ هينزينجر، مونيكا (2006)، "إيجاد صفحات ويب شبه متطابقة: تقييم واسع النطاق للخوارزميات"، وقائع المؤتمر الدولي السنوي التاسع والعشرين لجمعية ACM SIGIR حول البحث والتطوير في استرجاع المعلومات ، ص 284 ، doi : 10.1145/1148170.1148222 ، ISBN  978-1595933690، S2CID 207160068 .
  21. ↑ شاريكار، موسى س. (2002)، "تقنيات تقدير التشابه من خوارزميات التقريب"، وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 380-388 ، doi : 10.1145/509907.509965 ، ISBN  978-1581134957، S2CID 4229473 .
  22. ↑ غورميت سينغ، مانكو؛ جاين، أرفيند؛ داس سارما، أنيش (2007)، "الكشف عن النسخ المتطابقة تقريبًا لزحف الويب"، وقائع المؤتمر الدولي السادس عشر للويب العالمي (ملف PDF) ، ص 141، doi : 10.1145/1242572.1242592 ، ISBN  9781595936547، S2CID 1414324 .
  23. ↑ داس، أبهيناندان س.؛ داتار، مايور؛ غارغ، أشوتوش؛ راجارام، شيام؛ وآخرون (2007)، "تخصيص أخبار جوجل: ترشيح تعاوني قابل للتطوير عبر الإنترنت"، وقائع المؤتمر الدولي السادس عشر للويب العالمي ، ص 271، doi : 10.1145/1242572.1242610 ، ISBN   9781595936547، S2CID 207163129 .