Hashing sensible a la localidad

Técnica algorítmica que utiliza hash

En informática , el hash sensible a la localidad ( LSH ) es una técnica de hash difuso que divide elementos de entrada similares en los mismos "cubos" con alta probabilidad. ^[1] (La cantidad de cubos es mucho menor que el universo de posibles elementos de entrada). ^[1] Dado que los elementos similares terminan en los mismos cubos, esta técnica se puede utilizar para la agrupación de datos y la búsqueda del vecino más cercano . Se diferencia de las técnicas de hash convencionales en que las colisiones de hash se maximizan, no se minimizan. Alternativamente, la técnica puede verse como una forma de reducir la dimensionalidad de los datos de alta dimensión; los elementos de entrada de alta dimensión se pueden reducir a versiones de baja dimensión mientras se preservan las distancias relativas entre los elementos.

Los algoritmos de búsqueda de vecino más cercano aproximado basados ​​en hash generalmente utilizan una de dos categorías principales de métodos de hash: métodos independientes de los datos, como el hash sensible a la localidad (LSH); o métodos dependientes de los datos, como el hash que preserva la localidad (LPH). ^{[2] [3]}

El hash con preservación de localidad fue inicialmente concebido como una forma de facilitar la canalización de datos en implementaciones de algoritmos masivamente paralelos que utilizan enrutamiento aleatorio y hash universal para reducir la contención de memoria y la congestión de la red . ^{[4] [5]}

Definiciones

Una familia finita de funciones se define como una familia LSH ^{[1] [6] [7]} para ${\displaystyle {\mathcal {F}}}$ ${\displaystyle h\colon M\to S}$

• un espacio métrico , ${\displaystyle {\mathcal {M}}=(M,d)}$
• un umbral , ${\displaystyle r>0}$
• un factor de aproximación , ${\displaystyle c>1}$
• y probabilidades ${\displaystyle p_{1}>p_{2}}$

Si se cumple la siguiente condición: Para dos puntos cualesquiera y una función hash elegida de manera uniforme al azar entre : ${\displaystyle a,b\in M}$ ${\displaystyle h}$ ${\displaystyle {\mathcal {F}}}$

• Si , entonces (es decir, a y b chocan) con una probabilidad de al menos , ${\displaystyle d(a,b)\leq r}$ ${\displaystyle h(a)=h(b)}$ ${\displaystyle p_{1}}$
• Si , entonces con probabilidad como máximo . ${\displaystyle d(a,b)\geq cr}$ ${\displaystyle h(a)=h(b)}$ ${\displaystyle p_{2}}$

A una familia así se le llama -sensible. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle (r,cr,p_{1},p_{2})}$

LSH con respecto a una medida de similitud

Alternativamente ^[8] es posible definir una familia LSH en un universo de elementos U dotados de una función de similitud . En este contexto, un esquema LSH es una familia de funciones hash H acopladas a una distribución de probabilidad D sobre H tal que una función elegida según D satisface para cada . ${\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}$

Amplificación

Dada una familia sensible , podemos construir nuevas familias mediante la construcción AND o la construcción OR de . ^[1] ${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {F}}}$

