hash independiente de k

Familia de funciones Hash

En informática , se dice que una familia de funciones hash es k -independiente , k -independiente o k -universal ^[1] si la selección de una función al azar de la familia garantiza que los códigos hash de cualquier k clave designada sean aleatorios independientes. variables (consulte las definiciones matemáticas precisas a continuación). Estas familias permiten un buen rendimiento promedio de casos en algoritmos o estructuras de datos aleatorios, incluso si los datos de entrada son elegidos por un adversario. Las compensaciones entre el grado de independencia y la eficiencia de la evaluación de la función hash están bien estudiadas y se han propuesto muchas k familias independientes.

Fondo

El objetivo del hash suele ser asignar claves de algún dominio grande (universo) a un rango más pequeño, como contenedores (etiquetados ). En el análisis de estructuras de datos y algoritmos aleatorios, a menudo es deseable que los códigos hash de varias claves "se comporten de forma aleatoria". Por ejemplo, si el código hash de cada clave fuera una elección aleatoria independiente en , el número de claves por contenedor podría analizarse utilizando el límite de Chernoff . Una función hash determinista no puede ofrecer tal garantía en un entorno adversario, ya que el adversario puede elegir las claves para que sean precisamente la preimagen de un contenedor. Además, una función hash determinista no permite repetir : a veces los datos de entrada resultan ser malos para la función hash (por ejemplo, hay demasiadas colisiones), por lo que uno quisiera cambiar la función hash. ${\displaystyle U}$ ${\displaystyle m}$ ${\displaystyle [m]=\{0,\dots ,m-1\}}$ ${\displaystyle [m]}$

La solución a estos problemas es elegir una función al azar de una gran familia de funciones hash. La aleatoriedad en la elección de la función hash se puede utilizar para garantizar algún comportamiento aleatorio deseado de los códigos hash de cualquier clave de interés. La primera definición en este sentido fue el hash universal , que garantiza una baja probabilidad de colisión para dos claves designadas. El concepto de hash independiente, introducido por Wegman y Carter en 1981, ^[2] refuerza las garantías de comportamiento aleatorio para familias de claves designadas y añade una garantía sobre la distribución uniforme de códigos hash. ${\displaystyle k}$ ${\displaystyle k}$

Definiciones

La definición más estricta, introducida por Wegman y Carter ^[2] bajo el nombre de " familia de hash fuertemente universal", es la siguiente. Una familia de funciones hash es independiente si para claves distintas y códigos hash (no necesariamente distintos) , tenemos: ${\displaystyle _{k}}$ ${\displaystyle H=\{h:U\to [m]\}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (x_{1},\dots ,x_{k})\in U^{k}}$ ${\displaystyle k}$ ${\displaystyle (y_{1},\dots ,y_{k})\in [m]^{k}}$

${\displaystyle \Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}}$

Esta definición equivale a las dos condiciones siguientes:

1. para cualquier fijo , como se extrae aleatoriamente de , se distribuye uniformemente en . ${\displaystyle x\in U}$ ${\displaystyle h}$ ${\displaystyle H}$ ${\displaystyle h(x)}$ ${\displaystyle [m]}$
2. para cualquier clave fija y distinta , tal como se extrae aleatoriamente de , son variables aleatorias independientes. ${\displaystyle x_{1},\dots ,x_{k}\in U}$ ${\displaystyle h}$ ${\displaystyle H}$ ${\displaystyle h(x_{1}),\dots ,h(x_{k})}$

A menudo es inconveniente lograr la probabilidad conjunta perfecta debido a problemas de redondeo. A continuación, ^[3] se puede definir una familia independiente para satisfacer: ${\displaystyle m^{-k}}$ ${\displaystyle (\mu ,k)}$

${\displaystyle \forall }$distinto y , ${\displaystyle (x_{1},\dots ,x_{k})\in U^{k}}$ ${\displaystyle \forall (y_{1},\dots ,y_{k})\in [m]^{k}}$ ${\displaystyle ~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}}$

Observe que, incluso si está cerca de 1, ya no son variables aleatorias independientes, lo que suele ser un problema en el análisis de algoritmos aleatorios. Por lo tanto, una alternativa más común para tratar problemas de redondeo es demostrar que la familia hash está cercana en distancia estadística a una familia independiente, lo que permite el uso de caja negra de las propiedades de independencia. ${\displaystyle \mu }$ ${\displaystyle h(x_{i})}$ ${\displaystyle k}$

