Hashing 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 seleccionar una función al azar de la familia garantiza que los códigos hash de cualquier clave k designada sean variables aleatorias independientes (ver definiciones matemáticas precisas a continuación). Estas familias permiten un buen rendimiento de caso promedio en algoritmos aleatorios o estructuras de datos, 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 familias k -independientes.

Fondo

El objetivo del hash es generalmente mapear claves de un dominio grande (universo) en un rango más pequeño, como contenedores (etiquetados como ). En el análisis de algoritmos aleatorios y estructuras de datos, a menudo es deseable que los códigos hash de varias claves se "comportes aleatoriamente". Por ejemplo, si el código hash de cada clave fuera una elección aleatoria independiente en , la cantidad 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 que las claves sean precisamente la preimagen de un contenedor. Además, una función hash determinista no permite el rehashing : a veces los datos de entrada resultan ser malos para la función hash (por ejemplo, hay demasiadas colisiones), por lo que uno querría 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 aleatoriamente de una gran familia de funciones hash. La aleatoriedad en la elección de la función hash se puede utilizar para garantizar un comportamiento aleatorio deseado de los códigos hash de cualquier clave de interés. La primera definición en esta línea fue el hash universal , que garantiza una baja probabilidad de colisión para dos claves designadas cualesquiera. El concepto de hash independiente, introducido por Wegman y Carter en 1981, ^[2] fortalece las garantías de comportamiento aleatorio para familias de claves designadas y agrega una garantía sobre la distribución uniforme de los 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 hash fuertemente universal ", es la siguiente: una familia de funciones hash es independiente si para cualquier clave distinta y cualquier código hash (no necesariamente distinto) , 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 es equivalente a las dos condiciones siguientes:

1. para cualquier fijo , tal 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 resulta 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}}$

Obsérvese 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 los problemas de redondeo es demostrar que la familia hash está cerca 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 funciones hash k -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 los coeficientes de un polinomio de grado k − 1 cuyos valores módulo p se usan como el valor de la función hash. Todos los polinomios del grado dado módulo p son igualmente probables, y cualquier polinomio está determinado de forma única por cualquier k -tupla de pares argumento-valor con argumentos distintos, de lo que se deduce que cualquier k -tupla de argumentos distintos tiene la misma probabilidad de ser mapeada a cualquier k -tupla de valores hash. ^[2]

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

Hashing de tabulación

El hash de tabulación es una técnica para mapear claves a valores hash al dividir cada clave en bytes , usar cada byte como índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte) y combinar los resultados de estas búsquedas de tabla mediante una operación exclusiva o bit a bit . Por lo tanto, requiere más aleatoriedad en su inicialización que el método polinomial, 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 al realizar búsquedas de tabla basadas en combinaciones superpuestas de bits de la clave de entrada, o al aplicar el hash de tabulación simple de manera iterativa. ^{[6] [7]}

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

El hash doble 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 sondeo y la otra para determinar el tamaño del paso entre las posiciones en la secuencia de sondeo. Mientras ambas sean independientes entre sí, este método proporciona un tiempo esperado constante por operación. ^[8]

Por otra parte, 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 existen funciones hash de 4 independientes para las que se necesita un tiempo logarítmico por operación. ^[10]

Para el hash Cuckoo, la k-independencia requerida no se conoce a partir de 2021. En 2009 se demostró ^[11] que la k-independencia es suficiente y se necesita al menos 6-independencia . Otro enfoque es utilizar el hash Tabulation , que no es 6-independiente, pero se demostró en 2012 ^[12] que tiene otras propiedades suficientes para el hash Cuckoo. Un tercer enfoque de 2014 ^[13] es modificar ligeramente la tabla hash cuckoo con un llamado stash, que hace posible usar 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 de boceto Count para la reducción de dimensionalidad requiere dos funciones hash, una 2-independiente y otra 4-independiente .

El algoritmo de 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) . Journal of Computer and System Sciences . 22 (3): 265–279. doi : 10.1016/0022-0000(81)90033-7 . Versión de 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 equilibrio espacio-temporal" (PDF) . SIAM Journal on Computing . 33 (3): 505–543. doi :10.1137/S0097539701386216. Versión de conferencia en FOCS'89.
4. Lemire, Daniel y Owen Kaser. "Hash universal de 64 bits más rápido usando multiplicaciones sin acarreo". Journal of Cryptographic Engineering 6.3 (2016): 171-185.
5. Pătraşcu, Mihai ; Thorup, Mikkel (2012), "El poder del hash de tabulación simple", Journal of the ACM , 59 (3): Art. 14, arXiv : 1011.5200 , doi :10.1145/2220357.2220361, MR  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), "Tabulación simple, expansores rápidos, doble tabulación y alta independencia", Actas del 54.º Simposio anual IEEE sobre 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, Sr.  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ć, Milan (2009), "Sondaje 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) , Automata, Languages ​​and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, Francia, 6-10 de julio de 2010, Proceedings, Part I , Lecture Notes in Computer Science , vol. 6198, Springer, pp. 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 requerida para el hash cuckoo". ACM Transactions on Algorithms (2009).
12. Pǎtraşcu, Mihai y Mikkel Thorup. "El poder del hash de tabulación simple". Journal of the ACM (JACM) 59.3 (2012): 1-50.
13. Aumüller, Martin, Martin Dietzfelbinger y Philipp Woelfel. "Las familias de hash explícitas y eficientes son suficientes para el hash cuckoo con un stash". Algorithmica 70.3 (2014): 428-456.
14. Kane, Daniel M., Jelani Nelson y David P. Woodruff. "Un algoritmo óptimo para el problema de los elementos distintos". Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos. 2010.
15. Indyk, Piotr. "Una pequeña familia de funciones hash independientes, aproximadamente en orden min." Journal of Algorithms 38.1 (2001): 84-90.

Lectura adicional

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Cambridge University Press. pág. 221. ISBN 978-0-521-47465-8.