ในวิทยาการคอมพิวเตอร์การแฮชแบบไวต่อตำแหน่ง ( LSH ) เป็น เทคนิค การแฮชแบบฟัซซีที่แฮชรายการอินพุตที่คล้ายกันลงใน "ถัง" เดียวกันด้วยความน่าจะเป็นสูง^{[ 1 ]}จำนวนถังมีขนาดเล็กกว่าจักรวาลของรายการอินพุตที่เป็นไปได้มาก^{[ 1 ]}เนื่องจากรายการที่คล้ายกันจะอยู่ในถังเดียวกัน เทคนิคนี้จึงสามารถใช้สำหรับการจัดกลุ่มข้อมูลและการค้นหาเพื่อนบ้านที่ใกล้ที่สุดได้ แตกต่างจากเทคนิคการแฮชแบบดั้งเดิมตรงที่การชนกันของแฮชจะถูกทำให้สูงสุด ไม่ใช่ต่ำสุด หรืออีกนัยหนึ่ง เทคนิคนี้สามารถมองได้ว่าเป็นวิธีลดมิติของข้อมูลที่มีมิติสูง รายการอินพุตที่มีมิติสูงสามารถลดลงเป็นเวอร์ชันที่มีมิติต่ำได้ในขณะที่ยังคงรักษาระยะห่างสัมพัทธ์ระหว่างรายการไว้

โดยทั่วไปแล้ว อัลกอริ ทึม การค้นหาเพื่อนบ้านที่ใกล้ที่สุดโดยประมาณโดยใช้การแฮชจะใช้หนึ่งในสองประเภทหลักของวิธีการแฮช ได้แก่ วิธีการที่ไม่ขึ้นกับข้อมูล เช่น การแฮชแบบไวต่อตำแหน่ง (LSH) หรือวิธีการที่ขึ้นกับข้อมูล เช่น การแฮชแบบรักษาตำแหน่ง (LPH) ^{[ 2 ] [ 3 ]}

การแฮชแบบรักษาตำแหน่งถูกคิดค้นขึ้นในตอนแรกเพื่ออำนวยความสะดวกในการส่งข้อมูลแบบไปป์ไลน์ในการใช้งาน อัลกอริธึม แบบขนานขนาดใหญ่ที่ใช้ การกำหนด เส้นทางแบบสุ่มและการแฮชแบบสากลเพื่อลดการแย่งชิงหน่วย ความจำ และความแออัดของเครือข่าย^{[ 4 ​​] [ 5 ]}

ตระกูล ฟังก์ชันจำกัดถูกกำหนดให้เป็นตระกูล LSH ^{[ 1 ] [ 6 ] [ 7 ]} สำหรับ ${\displaystyle {\mathcal {F}}}$${\displaystyle h\colon M\to S}$

• ปริภูมิ เมตริก​${\displaystyle {\mathcal {M}}=(M,d)}$
• เกณฑ์​${\displaystyle r>0}$
• ปัจจัยการประมาณค่า${\displaystyle c>1}$
• และความน่าจะเป็น${\displaystyle p_{1}>p_{2}}$

หากตรงตามเงื่อนไขต่อไปนี้ สำหรับจุดสองจุดใดๆและฟังก์ชันแฮชที่เลือกแบบสุ่มอย่างสม่ำเสมอจาก: ${\displaystyle a,b\in M}$${\displaystyle h}$${\displaystyle {\mathcal {F}}}$

• ถ้าแล้ว(กล่าวคือaและbชนกัน) ด้วยความน่าจะเป็นอย่างน้อย,${\displaystyle d(a,b)\leq r}$${\displaystyle h(a)=h(b)}$${\displaystyle p_{1}}$
• ถ้าเช่นนั้นด้วยความน่าจะเป็นอย่างมากที่สุด${\displaystyle d(a,b)\geq cr}$${\displaystyle h(a)=h(b)}$${\displaystyle p_{2}}$