Técnicas

Polinomios con coeficientes aleatorios

La técnica original para construir k funciones hash independientes, dada por Carter y Wegman, era seleccionar un número primo grande p , elegir k números aleatorios módulo p y usar estos números como coeficientes de un polinomio de grado k − 1 cuyos valores El módulo p se utiliza como valor de la función hash. Todos los polinomios del grado dado módulo p son igualmente probables, y cualquier polinomio está determinado únicamente por cualquier k -tupla de pares argumento-valor con argumentos distintos, de lo que se deduce que cualquier k -tupla de distintos argumentos tiene la misma probabilidad de ser mapeada a cualquier k -tupla de valores hash. ^[2]

En general el polinomio se puede evaluar en cualquier cuerpo finito . Además de los campos módulo primo, una opción popular es el campo de tamaño , que admite aritmética rápida de campos finitos en las computadoras modernas. Este fue el enfoque adoptado por Daniel Lemire y Owen Kaser para CLHash. ^[4] ${\displaystyle 2^{n}}$

Hash de tabulación

El hash de tabulación es una técnica para asignar claves a valores hash dividiendo cada clave en bytes , utilizando cada byte como índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte) y combinando los resultados de estas búsquedas en la tabla por una operación u exclusiva bit a bit . Por lo tanto, requiere más aleatoriedad en su inicialización que el método polinómico, pero evita operaciones de multiplicación posiblemente lentas. Es independiente de 3 pero no de 4. ^[5] Las variaciones del hash de tabulación pueden lograr mayores grados de independencia realizando búsquedas en tablas basadas en combinaciones superpuestas de bits de la clave de entrada, o aplicando hash de tabulación simple de forma iterativa. ^{[6] [7]}

Independencia necesaria para los diferentes tipos de resolución de colisiones

La noción de k -independencia se puede utilizar para diferenciar entre diferentes resoluciones de colisión en tablas hash, según el nivel de independencia requerido para garantizar un tiempo esperado constante por operación.

Por ejemplo, el encadenamiento hash requiere un tiempo esperado constante incluso con una familia de funciones hash de 2 independientes , porque el tiempo esperado para realizar una búsqueda de una clave determinada está limitado por el número esperado de colisiones en las que está involucrada esa clave. Por linealidad de expectativa , este número esperado es igual a la suma, sobre todas las demás claves de la tabla hash, de la probabilidad de que la clave dada y la otra clave choquen. Debido a que los términos de esta suma solo involucran eventos probabilísticos que involucran dos claves, la independencia 2 es suficiente para garantizar que esta suma tenga el mismo valor que tendría para una función hash verdaderamente aleatoria. ^[2]

El doble hash es otro método de hash que requiere un bajo grado de independencia. Es una forma de direccionamiento abierto que utiliza dos funciones hash: una para determinar el inicio de una secuencia de sonda y la otra para determinar el tamaño del paso entre posiciones en la secuencia de sonda. Siempre que ambos sean independientes, este método proporciona un tiempo esperado constante por operación. ^[8]

Por otro lado, se puede garantizar que el sondeo lineal , una forma más simple de direccionamiento abierto donde el tamaño del paso es siempre uno, funcione en un tiempo esperado constante por operación con una función hash de 5 independientes, ^[9] y existe un hash de 4 independientes. funciones para las que se necesita un tiempo logarítmico por operación. ^[10]

Para el hashing de Cuckoo, la k-independencia requerida no se conoce en 2021. En 2009 se demostró ^[11] que -la independencia es suficiente y se necesita al menos 6-independencia . Otro enfoque es utilizar el hash de tabulación , que no es independiente de 6, pero en 2012 ^[12] se demostró que tiene otras propiedades suficientes para el hashing Cuckoo. Un tercer enfoque de 2014 ^[13] es modificar ligeramente la tabla hash del cuco con un llamado alijo, que permite utilizar nada más que 2 funciones hash independientes. ${\displaystyle O(\log n)}$

Otras aplicaciones

Kane , Nelson y David Woodruff mejoraron el algoritmo Flajolet-Martin para el problema de elementos distintos en 2010. ^[14] Para dar una aproximación a la respuesta correcta, necesitan una función hash independiente . ${\displaystyle \varepsilon }$ ${\displaystyle {\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}}$