Para crear una construcción AND, definimos una nueva familia de funciones hash g , donde cada función g se construye a partir de k funciones aleatorias de . Entonces decimos que para una función hash , si y solo si todas para . Dado que los miembros de se eligen independientemente para cualquier , es una familia sensible a . ${\displaystyle {\mathcal {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 {\mathcal {G}}}$ ${\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}$

Para crear una construcción OR, definimos una nueva familia de funciones hash g , donde cada función g se construye a partir de k funciones aleatorias de . Entonces decimos que para una función hash , si y solo si para uno o más valores de i . Dado que los miembros de se eligen independientemente para cualquier , es una familia sensible a . ${\displaystyle {\mathcal {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 {\mathcal {G}}}$ ${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}$

Aplicaciones

LSH se ha aplicado a varios dominios problemáticos, entre ellos:

• Detección de duplicados cercanos ^[9]
• Agrupamiento jerárquico ^{[10] [11]}
• Estudio de asociación de todo el genoma ^[12]
• Identificación de similitud de imágenes
  • VisualRank
• Identificación de similitud de expresión genética ^{[ cita requerida ]}
• Identificación de similitud de audio
• Búsqueda de vecino más cercano
• Huella de audio ^[13]
• Huella digital de vídeo
• Organización de la memoria compartida en computación paralela ^{[4] [5]}
• Organización física de datos en sistemas de gestión de bases de datos ^[14]
• Entrenamiento de redes neuronales completamente conectadas ^{[15] [16]}
• Seguridad informática ^[17]
• Aprendizaje automático ^[18]

Métodos

Muestreo de bits para la distancia de Hamming

Una de las formas más sencillas de construir una familia LSH es mediante muestreo de bits. ^[7] Este enfoque funciona para la distancia de Hamming sobre vectores d -dimensionales . Aquí, la familia de funciones hash es simplemente la familia de todas las proyecciones de puntos en una de las coordenadas, es decir, , donde es la coordenada ésima de . Una función aleatoria de simplemente selecciona un bit aleatorio del punto de entrada. Esta familia tiene los siguientes parámetros: , . Es decir, dos vectores cualesquiera con distancia de Hamming como máximo colisionan bajo un aleatorio con probabilidad de al menos . Cualquiera con distancia de Hamming como mínimo colisiona con probabilidad de como máximo . ${\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{ for some }}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}}$

Permutaciones independientes min-por-min

Supongamos que U está compuesto de subconjuntos de un conjunto básico de elementos enumerables S y que la función de similitud de interés es el índice de Jaccard J. Si π es una permutación de los índices de S , para sea . Cada posible elección de π define una única función hash h que asigna conjuntos de entrada a elementos de S. ${\displaystyle A\subseteq S}$ ${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$

Defina la familia de funciones H como el conjunto de todas esas funciones y sea D la distribución uniforme . Dados dos conjuntos, el evento que corresponde exactamente al evento de que el minimizador de π sobre se encuentre dentro de . Como h se eligió de manera uniforme al azar, defina un esquema LSH para el índice de 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)\,}$

Como el grupo simétrico de n elementos tiene un tamaño n !, la elección de una permutación verdaderamente aleatoria del grupo simétrico completo es inviable incluso para n de tamaño moderado . Debido a este hecho, se ha trabajado mucho para encontrar una familia de permutaciones que sea "min-independiente" —una familia de permutaciones para la que cada elemento del dominio tenga la misma probabilidad de ser el mínimo bajo un π elegido aleatoriamente . Se ha establecido que una familia de permutaciones independiente min-independiente tiene al menos un tamaño , ^[19] y que este límite es estricto. ^[20] ${\displaystyle \operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{n-o(n)}}$

Debido a que las familias independientes en función de los valores mínimos son demasiado grandes para aplicaciones prácticas, se introducen dos nociones variantes de independencia en función de los valores mínimos: familias de permutaciones independientes en función de los valores mínimos restringidas y familias independientes en función de los valores mínimos aproximadas. La independencia en función de los valores mínimos restringida es la propiedad de independencia en función de los valores mínimos restringida a ciertos conjuntos de cardinalidad como máximo k . ^[21] La independencia en función de los valores mínimos aproximada difiere de la propiedad en como máximo un ε fijo . ^[22]

Métodos de código abierto

Hash de Nilsimsa

Nilsimsa es un algoritmo de hash sensible a la localidad que se utiliza en iniciativas antispam . ^[23] El objetivo de Nilsimsa es generar un resumen de hash de un mensaje de correo electrónico de modo que los resúmenes de dos mensajes similares sean similares entre sí. El artículo sugiere que Nilsimsa satisface tres requisitos:

1. El resumen que identifica cada mensaje no debe variar significativamente por los cambios que se pueden producir automáticamente.
2. La codificación debe ser robusta contra ataques intencionales.
3. La codificación debe soportar un riesgo extremadamente bajo de falsos positivos.

Las pruebas realizadas en el documento sobre una variedad de tipos de archivos identificaron que el hash Nilsimsa tiene una tasa de falsos positivos significativamente mayor en comparación con otros esquemas de resumen de similitud como TLSH, Ssdeep y Sdhash. ^[24]

TLSH

TLSH es un algoritmo hash sensible a la localidad diseñado para una variedad de aplicaciones forenses digitales y de seguridad. ^[17] El objetivo de TLSH es generar resúmenes hash para mensajes de modo que las distancias bajas entre los resúmenes indiquen que es probable que sus mensajes correspondientes sean similares.

Una implementación de TLSH está disponible como software de código abierto . ^[25]

Proyección aleatoria

${\displaystyle {\frac {\theta (u,v)}{\pi }}}$es proporcional a en el intervalo [0, ] ${\displaystyle 1-\cos(\theta (u,v))}$ ${\displaystyle \pi }$

El método de proyección aleatoria de LSH creado por Moses Charikar ^[8], llamado SimHash (también llamado a veces arccos ^[26] ), utiliza una aproximación de la distancia del coseno entre vectores. La técnica se utilizó para aproximar el problema de corte máximo NP-completo . ^[8]

La idea básica de esta técnica es elegir un hiperplano aleatorio (definido por un vector unitario normal r ) desde el principio y utilizar el hiperplano para generar hash en los vectores de entrada.

Dado un vector de entrada v y un hiperplano definido por r , hacemos que . Es decir, depende de qué lado del hiperplano v se encuentre. De esta manera, cada posible elección de un hiperplano aleatorio r puede interpretarse como una función hash . ${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$ ${\displaystyle h(v)=\pm 1}$ ${\displaystyle h(v)}$

Para dos vectores u,v con ángulo entre ellos, se puede demostrar que ${\displaystyle \theta (u,v)}$

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

Dado que la relación entre y es al menos 0,87856 cuando , ^{[8] [27]} la probabilidad de que dos vectores estén en el mismo lado del hiperplano aleatorio es aproximadamente proporcional a la distancia del coseno entre ellos. ${\displaystyle {\frac {\theta (u,v)}{\pi }}}$ ${\displaystyle 1-\cos(\theta (u,v))}$ ${\displaystyle \theta (u,v)\in [0,\pi ]}$

Distribuciones estables

La función hash ^[28] asigna un vector d -dimensional al conjunto de números enteros. Cada función hash de la familia está indexada por una elección aleatoria de y donde es un vector d -dimensional con entradas elegidas independientemente de una distribución estable y es un número real elegido uniformemente del rango [0,r]. Para un fijo la función hash está dada por . ${\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 }$

Se han propuesto otros métodos de construcción de funciones hash para ajustar mejor los datos. ^[29] En particular, las funciones hash k-means son mejores en la práctica que las funciones hash basadas en proyecciones, pero sin ninguna garantía teórica.

Hashing semántico

El hash semántico es una técnica que intenta asignar elementos de entrada a direcciones de modo que las entradas más cercanas tengan una mayor similitud semántica . ^[30] Los códigos hash se encuentran mediante el entrenamiento de una red neuronal artificial o un modelo gráfico . ^{[ cita requerida ]}

Algoritmo para la búsqueda del vecino más cercano

Una de las principales aplicaciones de LSH es proporcionar un método para algoritmos eficientes de búsqueda aproximada del vecino más próximo . Consideremos una familia LSH . El algoritmo tiene dos parámetros principales: el parámetro de ancho k y el número de tablas hash L. ${\displaystyle {\mathcal {F}}}$

En el primer paso, definimos una nueva familia de funciones hash g , donde cada función g se obtiene concatenando k funciones de , es decir, . En otras palabras, una función hash aleatoria g se obtiene concatenando k funciones hash elegidas aleatoriamente de . A continuación, el algoritmo construye L tablas hash, cada una correspondiente a una función hash g diferente elegida aleatoriamente . ${\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}}}$