ครอบครัวที่มีลักษณะเช่นนี้เรียกว่า ครอบครัว ที่ไวต่อสิ่งต่างๆ (-sensitive) ${\displaystyle {\mathcal {F}}}$${\displaystyle (r,cr,p_{1},p_{2})}$

อีกทางเลือกหนึ่ง^{[ 8 ]}เป็นไปได้ที่จะกำหนดตระกูล LSH บนเอกภพของรายการUที่มีฟังก์ชันความคล้ายคลึงกันในการตั้งค่านี้ แผนการ LSH คือตระกูลของฟังก์ชันแฮชHที่เชื่อมโยงกับการกระจายความน่าจะเป็นDบนHโดยที่ฟังก์ชันที่เลือกตามD เป็นไปตาม เงื่อนไขสำหรับแต่ละ ${\displaystyle \phi \colon U\times U\to [0,1]}$${\displaystyle h\in H}$${\displaystyle Pr[h(a)=h(b)]=\phi (a,b)}$${\displaystyle a,b\in U}$

เมื่อกำหนดตระกูลที่ไวต่อ - แล้วเราสามารถสร้างตระกูลใหม่ได้โดยใช้การสร้างแบบ AND หรือการสร้างแบบ OR ของ^{[ 1 ]}${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\คณิตศาสตร์ {G}}}$${\displaystyle {\mathcal {F}}}$

ในการสร้างโครงสร้าง AND เรากำหนดตระกูลฟังก์ชันแฮช ใหม่ gโดยที่แต่ละฟังก์ชันgถูกสร้างขึ้นจากฟังก์ชันสุ่มk ฟังก์ชัน จาก จากนั้นเรากล่าวว่าสำหรับฟังก์ชันแฮช g = 1 ก็ต่อเมื่อ k ทุกตัวสำหรับk ∈ 1 เนื่องจากสมาชิกของถูกเลือกอย่างอิสระสำหรับ k ใดๆ g จึงเป็นตระกูลที่ไวต่อ k ${\displaystyle {\คณิตศาสตร์ {G}}}$${\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 {\คณิตศาสตร์ {G}}}$${\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}$

