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]
Si se cumple la siguiente condición: Para dos puntos cualesquiera y una función hash elegida de manera uniforme al azar entre :
Si , entonces (es decir, a y b chocan) con una probabilidad de al menos ,
Si , entonces con probabilidad como máximo .
A una familia así se le llama -sensible.
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 .
Amplificación
Dada una familia sensible , podemos construir nuevas familias mediante la construcción AND o la construcción OR de . [1]
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 .
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 .
Aplicaciones
LSH se ha aplicado a varios dominios problemáticos, entre ellos:
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 .
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.
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.
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-sabia tiene al menos un tamaño , [19] y que este límite es estricto. [20]
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:
El resumen que identifica cada mensaje no debe variar significativamente por los cambios que se pueden producir automáticamente.
La codificación debe ser robusta contra ataques intencionales.
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.
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 .
Para dos vectores u,v con ángulo entre ellos, se puede demostrar que
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.
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 .
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.
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 diferente elegida aleatoriamente g .
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 .
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 ;
espacio: , más el espacio para almacenar puntos de datos;
tiempo de consulta: ;
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 ;
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:
tiempo de preprocesamiento :;
espacio: , más el espacio para almacenar puntos de datos;
tiempo de consulta: ;
Mejoras
Cuando t es grande, es posible reducir el tiempo de hash de . Esto se demostró en [31] y [32], que dieron
tiempo de consulta: ;
espacio: ;
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.
Véase también
Filtro Bloom : estructura de datos para la pertenencia aproximada a un conjunto
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
^ abcd Rajaraman, A.; Ullman, J. (2010). "Extracción de conjuntos de datos masivos, cap. 3".
^ Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). Hashing con preservación de localidad. Conferencia AAAI sobre inteligencia artificial. Vol. 28. págs. 2874–2880.
^ Tsai, Yi-Hsuan; Yang, Ming-Hsuan (octubre de 2014). "Hashing que preserva la localidad". Conferencia internacional IEEE 2014 sobre procesamiento de imágenes (ICIP) . págs. 2988–2992. doi :10.1109/ICIP.2014.7025604. ISBN978-1-4799-5751-4. ISSN 1522-4880. S2CID 8024458.
^ ab Chin, Andrew (1991). Problemas de complejidad en computación paralela de propósito general (DPhil). Universidad de Oxford. págs. 87–95.
^ ab 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.
^ 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) .
^ abcd 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.
^ 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, ISBN9781595936547, Número de identificación del sujeto 207163129.
^ 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.
^ 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, ISBN9781450327589, Número de identificación del sujeto 14414777.
^ 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
^ dejavu - Huellas digitales y reconocimiento de audio en Python, 19 de diciembre de 2018
^ 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
^ 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].
^ Chen, Beidi; Liu, Zichang; Peng, Binghui; Xu, Zhaozhuo; Li, Jonathan Lingjie; Dao, Tri; Canción, Zhao; Shrivastava, Anshumali; Re, Christopher (2021), "MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training", Conferencia internacional sobre representación del aprendizaje
^ ab 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. ISBN978-1-4799-3076-0.
^ Fanaee-T, Hadi (2024), Aprendizaje natural , arXiv : 2404.05903
^ 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 .
^ Takei, Y.; Itoh, T.; Shinozaki, T. "Una construcción óptima de permutaciones independientes exactamente en orden min". Informe técnico COMP98-62, IEICE, 1998 .
^ 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 .
^ 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 .
^ 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 .
^ 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 .
^ "TLSH". GitHub . Consultado el 10 de abril de 2014 .
^ 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.
^ 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.
^ 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 .
^ 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.
^ 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 .
^ 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.
^ 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.
^ Ahle, Thomas Dybdahl. "Sobre el problema del hash sensible a la localidad". Conferencia internacional sobre búsqueda de similitudes y aplicaciones. Springer, Cham, 2020.
^ 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.S2CID 15693787 .
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 y eficiente en el uso del espacio, 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