التجزئة الحساسة للموقع

بدلاً من ذلك ^{[ 8 ]،} من الممكن تعريف عائلة LSH على مجموعة من العناصر U مزودة بدالة تشابه${\displaystyle \phi \colon U\times U\to [0,1]}$في هذا السياق، تُعرَّف خوارزمية LSH بأنها مجموعة من دوال التجزئة H مقترنة بتوزيع احتمالي D على H بحيث تكون الدالة${\displaystyle h\in H}$يتم الاختيار وفقًا لـ D يرضي${\displaystyle Pr[h(a)=h(b)]=\phi (a,b)}$لكل${\displaystyle a,b\in U}$.

بافتراض${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$عائلة حساسة${\displaystyle {\mathcal {F}}}$يمكننا بناء عائلات جديدة${\displaystyle {\mathcal {G}}}$إما عن طريق بناء "و" أو بناء "أو"${\displaystyle {\mathcal {F}}}$[ ^{1 ]​}

لإنشاء بنية AND، نقوم بتعريف عائلة جديدة${\displaystyle {\mathcal {G}}}$من دوال التجزئة g ، حيث يتم إنشاء كل دالة g من k دوال عشوائية${\displaystyle h_{1},\ldots ,h_{k}}$من${\displaystyle {\mathcal {F}}}$ثم نقول ذلك بالنسبة لدالة التجزئة${\displaystyle g\in {\mathcal {G}}}$،${\displaystyle g(x)=g(y)}$إذا وفقط إذا كان كل${\displaystyle h_{i}(x)=h_{i}(y)}$ل${\displaystyle i=1,2,\ldots ,k}$منذ أعضاء${\displaystyle {\mathcal {F}}}$يتم اختيارهم بشكل مستقل لأي${\displaystyle g\in {\mathcal {G}}}$،${\displaystyle {\mathcal {G}}}$هو${\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}$عائلة حساسة.

لإنشاء بنية OR، نقوم بتعريف عائلة جديدة${\displaystyle {\mathcal {G}}}$من دوال التجزئة g ، حيث يتم إنشاء كل دالة g من k دوال عشوائية${\displaystyle h_{1},\ldots ,h_{k}}$من${\displaystyle {\mathcal {F}}}$ثم نقول ذلك بالنسبة لدالة التجزئة${\displaystyle g\in {\mathcal {G}}}$،${\displaystyle g(x)=g(y)}$إذا وفقط إذا${\displaystyle h_{i}(x)=h_{i}(y)}$لقيمة واحدة أو أكثر من قيم i . بما أن أعضاء${\displaystyle {\mathcal {F}}}$يتم اختيارهم بشكل مستقل لأي${\displaystyle g\in {\mathcal {G}}}$،${\displaystyle {\mathcal {G}}}$هو${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}$عائلة حساسة.

إحدى أسهل الطرق لإنشاء عائلة LSH هي أخذ عينات من البتات. ^{[ 7 ]} هذه الطريقة فعالة لحساب مسافة هامينغ على المتجهات ذات الأبعاد d.${\displaystyle \{0,1\}^{d}}$هنا، العائلة${\displaystyle {\mathcal {F}}}$إن مجموعة دوال التجزئة هي ببساطة عائلة جميع إسقاطات النقاط على أحد${\displaystyle d}$الإحداثيات، أي${\displaystyle {\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ لبعض }}i\in \{1,\ldots ,d\}\}}$، أين${\displaystyle x_{i}}$هو${\displaystyle i}$الإحداثي رقم th لـ${\displaystyle x}$دالة عشوائية${\displaystyle h}$من${\displaystyle {\mathcal {F}}}$ببساطة، يختار بتًا عشوائيًا من نقطة الإدخال. تحتوي هذه المجموعة على المعلمات التالية:${\displaystyle P_{1}=1-R/d}$،${\displaystyle P_{2}=1-cR/d}$أي متجهين${\displaystyle x,y}$بمسافة هامينغ على الأكثر${\displaystyle R}$تصادم تحت تأثير عشوائي${\displaystyle h}$باحتمالية لا تقل عن${\displaystyle P_{1}}$. أي${\displaystyle x,y}$بمسافة هامينغ على الأقل${\displaystyle cR}$الاصطدام باحتمالية لا تتجاوز${\displaystyle P_{2}}$.