ในการสร้างโครงสร้าง OR เรากำหนดตระกูลฟังก์ชันแฮช ใหม่ gโดยที่แต่ละฟังก์ชันgถูกสร้างขึ้นจากฟังก์ชันสุ่มk ฟังก์ชัน จาก จากนั้นเรากล่าวว่าสำหรับฟังก์ชันแฮชก็ต่อเมื่อ สำหรับค่า iอย่างน้อยหนึ่งค่าเนื่องจากสมาชิกของถูกเลือกอย่างอิสระสำหรับ ใดๆจึงเป็นตระกูลที่ไวต่อ (sensitivity family) ${\displaystyle {\คณิตศาสตร์ {G}}}$${\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 {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle {\คณิตศาสตร์ {G}}}$${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}$

LSH ได้ถูกนำไปประยุกต์ใช้กับปัญหาหลายด้าน รวมถึง:

• การตรวจจับการทำซ้ำใกล้เคียง^{[ 9 ]}
• การจัดกลุ่มแบบลำดับชั้น^{[ 10 ] [ 11 ]}
• การศึกษาการเชื่อมโยงทั่วทั้งจีโนม^{[ 12 ]}
• การระบุความคล้ายคลึงของภาพ
  • VisualRank
• การระบุความคล้ายคลึงของการแสดงออกของยีน
• การระบุความคล้ายคลึงของเสียง
• การค้นหาเพื่อนบ้านที่ใกล้ที่สุด
• ลายนิ้วมือเสียง^{[ 13 ]}
• ลายนิ้วมือวิดีโอดิจิทัล^{[ 14 ]}
• การจัดระเบียบ หน่วยความจำร่วมในการประมวลผลแบบขนาน^{[ 4 ] [ 5 ]}
• การจัดระเบียบข้อมูลทางกายภาพในระบบจัดการฐานข้อมูล^{[ 15 ]}
• การฝึกเครือข่ายประสาทที่เชื่อมต่ออย่างสมบูรณ์^{[ 16 ] [ 17 ]}
• ความปลอดภัยของคอมพิวเตอร์^{[ 18 ]}
• การเรียนรู้ของเครื่อง^{[ 19 ]}

หนึ่งในวิธีที่ง่ายที่สุดในการสร้างตระกูล 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}$${\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 ของรายการที่นับได้ และฟังก์ชันความคล้ายคลึงที่สนใจคือดัชนี Jaccard Jถ้าπเป็นการเรียงสับเปลี่ยนบนดัชนีของSให้แต่ละตัวเลือกที่เป็นไปได้ของπ จะกำหนดฟังก์ชันแฮช hเพียงฟังก์ชันเดียวที่แมปเซตอินพุตไปยังองค์ประกอบของ S${\displaystyle A\subseteq S}$${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$

กำหนดให้Hเป็นเซตของฟังก์ชันทั้งหมดดังกล่าว และให้Dเป็นการแจกแจงแบบเอกรูปกำหนดให้เซตสองเซตเหตุการณ์ที่สอดคล้องกับเหตุการณ์ที่ค่าต่ำสุดของπบนอยู่ภายใน เซต นั้น เนื่องจากhถูกเลือกแบบสุ่มอย่างสม่ำเสมอและกำหนดรูปแบบ LSH สำหรับดัชนี Jaccard ${\displaystyle A,B\subseteq S}$${\displaystyle h(A)=h(B)}$${\displaystyle A\cup B}$${\displaystyle A\cap B}$${\displaystyle Pr[h(A)=h(B)]=J(A,B)\,}$${\displaystyle (H,D)\,}$

เนื่องจากกลุ่มสมมาตรบน องค์ประกอบ nมีขนาดn ! การเลือกการเรียงสับเปลี่ยนแบบสุ่ม อย่างแท้จริง จากกลุ่มสมมาตรทั้งหมดจึงเป็นไปไม่ได้แม้แต่สำหรับn ที่มีขนาดปานกลาง ด้วยเหตุนี้จึงมีการทำงานอย่างมากในการค้นหาตระกูลของการเรียงสับเปลี่ยนที่เป็น "อิสระแบบ min-wise" ซึ่งเป็นตระกูลของการเรียงสับเปลี่ยนที่แต่ละองค์ประกอบของโดเมนมีความน่าจะเป็นเท่ากันที่จะเป็นค่าต่ำสุดภายใต้π ที่เลือกแบบสุ่ม ได้มีการพิสูจน์แล้วว่าตระกูลของการเรียงสับเปลี่ยนที่เป็นอิสระ ^แบบ min-wise มีขนาดอย่างน้อย[ ^{20 ]}และขอบเขตนี้แน่น^{[ 21 ]}${\displaystyle \operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{no(n)}}$

เนื่องจากตระกูลอิสระแบบ min-wise มีขนาดใหญ่เกินไปสำหรับการใช้งานจริง จึงมีการแนะนำแนวคิดอิสระแบบ min-wise สองรูปแบบ ได้แก่ ตระกูลการเรียงสับเปลี่ยนอิสระแบบ min-wise ที่จำกัด และตระกูลอิสระแบบ min-wise โดยประมาณ อิสระแบบ min-wise ที่จำกัดคือคุณสมบัติอิสระแบบ min-wise ที่จำกัดไว้เฉพาะเซตที่มีขนาดไม่เกินk [ ^{22 ] อิสระ} แบบ min-wise โดยประมาณจะแตกต่างจากคุณสมบัตินี้โดยมีค่า ε คงที่ไม่เกินค่าใดค่าหนึ่ง^{[ 23 ]}

Nilsimsaเป็นอัลกอริธึมแฮชที่ไวต่อตำแหน่งที่ใช้ในความพยายามต่อต้านสแปม^{[ 24 ]}เป้าหมายของ Nilsimsa คือการสร้างแฮชไดเจสต์ของข้อความอีเมลเพื่อให้ไดเจสต์ของข้อความที่คล้ายกันสองข้อความมีความคล้ายคลึงกัน เอกสารแนะนำว่า Nilsimsa ตรงตามข้อกำหนดสามประการ:

1. ค่าสรุปที่ระบุแต่ละข้อความไม่ควรเปลี่ยนแปลงอย่างมีนัยสำคัญสำหรับการเปลี่ยนแปลงที่สามารถสร้างขึ้นโดยอัตโนมัติได้
2. ระบบการเข้ารหัสต้องมีความแข็งแกร่งต่อการโจมตีโดยเจตนา
3. ระบบการเข้ารหัสควรช่วยลดความเสี่ยงของการเกิดผลลัพธ์ที่ผิดพลาดได้อย่างมาก

การทดสอบที่ดำเนินการในเอกสารเกี่ยวกับประเภทไฟล์ต่างๆ พบว่าแฮช Nilsimsa มีอัตราการเกิดผลบวกเท็จที่สูงกว่าอย่างมีนัยสำคัญเมื่อเปรียบเทียบกับรูปแบบการย่อยความคล้ายคลึงอื่นๆ เช่น TLSH, Ssdeep และ Sdhash ^{[ 25 ]}

TLSHเป็นอัลกอริธึมแฮชที่ไวต่อตำแหน่งที่ออกแบบมาสำหรับการใช้งานด้านความปลอดภัยและนิติวิทยาศาสตร์ดิจิทัลหลายประเภท^{[ 18 ]}เป้าหมายของ TLSH คือการสร้างแฮชไดเจสต์สำหรับข้อความโดยที่ระยะห่างต่ำระหว่างไดเจสต์บ่งชี้ว่าข้อความที่เกี่ยวข้องมีแนวโน้มที่จะคล้ายกัน

การใช้งาน TLSH มีให้บริการในรูปแบบซอฟต์แวร์โอเพนซอร์ส^{[ 26 ]}

วิธีการฉายภาพแบบสุ่มของ LSH เนื่องมาจากMoses Charikar ^{[ 8 ]}เรียกว่าSimHash (บางครั้งเรียกว่า arccos ^{[ 27 ]} ) ใช้การประมาณระยะทางโคไซน์ระหว่างเวกเตอร์ เทคนิคนี้ใช้ในการประมาณปัญหาmax-cut ที่สมบูรณ์แบบ NP ^{[ 8 ]}

แนวคิดพื้นฐานของเทคนิคนี้คือการเลือกไฮเปอร์เพลน แบบสุ่ม (กำหนดโดยเวกเตอร์หน่วยปกติr ) ในตอนเริ่มต้น และใช้ไฮเปอร์เพลนนั้นในการแฮชเวกเตอร์อินพุต

เมื่อกำหนดเวกเตอร์อินพุตvและระนาบไฮเปอร์ที่กำหนดโดยrเราจะให้นั่นคือ ขึ้นอยู่กับว่า v อยู่ ด้านใดของระนาบไฮเปอร์ด้วยวิธีนี้ การเลือกระนาบไฮเปอร์แบบสุ่มr แต่ละแบบ สามารถตีความได้ว่าเป็นฟังก์ชันแฮช ${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$${\displaystyle h(v)=\pm 1}$${\displaystyle h(v)}$

สำหรับเวกเตอร์สองตัวคือ u และ vที่มีมุมระหว่างกัน สามารถแสดงได้ว่า ${\displaystyle \theta (u,v)}$

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

เนื่องจากอัตราส่วนระหว่างและมีค่าอย่างน้อย 0.439 เมื่อ[ ^{8 ] [ 28 ] ความ}น่าจะเป็นที่เวกเตอร์สองตัวจะอยู่คนละด้านของระนาบไฮเปอร์แบบสุ่มจะเป็นสัดส่วนโดยประมาณกับระยะทางโคไซน์ระหว่างเวกเตอร์ทั้งสอง ${\displaystyle {\frac {\theta (u,v)}{\pi }}}$${\displaystyle 1-\cos(\theta (u,v))}$${\displaystyle \theta (u,v)\in [0,\pi ]}$

ฟังก์ชันแฮช ^{[ 29 ]} แมปเวกเตอร์มิติ dไปยังเซตของจำนวนเต็ม ฟังก์ชันแฮชแต่ละฟังก์ชันในตระกูลนี้จะถูกจัดทำดัชนีโดยการเลือกแบบสุ่มและ โดยที่เป็น เวกเตอร์มิติ dที่มีรายการที่เลือกอย่างอิสระจากการกระจายแบบเสถียรและ เป็นจำนวนจริงที่เลือกอย่างสม่ำเสมอจากช่วง [0,r] สำหรับค่าคง ที่ ฟังก์ชันแฮชจะกำหนดโดย ${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$${\displaystyle {\boldsymbol {\upsilon }}}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\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 ]}รหัสแฮชจะถูกค้นพบผ่านการฝึกเครือข่ายประสาทเทียมหรือแบบจำลองกราฟิก

หนึ่งในแอปพลิเคชันหลักของ LSH คือการจัดหาวิธีการสำหรับอัลกอริธึ ม การค้นหาเพื่อนบ้านที่ใกล้ที่สุด โดยประมาณที่มีประสิทธิภาพ พิจารณาตระกูล LSH อัลกอริธึมนี้มี พารามิเตอร์ หลักสองตัว ได้แก่ พารามิเตอร์ความกว้างkและจำนวนตารางแฮชL${\displaystyle {\mathcal {F}}}$

ในขั้นตอนแรก เรากำหนดตระกูลฟังก์ชันแฮช ใหม่ gโดยที่แต่ละฟังก์ชันgได้มาจากการต่อ ฟังก์ชัน kฟังก์ชันจากนั่นคือ. กล่าวอีกนัยหนึ่ง ฟังก์ชันแฮชแบบสุ่มgได้มาจากการนำ ฟังก์ชันแฮชที่เลือกแบบสุ่ม kฟังก์ชันจาก มาต่อกัน จากนั้น อัลกอริทึมจะสร้าง ตารางแฮช Lตาราง โดยแต่ละตารางจะสอดคล้องกับฟังก์ชันแฮชgที่ เลือกแบบสุ่มที่แตกต่างกัน${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g(p)=[h_{1}(p),\ldots ,h_{k}(p)]}$${\displaystyle {\mathcal {F}}}$

ในขั้นตอนการประมวลผลล่วงหน้า เราจะสร้างแฮชให้กับ จุดข้อมูล n จุดที่มีมิติ dจากชุดข้อมูลS ลงในตารางแฮช L ตาราง แต่ละตารางเนื่องจากตารางแฮชที่ได้จะมี ค่าที่ไม่เป็นศูนย์เพียง nค่า เท่านั้น จึงสามารถลดปริมาณหน่วยความจำที่ใช้ต่อตารางแฮชแต่ละตารางลงได้โดย ใช้ ฟังก์ชันแฮชมาตรฐาน${\displaystyle O(n)}$

เมื่อกำหนดจุดสอบถามqแล้ว อัลกอริทึมจะวนซ้ำไปตามฟังก์ชันแฮชg จำนวน L ฟังก์ชัน สำหรับแต่ละgที่พิจารณา จะดึงจุดข้อมูลที่ถูกแฮชลงในบัคเก็ตเดียวกันกับq กระบวนการจะหยุดลงทันทีที่ พบ จุดที่อยู่ภายในระยะทางcRจากq

เมื่อกำหนดพารามิเตอร์kและLแล้ว อัลกอริทึมนี้จะรับประกันประสิทธิภาพดังต่อไปนี้:

• เวลาในการประมวลผลล่วงหน้า: โดยที่t คือเวลาในการ ประเมินฟังก์ชันบนจุดอินพุตp${\displaystyle O(nLkt)}$${\displaystyle h\in {\mathcal {F}}}$
• พื้นที่: บวกกับพื้นที่สำหรับจัดเก็บจุดข้อมูล;${\displaystyle O(nL)}$
• เวลาในการค้นหา: ;${\displaystyle O(L(kt+dnP_{2}^{k}))}$
• อัลกอริทึมจะประสบความสำเร็จในการค้นหาจุดที่อยู่ภายในระยะทางcRจากq (หากมีจุดที่อยู่ภายในระยะทางR ) ด้วยความน่าจะเป็นอย่างน้อย;${\displaystyle 1-(1-P_{1}^{k})^{L}}$

สำหรับอัตราส่วนการประมาณค่าและค่าความน่า จะเป็นคงที่ และเราสามารถกำหนดและโดยที่ จากนั้นจะได้การรับประกันประสิทธิภาพดังต่อไปนี้: ${\displaystyle c=1+\epsilon }$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle k=\left\lceil {\tfrac {\log n}{\log 1/P_{2}}}\right\rceil }$${\displaystyle L=\lceil P_{1}^{-k}\rceil =O(n^{\rho }P_{1}^{-1})}$${\displaystyle \rho ={\tfrac {\log P_{1}}{\log P_{2}}}}$

• เวลาในการประมวลผลล่วงหน้า: ;${\displaystyle O(n^{1+\rho }P_{1}^{-1}kt)}$
• พื้นที่: บวกกับพื้นที่สำหรับจัดเก็บจุดข้อมูล;${\displaystyle O(n^{1+\rho }P_{1}^{-1})}$
• เวลาในการค้นหา: ;${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d))}$

