En ciencias de la computación, el hash sensible a la localidad ( LSH ) es una técnica algorítmica que clasifica elementos de entrada similares en los mismos "cubos" con alta probabilidad. [1] (El número de depósitos es mucho menor que el universo de posibles elementos de entrada). [1] Dado que elementos similares terminan en los mismos depósitos, 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 dimensionalidadde datos de alta dimensión; Los elementos de entrada de alta dimensión se pueden reducir a versiones de dimensiones reducidas y, al mismo tiempo, se mantienen las distancias relativas entre los elementos.
Los algoritmos de búsqueda de vecinos más cercanos aproximados basados en hash generalmente utilizan una de las dos categorías principales de métodos de hash: métodos independientes de datos, como el hash sensible a la localidad (LSH); o métodos dependientes de datos, como el hash que preserva la localidad (LPH). [2] [3]
Definiciones
Una familia LSH [1] [4] [5]está definido para un espacio métrico , un umbral y un factor de aproximación . Esta familia es una familia de funciones qué mapean elementos del espacio métrico a los depósitos . La familia LSH satisface las siguientes condiciones para dos puntos cualesquiera, usando una función que se elige uniformemente al azar:
- Si , luego (es decir, p y q chocan) con una probabilidad de al menos,
- Si , luego con probabilidad como máximo .
Una familia es interesante cuando . Tal familia se llama -sensible .
Alternativamente [6] se define con respecto a un universo de elementos U que tienen una función de similitud. Un esquema LSH es una familia de funciones hash H junto con una distribución de probabilidad D sobre las funciones tal que una funciónelegido de acuerdo con D satisface la propiedad de que para cualquier .
Hash para preservar la localidad
Un hash que preserva la localidad es una función hash f que mapea un punto o puntos en un espacio de coordenadas multidimensional a un valor escalar, de modo que si tenemos tres puntos A , B y C tales que
En otras palabras, se trata de funciones hash en las que la distancia relativa entre los valores de entrada se conserva en la distancia relativa entre los valores hash de salida; los valores de entrada más cercanos entre sí producirán valores hash de salida más cercanos entre sí.
Esto contrasta con las funciones hash criptográficas y las sumas de comprobación , que están diseñadas para tener una diferencia de salida aleatoria entre entradas adyacentes .
Los valores hash que preservan la localidad están relacionados con las curvas que llenan el espacio . [ ¿cómo? ]
Amplificación
Dado un -familia sensible , podemos construir nuevas familias ya sea por la construcción Y o la construcción OR de . [1]
Para crear una construcción Y, definimos una nueva familia de funciones hash g , donde cada función g se construye a partir de k funciones aleatorias de . Luego decimos que para una función hash, si y solo si todo por . Dado que los miembros de son elegidos independientemente para cualquier , es un -familia sensible.
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 . Luego decimos que para una función hash, si y solo si para uno o más valores de i . Dado que los miembros de son elegidos independientemente para cualquier , es un -familia sensible.
Aplicaciones
LSH se ha aplicado a varios dominios problemáticos, que incluyen:
- Detección de casi duplicados [7]
- Agrupación jerárquica [8] [9]
- Estudio de asociación del genoma completo [10]
- Identificación de similitud de imagen
- 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 digital de audio [11]
- Toma de huellas digitales de video
- Organización de datos físicos en sistemas de gestión de bases de datos [12]
- Entrenamiento de redes neuronales completamente conectadas [13] [14]
- Seguridad informática [15]
Métodos
Muestreo de bits para distancia de Hamming
Una de las formas más sencillas de construir una familia LSH es mediante muestreo de bits. [5] 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 uno de los coordenadas, es decir, , dónde es el th coordenada de . Una función aleatoria de simplemente selecciona un bit aleatorio del punto de entrada. Esta familia tiene los siguientes parámetros:, . [ aclaración necesaria ]
Permutaciones independientes mínimas
Supongamos que U está compuesta de los subconjuntos de un conjunto de tierra de artículos enumerables S y la función de similitud de interés es el Jaccard índice J . Si π es una permutación de los índices de S , para dejar . Cada posible elección de π define una única función de hash h conjuntos de entrada de mapeo a los 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 yace dentro . Como h se eligió uniformemente al azar, y definir un esquema LSH para el índice Jaccard.
Debido a que el grupo simétrico de n elementos tiene un tamaño n !, Elegir una permutación verdaderamente aleatoria del grupo simétrico completo no es factible incluso para n de tamaño moderado . Debido a este hecho, ha habido un trabajo significativo para encontrar una familia de permutaciones que sea "min-sabiamente independiente" - una familia de permutación para la cual cada elemento del dominio tiene la misma probabilidad de ser el mínimo bajo un π elegido al azar . Se ha establecido que una familia de permutaciones independientes en términos mínimos tiene al menos el tamaño, [16] y que este límite es estrecho. [17]
Debido a que las familias independientes en términos mínimos son demasiado grandes para aplicaciones prácticas, se introducen dos nociones variantes de independencia en términos mínimos: familias de permutaciones independientes restringidas en términos mínimos y familias independientes aproximadas en términos mínimos. La independencia mínima restringida es la propiedad de independencia mínima restringida a ciertos conjuntos de cardinalidad como máximo k . [18] La independencia mínima aproximada difiere de la propiedad en un ε fijo como máximo . [19]
Métodos de código abierto
Nilsimsa Hash
Nilsimsa es un algoritmo de hash sensible a la localidad que se utiliza en los esfuerzos anti-spam . [20] 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 documento sugiere que Nilsimsa satisface tres requisitos:
- El resumen que identifica cada mensaje no debe variar significativamente para los cambios que se pueden producir automáticamente.
- La codificación debe ser robusta contra ataques intencionales.
- La codificación debe admitir un riesgo extremadamente bajo de falsos positivos.
TLSH
TLSH es un algoritmo de hash sensible a la localidad diseñado para una variedad de aplicaciones forenses digitales y de seguridad. [21] El objetivo de TLSH es generar resúmenes hash para mensajes de modo que las distancias bajas entre resúmenes indiquen que es probable que sus mensajes correspondientes sean similares.
Las pruebas realizadas en el documento en una variedad de tipos de archivos identificaron que el hash de Nilsimsa tenía una tasa de falsos positivos significativamente más alta en comparación con otros esquemas de resumen de similitudes como TLSH, Ssdeep y Sdhash.
Una implementación de TLSH está disponible como software de código abierto . [22]
Proyección aleatoria
El método de proyección aleatoria de LSH debido a Moses Charikar [6] llamado SimHash (también llamado a veces arccos [23] ) está diseñado para aproximar la distancia del coseno entre vectores. La idea básica de esta técnica es elegir un hiperplano aleatorio (definido por un vector unitario normal r ) desde el principio y usar el hiperplano para hacer hash de los vectores de entrada.
Dado un vector de entrada vy un hiperplano definido por r , dejamos. Es decir,dependiendo de qué lado del hiperplano v se encuentre.
Cada posible elección de r define una única función. Sea H el conjunto de todas estas funciones y sea D la distribución uniforme una vez más. No es difícil demostrar que, para dos vectores, , dónde es el ángulo entre u y v . está estrechamente relacionado con .
En este caso, el hash produce solo un bit. Los bits de dos vectores coinciden con una probabilidad proporcional al coseno del ángulo entre ellos.
Distribuciones estables
La función hash [24] mapas de un vector dimensional den el conjunto de números enteros. Cada función hash de la familia se indexa mediante una elección aleatoria y dónde es un vector d dimensional con entradas elegidas independientemente de una distribución estable yes un número real elegido uniformemente del rango [0, r]. Por un fijo la función hash es dado por .
Se han propuesto otros métodos de construcción de funciones hash para ajustar mejor los datos. [25] En particular, las funciones hash de k-medias son mejores en la práctica que las funciones hash basadas en proyección, pero sin ninguna garantía teórica.
Algoritmo LSH 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 de vecinos más cercanos aproximados . Considere una familia LSH. El algoritmo tiene dos parámetros principales: el parámetro de anchura 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 de las cuales corresponde a una función hash g diferente elegida aleatoriamente .
En el paso de preprocesamiento, codificamos todos los n puntos 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 autilizando 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 hash en el mismo depósito que q . El proceso se detiene tan pronto como un punto dentro de la distanciaa partir de q se encuentra.
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ónen 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 de q (si existe un punto dentro de la distancia R ) con probabilidad al menos;
Para una relación de aproximación fija y probabilidades y , uno puede configurar y , dónde . Entonces se obtienen las siguientes garantías de desempeño:
- tiempo de preprocesamiento: ;
- espacio: , más el espacio para almacenar puntos de datos;
- Tiempo de consulta: ;
Ver también
- Filtro de floración
- Maldición de dimensionalidad
- Función hash
- Transformadas relacionadas con Fourier
- Geohash
- Aprendizaje subespacial multilineal
- Análisis de componentes principales
- Indexación aleatoria [26]
- Hash rodante
- Valor singular de descomposición
- Memoria distribuida escasa
- Compresión wavelet
Referencias
- ↑ a b c d Rajaraman, A .; Ullman, J. (2010). "Minería de conjuntos de datos masivos, cap. 3" .
- ^ Zhao, Kang; Lu, Hongtao; Mei, Jincheng (2014). "Locality Preserving Hashing" . págs. 2874–2880. Parámetro desconocido
|conference=
ignorado ( ayuda ) - ^ Tsai, Yi-Hsuan; Yang, Ming-Hsuan (octubre de 2014). "Localidad preservando el hash". 2014 IEEE International Conference on Image Processing (ICIP) . págs. 2988–2992. doi : 10.1109 / ICIP.2014.7025604 . ISBN 978-1-4799-5751-4. ISSN 1522-4880 . S2CID 8024458 .
- ^ Gionis, A .; Indyk, P .; Motwani, R. (1999). "Búsqueda de similitudes en altas dimensiones mediante hash" . Actas de la 25ª Conferencia de bases de datos muy grandes (VLDB) .
- ^ a b Indyk, Piotr .; Motwani, Rajeev . (1998). "Vecinos más cercanos aproximados: hacia la eliminación de la maldición de la dimensionalidad". . Actas del 30º Simposio de Teoría de la Computación .
- ^ a b Charikar, Moses S. (2002). "Técnicas de estimación de similitud a partir de algoritmos de redondeo". Actas del 34º Simposio Anual ACM sobre Teoría de la Computación . págs. 380–388. CiteSeerX 10.1.1.147.4064 . doi : 10.1145 / 509907.509965 .
- ^ 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 : 271, doi : 10.1145 / 1242572.1242610 , ISBN 9781595936547, S2CID 207163129.
- ^ Koga, Hisashi; Tetsuo Ishibashi; Toshinori Watanabe (2007), "Algoritmo de agrupación jerárquica de aglomeración rápida que utiliza hash sensible a la localidad", Sistemas de información y conocimiento , 12 (1): 25–53, doi : 10.1007 / s10115-006-0027-5 , S2CID 4613827.
- ^ Cochez, Michael; Mou, Hao (2015), "Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time", Proceeding SIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data : 505-517, doi : 10.1145 / 2723372.2751521 , ISBN 9781450327589, S2CID 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 , 2018-12-19
- ^ Aluç, Güneş; Özsu, M. Tamer; Daudjee, Khuzaima (2018), "Creación de bases de datos RDF autoagrupadas mediante Tunable-LSH", The VLDB Journal , 28 (2): 173-195, doi : 10.1007 / s00778-018-0530-9 , S2CID 53695535
- ^ Chen, Beidi; Medini, Tharun; Adiós, James; Gobriel, Sameh; Tai, Charlie; Shrivastava, Anshumali (29 de febrero de 2020). "DIAPOSITIVA: En defensa de algoritmos inteligentes sobre 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; Song, Zhao; Shrivastava, Anshumali; Re, Christopher (2021), "MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training" , Conferencia internacional sobre representación del aprendizaje
- ^ Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013), "TLSH - un hash sensible a la localidad" , 4º Taller sobre ciberdelincuencia y computación confiable , doi : 10.1109 / CTC.2013.9 , ISBN 978-1-4799-3076-0
- ^ Broder, AZ ; Charikar, M .; Frieze, AM ; Mitzenmacher, M. (1998). "Permutaciones independientes mínimas" . Actas del Trigésimo Simposio Anual 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 mínimas". Informe técnico COMP98-62, IEICE, 1998 .
- ^ Matoušek , J .; Stojakovic, M. (2002). "Sobre la independencia restringida Min-Wise de permutaciones" . 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-sabias aproximadas" . Cartas de procesamiento de información . 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" . IV Taller de Ciberdelincuencia y Computación Confiable . Consultado el 6 de abril de 2015 .
- ^ "TLSH" . Consultado el 10 de abril de 2014 .
- ^ Alexandr Andoni; Indyk, P. (2008). "Algoritmos de hash casi óptimos para el vecino más cercano aproximado en altas dimensiones". Comunicaciones de la ACM . 51 (1): 117-122. CiteSeerX 10.1.1.226.6905 . doi : 10.1145 / 1327452.1327494 . S2CID 6468963 .
- ^ 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 los tipos de función hash y los mecanismos de consulta" . Cartas de reconocimiento de patrones . 31 (11): 1348-1358. doi : 10.1016 / j.patrec.2010.04.004 .
- ^ Gorman, James y James R. Curran. "Escalar la similitud distributiva a grandes corpora". Actas de la 21ª Conferencia Internacional sobre Lingüística Computacional y la 44ª reunión anual de la Asociación de Lingüística Computacional. Asociación de Lingüística Computacional, 2006.
Otras lecturas
- Samet, H. (2006) Fundamentos de estructuras de datos métricas y multidimensionales . Morgan Kaufmann. ISBN 0-12-369446-9
- Indyk, Piotr ; Motwani, Rajeev ; Raghavan, Prabhakar; Vempala, Santosh (1997). "Hashing que preserva la localidad en espacios multidimensionales". Actas del vigésimo noveno simposio anual de ACM sobre teoría de la computación . págs. 618–625. CiteSeerX 10.1.1.50.4927 . doi : 10.1145 / 258533.258656 . ISBN 978-0-89791-888-6. S2CID 15693787 . Parámetro desconocido
|conference=
ignorado ( ayuda ) - Chin, Andrew (1994). "Funciones hash que preservan la localidad para el cálculo paralelo de propósito general" (PDF) . Algoritmica . 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 opcionalmente admite 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 de hash LSH, además de Kd-Trees, K-Means jerárquico y algoritmos de búsqueda de archivos invertidos.
- Slash: una biblioteca C ++ LSH, implementando Spherical LSH 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 es 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 espacio basado en proyección aleatoria p-estable
- Código abierto TLSH 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