لنفترض أن U تتكون من مجموعات جزئية من مجموعة أساسية من العناصر القابلة للعد S، وأن دالة التشابه محل الاهتمام هي مؤشر جاكارد J. إذا كان π تبديلاً على مؤشرات S ، لـ${\displaystyle A\subseteq S}$يترك${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$. كل اختيار ممكن لـ π يحدد دالة تجزئة واحدة h تقوم بربط مجموعات الإدخال بعناصر S.

عرّف عائلة الدوال H بأنها مجموعة جميع هذه الدوال، ولتكن D هي التوزيع المنتظم . بفرض مجموعتين${\displaystyle A,B\subseteq S}$الحدث الذي${\displaystyle h(A)=h(B)}$يتوافق هذا تمامًا مع الحدث الذي يكون فيه أصغر قيمة لـ π على${\displaystyle A\cup B}$يكمن في الداخل${\displaystyle A\cap B}$بما أن قيمة h تم اختيارها عشوائياً وبشكل منتظم،${\displaystyle Pr[h(A)=h(B)]=J(A,B)\,}$و${\displaystyle (H,D)\,}$قم بتحديد مخطط LSH لمؤشر جاكارد.

نظرًا لأن المجموعة المتناظرة على n عنصرًا حجمها n !، فإن اختيار تبديل عشوائي حقيقي من المجموعة المتناظرة الكاملة غير ممكن حتى بالنسبة لـ n ذي الحجم المتوسط . ولهذا السبب، بُذلت جهود كبيرة لإيجاد عائلة من التبديلات "المستقلة عند الحد الأدنى" - وهي عائلة تبديلات يكون لكل عنصر من عناصر المجال فيها احتمال متساوٍ لكونه أصغر قيمة تحت قيمة π مختارة عشوائيًا . وقد ثبت أن عائلة التبديلات المستقلة عند الحد الأدنى حجمها على الأقل n!${\displaystyle \operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{no(n)}}$[ ^{20 ]} وأن هذا الحد محكم ^{. [ 21 ]}

نظرًا لأن العائلات المستقلة على المستوى الأدنى كبيرة جدًا بالنسبة للتطبيقات العملية، فقد تم تقديم مفهومين بديلين للاستقلال على المستوى الأدنى: عائلات التباديل المستقلة على المستوى الأدنى المقيدة، والعائلات المستقلة على المستوى الأدنى التقريبية. الاستقلال على المستوى الأدنى المقيد هو خاصية الاستقلال على المستوى الأدنى المقيدة بمجموعات معينة لا يتجاوز عدد عناصرها k . ^{[ 22 ]} ويختلف الاستقلال على المستوى الأدنى التقريبي عن الخاصية بمقدار ثابت ε على الأكثر . ^{[ 23 ]}

تستخدم طريقة الإسقاط العشوائي لخوارزمية LSH، التي ابتكرها موسى شاريكار ^{[ 8 ]} وتُسمى SimHash (وتُعرف أحيانًا باسم arccos ^{[ 27 ]} )، تقريبًا لمسافة جيب التمام بين المتجهات. وقد استُخدمت هذه التقنية لتقريب مسألة القطع الأقصى NP-complete . ^{[ 8 ]}

تتمثل الفكرة الأساسية لهذه التقنية في اختيار مستوى فائق عشوائي (محدد بواسطة متجه وحدة عادي r ) في البداية واستخدام المستوى الفائق لتجزئة متجهات الإدخال.

بفرض وجود متجه إدخال v ومستوى فائق معرف بواسطة r ، فإننا نضع${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$. إنه، ${\displaystyle h(v)=\pm 1}$اعتمادًا على أي جانب من المستوى الفائق يقع v . وبهذه الطريقة، يمكن تفسير كل اختيار ممكن لمستوى فائق عشوائي r كدالة تجزئة.${\displaystyle h(v)}$.

للمتجهين u و v بزاوية${\displaystyle \theta (u,v)}$ويمكن إثبات ذلك بينهما.

${\displaystyle Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}.}$

بما أن النسبة بين${\displaystyle {\frac {\theta (u,v)}{\pi }}}$و${\displaystyle 1-\cos(\theta (u,v))}$تكون القيمة 0.439 على الأقل عندما${\displaystyle \theta (u,v)\in [0,\pi ]}$[ ^{8 ] [ 28 ]} احتمال وجود متجهين على جانبين مختلفين من المستوى الفائق العشوائي يتناسب تقريبًا مع ^مسافة جيب التمام بينهما.

دالة التجزئة ^{[ 29 ]}${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$رسم متجه ذي أبعاد d${\displaystyle {\boldsymbol {\upsilon }}}$على مجموعة الأعداد الصحيحة. يتم فهرسة كل دالة تجزئة في العائلة باختيار عشوائي${\displaystyle \mathbf {a} }$و ${\displaystyle b}$أين${\displaystyle \mathbf {a} }$هو متجه ذو أبعاد d، يتم اختيار عناصره بشكل مستقل من توزيع مستقر و ${\displaystyle b}$هو عدد حقيقي يتم اختياره بشكل منتظم من النطاق [0، r]. لقيمة ثابتة ${\displaystyle \mathbf {a} ,b}$دالة التجزئة${\displaystyle h_{\mathbf {a} ,b}}$يُعطى بواسطة${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor }$.

تم اقتراح طرق بناء أخرى لدوال التجزئة لتحسين ملاءمتها للبيانات. ^{[ 30 ]} وعلى وجه الخصوص، فإن دوال التجزئة k-means أفضل عمليًا من دوال التجزئة القائمة على الإسقاط، ولكن دون أي ضمان نظري.

التجزئة الدلالية هي تقنية تحاول ربط عناصر الإدخال بالعناوين بحيث يكون للإدخالات الأقرب تشابه دلالي أعلى . ^{[ 31 ]} يتم إيجاد رموز التجزئة من خلال تدريب شبكة عصبية اصطناعية أو نموذج رسومي .

لتعميم الخوارزمية المذكورة أعلاه دون تثبيت نصف القطر R ، يمكننا أخذ الخوارزمية وإجراء نوع من البحث الثنائي على R. وقد ثبت ^{[ 32 ]} وجود بنية بيانات لأقرب جار تقريبي مع ضمانات الأداء التالية:

• فضاء:${\displaystyle O(n^{1+\rho }P_{1}^{-1}d\log ^{2}n)}$؛
• وقت الاستعلام:${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d)\log n)}$؛
• تنجح الخوارزمية في إيجاد أقرب جار باحتمالية لا تقل عن${\displaystyle 1-((1-P_{1}^{k})^{L}\log n)}$؛

عندما تكون قيمة t كبيرة، فمن الممكن تقليل وقت التجزئة من${\displaystyle O(n^{\rho })}$وقد تم إثبات ذلك من خلال ^{[ 33 ]} و ^{[ 34 ]} اللذين أعطيا

• وقت الاستعلام:${\displaystyle O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1}))}$؛
• فضاء:${\displaystyle O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})}$؛

وفي بعض الأحيان يكون العامل${\displaystyle 1/P_{1}}$قد يكون حجم البيانات كبيرًا جدًا. يحدث هذا، على سبيل المثال، مع بيانات تشابه جاكارد ، حيث غالبًا ما يكون تشابه جاكارد بين أقرب جار والاستعلام منخفضًا جدًا. في ^{[ 35 ]} ، تم توضيح كيفية تقليل وقت الاستعلام إلى${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$(باستثناء تكاليف التجزئة) وبالمثل استخدام المساحة.