เพื่อให้อัลกอริทึมข้างต้นเป็นแบบทั่วไปโดยไม่ต้องกำหนดรัศมี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มีขนาดใหญ่ จะสามารถลดเวลาแฮชจาก ได้ซึ่งแสดงให้เห็นโดย^{[ 33 ]}และ^{[ 34 ]}ซึ่งให้ ${\displaystyle O(n^{\rho })}$

• เวลาในการค้นหา: ;${\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})}$

บางครั้งปัจจัยดังกล่าวอาจมีขนาดใหญ่มาก ตัวอย่างเช่น เกิดขึ้นกับ ข้อมูล ความคล้ายคลึงของ Jaccardซึ่งแม้แต่เพื่อนบ้านที่คล้ายคลึงที่สุดก็มักจะมีความคล้ายคลึงของ Jaccard กับแบบสอบถามค่อนข้างต่ำ ใน^{[ 35 ]}ได้แสดงวิธีการลดเวลาการค้นหา(ไม่รวมค่าใช้จ่ายในการแฮช) และลดการใช้พื้นที่ในทำนองเดียวกัน ${\displaystyle 1/P_{1}}$${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$

• Bloom filter  – โครงสร้างข้อมูลสำหรับการประมาณค่าสมาชิกเซต
• คำสาปแห่งมิติ  – ความยากลำบากที่เกิดขึ้นเมื่อวิเคราะห์ข้อมูลที่มีหลายแง่มุม ("มิติ")
• การแฮชคุณลักษณะ  – การแปลงคุณลักษณะให้เป็นเวกเตอร์โดยใช้ฟังก์ชันแฮช
• การแปลงที่เกี่ยวข้องกับฟูริเยร์
• Geohash  – ระบบระบุพิกัดทางภูมิศาสตร์แบบสาธารณะที่คิดค้นขึ้นในปี 2008
• การเรียนรู้ซับสเปซเชิงเส้นหลายตัว  – แนวทางการลดมิติ
• การวิเคราะห์ส่วนประกอบหลัก  – วิธีการวิเคราะห์ข้อมูล
• การจัดทำดัชนีแบบสุ่ม^{[ 36 ]}
• โรลลิ่งแฮช  – ประเภทหนึ่งของฟังก์ชันแฮช
• การแยกส่วนค่าเอกลักษณ์  – การแยกส่วนเมทริกซ์
• หน่วยความจำแบบกระจายที่เบาบาง  – แบบจำลองทางคณิตศาสตร์ของหน่วยความจำ
• การบีบอัดแบบเวฟเล็ต  – เทคนิคทางคณิตศาสตร์ที่ใช้ในการบีบอัดและวิเคราะห์ข้อมูลPages displaying short descriptions of redirect targets
• ความใกล้เคียงของการอ้างอิง  – แนวโน้มของหน่วยประมวลผลที่จะเข้าถึงตำแหน่งหน่วยความจำที่อยู่ใกล้เคียงกันในเชิงพื้นที่หรือเวลา

• Samet, H. (2006) พื้นฐานของโครงสร้างข้อมูลหลายมิติและเมตริก Morgan Kaufmann. ISBN 0-12-369446-9
• Indyk, Piotr ; Motwani, Rajeev ; Raghavan, Prabhakar; Vempala, Santosh (1997). "การแฮชแบบรักษาความเฉพาะที่ในปริภูมิหลายมิติ". รายงานการประชุมสัมมนาประจำปีครั้งที่ 29 ของ ACM เรื่องทฤษฎีการคำนวณ STOC '97หน้า  618–625 . CiteSeerX  10.1.1.50.4927 . doi : 10.1145/258533.258656 . ISBN 978-0-89791-888-6S2CID 15693787​ ​
• Chin, Andrew (1994). "ฟังก์ชันแฮชที่รักษาความเฉพาะที่สำหรับการคำนวณแบบขนานทั่วไป" (PDF) . Algorithmica . 12 ( 2– 3): 170– 181. doi : 10.1007/BF01185209 . S2CID  18108051 .

• โฮมเพจ LSH ของ Alex Andoni
• LSHKIT: ไลบรารีแฮชแบบคำนึงถึงตำแหน่งที่ตั้งในภาษา C++
• ไลบรารี Python สำหรับสร้างแฮชแบบ Locality Sensitive Hashing ที่รองรับการจัดเก็บข้อมูลถาวรผ่าน Redis (เป็นตัวเลือกเสริม)
• Caltech Large Scale Image Search Toolbox : ชุดเครื่องมือ Matlab ที่ใช้ฟังก์ชันแฮช LSH หลายฟังก์ชัน รวมถึงอัลกอริธึม Kd-Trees, Hierarchical K-Means และ Inverted File search ด้วย
• Slash: ไลบรารี LSH ที่เขียนด้วยภาษา C++ ซึ่งใช้ Spherical LSH โดย Terasawa, K. และ Tanaka, Y.
• LSHBOX: ชุดเครื่องมือโอเพนซอร์สที่เขียนด้วยภาษา C++ สำหรับการแฮชแบบคำนึงถึงตำแหน่งที่ตั้ง เพื่อการค้นหารูปภาพขนาดใหญ่ รองรับ Python และ MATLAB ด้วย
• SRS: การใช้งานอัลกอริธึมการประมวลผลการค้นหาเพื่อนบ้านที่ใกล้ที่สุดโดยประมาณแบบประหยัดพื้นที่และประมวลผลในหน่วยความจำ โดยใช้ภาษา C++ ซึ่งอิงตามการฉายภาพแบบสุ่มที่มีเสถียรภาพ p
• TLSH เป็นโอเพนซอร์สบน Github
• TLSH (Trend Micro Locality Sensitive Hashing) เวอร์ชัน JavaScript ที่รวมอยู่ในโมดูล Node.js
• TLSH (Trend Micro Locality Sensitive Hashing) เวอร์ชัน Java ที่รวมอยู่ในแพ็คเกจ Maven