En el paso de preprocesamiento, convertimos todos los puntos n d- dimensionales del conjunto de datos S en cada una de las L tablas hash. Dado que las tablas hash resultantes tienen solo n entradas distintas de cero, se puede reducir la cantidad de memoria utilizada por cada tabla hash utilizando funciones hash estándar . ${\displaystyle O(n)}$

Dado un punto de consulta q , el algoritmo itera sobre las L funciones hash g . Para cada g considerado, recupera los puntos de datos que están codificados en el mismo contenedor que q . El proceso se detiene tan pronto como se encuentra un punto dentro de la distancia cR desde q .

Dados los parámetros k y L , el algoritmo tiene las siguientes garantías de rendimiento:

• tiempo de preprocesamiento: , donde t es el tiempo para evaluar una función en un punto de entrada p ; ${\displaystyle O(nLkt)}$ ${\displaystyle h\in {\mathcal {F}}}$
• espacio: , más el espacio para almacenar puntos de datos; ${\displaystyle O(nL)}$
• tiempo de consulta: ; ${\displaystyle O(L(kt+dnP_{2}^{k}))}$
• el algoritmo logra encontrar un punto dentro de la distancia cR desde q (si existe un punto dentro de la distancia R ) con una probabilidad al menos ; ${\displaystyle 1-(1-P_{1}^{k})^{L}}$