El algoritmo Count sketch para la reducción de dimensionalidad requiere dos funciones hash, una 2 independiente y otra 4 independiente .

El algoritmo Karloff-Zwick para el problema MAX-3SAT se puede implementar con 3 variables aleatorias independientes.

El algoritmo MinHash se puede implementar utilizando una función hash independiente, como lo demostró Piotr Indyk en 1999 ^[15]. ${\displaystyle \log {\tfrac {1}{\epsilon }}}$

Referencias

1. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
2. Wegman, Mark N .; Carter, J. Lawrence (1981). "Nuevas funciones hash y su uso en autenticación e igualdad de conjuntos" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 22 (3): 265–279. doi : 10.1016/0022-0000(81)90033-7 . Versión conferencia en FOCS'79 . Consultado el 9 de febrero de 2011 .
3. Siegel, Alan (2004). "Sobre clases universales de funciones hash de tiempo constante extremadamente aleatorias y su compensación tiempo-espacio" (PDF) . Revista SIAM de Computación . 33 (3): 505–543. doi :10.1137/S0097539701386216. Versión conferencia en FOCS'89.
4. Lemire, Daniel y Owen Kaser. "Hashing universal de 64 bits más rápido mediante multiplicaciones sin acarreo". Revista de Ingeniería Criptográfica 6.3 (2016): 171-185.
5. Pătraşcu, Mihai ; Thorup, Mikkel (2012), "El poder del hashing de tabulación simple", Journal of the ACM , 59 (3): art. 14, arXiv : 1011.5200 , doi : 10.1145/2220357.2220361, SEÑOR  2946218
6. Siegel, Alan (2004), "Sobre clases universales de funciones hash de tiempo constante extremadamente aleatorias" (PDF) , SIAM Journal on Computing , 33 (3): 505–543, doi :10.1137/S0097539701386216, MR  2066640, S2CID  1742179 , archivado desde el original (PDF) el 2019-02-17
7. Thorup, M. (2013), "Tablación simple, expansores rápidos, tabulación doble y alta independencia", Actas del 54º Simposio anual del IEEE sobre los fundamentos de la informática (FOCS 2013) , págs. 90–99, arXiv : 1311.3121 , doi :10.1109/FOCS.2013.18, ISBN 978-0-7695-5135-7, SEÑOR  3246210
8. Bradford, Phillip G.; Katehakis, Michael N. (2007), "Un estudio probabilístico sobre expansores combinatorios y hash" (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi :10.1137/S009753970444630X, MR  2306284, archivado desde el original (PDF) el 25 de enero de 2016 , consultado el 19 de enero de 2016
9. Pagh, Anna; Pagh, Rasmus ; Ružić, Milán (2009), "Sondeo lineal con independencia constante", SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs/0612055 , doi :10.1137/070702278, MR  2538852
10. Pătraşcu, Mihai ; Thorup, Mikkel (2010), "Sobre la independencia k requerida por el sondeo lineal y la independencia minwise" (PDF) , Autómatas, lenguajes y programación, 37º Coloquio Internacional, ICALP 2010, Burdeos, Francia, 6 al 10 de julio de 2010, Actas , Parte I , Apuntes de conferencias sobre informática , vol. 6198, Springer, págs. 715–726, arXiv : 1302.5127 , doi : 10.1007/978-3-642-14165-2_60, ISBN 978-3-642-14164-5
11. Cohen, Jeffrey S. y Daniel M. Kane. "Límites de la independencia necesaria para el hash cuco". Transacciones ACM sobre algoritmos (2009).
12. Pǎtraşcu, Mihai y Mikkel Thorup. "El poder del hash de tabulación simple". Revista de la ACM (JACM) 59.3 (2012): 1-50.
13. Aumüller, Martin, Martin Dietzfelbinger y Philipp Woelfel. "Para hacer hash cuco con un alijo, basta con familias de hash explícitas y eficientes". Algorítmica 70.3 (2014): 428-456.
14. Kane, Daniel M., Jelani Nelson y David P. Woodruff. "Un algoritmo óptimo para el problema de los distintos elementos". Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos. 2010.
15. Indyk, Piotr. "Una pequeña familia independiente de funciones hash aproximadamente mínimas". Revista de Algoritmos 38.1 (2001): 84-90.

Otras lecturas

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge. pag. 221.ISBN​ 978-0-521-47465-8.