Para una razón de aproximación fija y probabilidades y , se puede establecer y , donde . Entonces se obtienen las siguientes garantías de rendimiento: ${\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}}}}$

• tiempo de preprocesamiento :; ${\displaystyle O(n^{1+\rho }P_{1}^{-1}kt)}$
• espacio: , más el espacio para almacenar puntos de datos; ${\displaystyle O(n^{1+\rho }P_{1}^{-1})}$
• tiempo de consulta: ; ${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d))}$

Mejoras

Cuando t es grande, es posible reducir el tiempo de hash de . Esto se demostró en ^[31] y ^[32], que dieron ${\displaystyle O(n^{\rho })}$

• tiempo de consulta: ; ${\displaystyle O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1}))}$
• espacio: ; ${\displaystyle O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})}$

También ocurre a veces que el factor puede ser muy grande. Esto sucede, por ejemplo, con los datos de similitud Jaccard , donde incluso el vecino más similar suele tener una similitud Jaccard bastante baja con la consulta. En ^[33] se mostró cómo reducir el tiempo de consulta (sin incluir los costos de hash) y, de manera similar, el uso del espacio. ${\displaystyle 1/P_{1}}$ ${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$

Véase también

• Filtro Bloom  : estructura de datos para la pertenencia aproximada a un conjunto
• La maldición de la dimensionalidad  : dificultades que surgen al analizar datos con muchos aspectos ("dimensiones")
• Hashing de características  : vectorización de características mediante una función hash
• Transformadas relacionadas con Fourier
• Geohash  : geocodificación de dominio público inventada en 2008
• Aprendizaje de subespacios multilineales  : enfoque para la reducción de la dimensionalidad
• Análisis de componentes principales  – Método de análisis de datos
• Indexación aleatoria ^[34]
• Rolling hash  – Tipo de función hash
• Descomposición en valores singulares  – Descomposición matricial
• Memoria distribuida dispersa  : modelo matemático de la memoria
• Compresión wavelet  : técnica matemática utilizada en la compresión y análisis de datos.Pages displaying short descriptions of redirect targets

Referencias

1. Rajaraman, A.; Ullman, J. (2010). "Extracción de conjuntos de datos masivos, cap. 3".
2. Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). Hash que preserva la localidad. Conferencia AAAI sobre Inteligencia Artificial. vol. 28. págs. 2874–2880.
3. Tsai, Yi-Hsuan; Yang, Ming-Hsuan (octubre de 2014). "Hashing que preserva la localidad". Conferencia internacional sobre procesamiento de imágenes (ICIP) del IEEE de 2014. págs. 2988–2992. doi :10.1109/ICIP.2014.7025604. ISBN 978-1-4799-5751-4. ISSN  1522-4880. S2CID  8024458.
4. Chin, Andrew (1991). Problemas de complejidad en computación paralela de propósito general (DPhil). Universidad de Oxford. págs. 87–95.
5. Chin, Andrew (1994). "Funciones hash que preservan la localidad para computación paralela de propósito general" (PDF) . Algorithmica . 12 (2–3): 170–181. doi :10.1007/BF01185209. S2CID  18108051.
6. Gionis, A.; Indyk, P.; Motwani , R. (1999). "Búsqueda de similitud en grandes dimensiones mediante hash". Actas de la 25.ª Conferencia sobre bases de datos de gran tamaño (VLDB) .
7. Indyk, Piotr .; Motwani, Rajeev . (1998). "Vecinos más próximos aproximados: hacia la eliminación de la maldición de la dimensionalidad". Actas del 30º Simposio sobre teoría de la computación .
8. Charikar, Moses S. (2002). "Técnicas de estimación de similitud a partir de algoritmos de redondeo". Actas del 34.º Simposio anual de la ACM sobre teoría de la computación . págs. 380–388. CiteSeerX 10.1.1.147.4064 . doi :10.1145/509907.509965. ISBN.  1-58113-495-9.
9. Das, Abhinandan S.; et al. (2007), "Personalización de noticias de Google: filtrado colaborativo en línea escalable", Actas de la 16.ª conferencia internacional sobre la World Wide Web , págs. 271-280, doi :10.1145/1242572.1242610, ISBN 9781595936547, Número de identificación del sujeto  207163129.
10. Koga, Hisashi; Tetsuo Ishibashi; Toshinori Watanabe (2007), "Algoritmo de agrupamiento jerárquico aglomerativo rápido utilizando hash sensible a la localidad", Knowledge and Information Systems , 12 (1): 25–53, doi :10.1007/s10115-006-0027-5, S2CID  4613827.
11. Cochez, Michael; Mou, Hao (2015), "Twister Tries", Actas de la Conferencia Internacional ACM SIGMOD de 2015 sobre Gestión de Datos (PDF) , págs. 505–517, doi :10.1145/2723372.2751521, ISBN 9781450327589, Número de identificación del sujeto  14414777.
12. Brinza, Dumitru; et al. (2010), "Detección rápida de interacciones gen-gen en estudios de asociación de todo el genoma", Bioinformatics , 26 (22): 2856–2862, doi :10.1093/bioinformatics/btq529, PMC 3493125 , PMID  20871107 
13. dejavu - Huellas digitales y reconocimiento de audio en Python, 19 de diciembre de 2018
14. Aluç, Güneş; Özsu, M. Tamer; Daudjee, Khuzaima (2018), "Construcción de bases de datos RDF autoagrupadas utilizando Tunable-LSH", The VLDB Journal , 28 (2): 173–195, doi :10.1007/s00778-018-0530-9, S2CID  53695535
15. Chen, Beidi; Medini, Tharun; Farwell, James; Gobriel, Sameh; Tai, Charlie; Shrivastava, Anshumali (29 de febrero de 2020). "SLIDE: En defensa de los algoritmos inteligentes frente a la aceleración de hardware para sistemas de aprendizaje profundo a gran escala". arXiv : 1903.03129 [cs.DC].
16. Chen, Beidi; Liu, Zichang; Peng, Binghui; Xu, Zhaozhuo; Li, Jonathan Lingjie; Dao, Tri; Song, Zhao; Shrivastava, Anshumali; Re, Christopher (2021), "MONGOOSE: un marco LSH aprendible para el entrenamiento eficiente de redes neuronales", Conferencia internacional sobre representación del aprendizaje
17. Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). TLSH: un hash sensible a la localidad. 4.º Taller sobre ciberdelincuencia y computación confiable . págs. 7–13. doi :10.1109/CTC.2013.9. ISBN 978-1-4799-3076-0.
18. Fanaee-T, Hadi (2024), Aprendizaje natural , arXiv : 2404.05903
19. Broder, AZ ; Charikar, M. ; Frieze, AM ; Mitzenmacher, M. (1998). "Min-wise independent permutations". Actas del Trigésimo Simposio Anual de la ACM sobre Teoría de la Computación . págs. 327–336. CiteSeerX 10.1.1.409.9220 . doi :10.1145/276698.276781 . Consultado el 14 de noviembre de 2007 . 
20. Takei, Y.; Itoh, T.; Shinozaki, T. "Una construcción óptima de permutaciones independientes exactamente en orden min". Informe técnico COMP98-62, IEICE, 1998 .
21. Matoušek , J.; Stojakovic, M. (2002). "Sobre la independencia restringida de permutaciones en función de los mínimos". Preimpresión . Consultado el 14 de noviembre de 2007 .
22. Saks, M. ; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000). "Los conjuntos de baja discrepancia producen familias de permutación independientes min-wise aproximadas". Information Processing Letters . 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264 . doi :10.1016/S0020-0190(99)00163-5 . Consultado el 14 de noviembre de 2007 . 
23. Damiani; et al. (2004). "Una técnica basada en Open Digest para la detección de spam" (PDF) . Consultado el 1 de septiembre de 2013 .
24. Oliver; et al. (2013). "TLSH - Un hash sensible a la localidad". 4.º Taller sobre ciberdelincuencia y computación confiable . Consultado el 4 de junio de 2015 .
25. "TLSH". GitHub . Consultado el 10 de abril de 2014 .
26. Alexandr Andoni; Indyk, P. (2008). "Algoritmos de hash casi óptimos para el vecino más próximo aproximado en dimensiones altas". Comunicaciones de la ACM . 51 (1): 117–122. CiteSeerX 10.1.1.226.6905 . doi :10.1145/1327452.1327494. S2CID  6468963. 
27. Goemans, Michel X.; Williamson, David P. (1995). "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida". Revista de la ACM . 42 (6). Association for Computing Machinery (ACM): 1115–1145. doi : 10.1145/227683.227684 . ISSN  0004-5411. S2CID  15794408.
28. Datar, M.; Immorlica, N.; Indyk , P.; Mirrokni, VS (2004). "Esquema de hash sensible a la localidad basado en distribuciones p-estables". Actas del Simposio sobre geometría computacional .
29. Pauleve, L.; Jegou, H.; Amsaleg, L. (2010). "Hash sensible a la localidad: una comparación de tipos de funciones hash y mecanismos de consulta". Pattern Recognition Letters . 31 (11): 1348–1358. Código Bibliográfico :2010PaReL..31.1348P. doi :10.1016/j.patrec.2010.04.004. S2CID  2666044.
30. Salakhutdinov, Ruslan; Hinton, Geoffrey (2008). "Hash semántico". Revista internacional de razonamiento aproximado . 50 (7): 969–978. doi : 10.1016/j.ijar.2008.11.006 .
31. Dahlgaard, Søren, Mathias Bæk Tejs Knudsen y Mikkel Thorup. "Dibujo rápido de similitudes". 58º Simposio Anual del IEEE 2017 sobre Fundamentos de la Informática (FOCS). IEEE, 2017.
32. Christiani, Tobias. "Marcos de hash rápidos sensibles a la localidad para búsquedas aproximadas de vecinos cercanos". Conferencia internacional sobre búsqueda de similitudes y aplicaciones. Springer, Cham, 2019.
33. Ahle, Thomas Dybdahl. "Sobre el problema del hash sensible a la localidad". Conferencia internacional sobre búsqueda de similitudes y aplicaciones. Springer, Cham, 2020. ${\displaystyle p_{1}^{-1}}$
34. Gorman, James y James R. Curran. "Escalando la similitud distributiva en grandes corpus". Actas de la 21.ª Conferencia Internacional sobre Lingüística Computacional y de la 44.ª reunión anual de la Asociación de Lingüística Computacional. Asociación de Lingüística Computacional, 2006.

Lectura adicional

• Samet, H. (2006) Fundamentos de estructuras de datos multidimensionales y métricas . Morgan Kaufmann. ISBN 0-12-369446-9 
• Indyk, Piotr ; Motwani, Rajeev ; Raghavan, Prabhakar; Vempala, Santosh (1997). "Hash con preservación de localidad en espacios multidimensionales". Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación . STOC '97 . págs. 618–625. CiteSeerX  10.1.1.50.4927 . doi :10.1145/258533.258656. ISBN 978-0-89791-888-6.S2CID15693787  .​
• Chin, Andrew (1994). "Funciones hash que preservan la localidad para computación paralela de propósito general" (PDF) . Algorithmica . 12 (2–3): 170–181. doi :10.1007/BF01185209. S2CID  18108051.

Enlaces externos

• Página de inicio de LSH de Alex Andoni
• LSHKIT: una biblioteca de hash sensible a la localidad de C++
• Una biblioteca de hash sensible a la localidad de Python que admite opcionalmente la persistencia a través de redis
• Caja de herramientas de búsqueda de imágenes a gran escala de Caltech: una caja de herramientas de Matlab que implementa varias funciones hash LSH, además de algoritmos de búsqueda de árboles Kd, K-medias jerárquicas y archivos invertidos.
• Slash: una biblioteca LSH de C++ que implementa LSH esférico por Terasawa, K., Tanaka, Y.
• LSHBOX: una caja de herramientas C++ de código abierto de hash sensible a la localidad para la recuperación de imágenes a gran escala. También compatible con Python y MATLAB.
• SRS: Una implementación en C++ de un algoritmo de procesamiento de consultas de vecino más cercano aproximado, eficiente en el uso del espacio y en memoria, basado en una proyección aleatoria p-estable
• TLSH de código abierto en Github
• Puerto JavaScript de TLSH (Trend Micro Locality Sensitive Hashing) incluido como módulo node.js
• Puerto Java de TLSH (Trend Micro Locality Sensitive Hashing) incluido como paquete maven