¿Por qué el bosquejo de la ministra requiere funciones hash independientes por pares?

Question

los Boceto es una estructura de datos impresionante para estimar las frecuencias de diferentes elementos en un flujo de datos. Intuitivamente, funciona eligiendo una variedad de funciones hash, hashando cada elemento con esas funciones hash e incrementando las frecuencias de varias ranuras en varias tablas. Para estimar la frecuencia de un elemento, el bosquejo de minuto de cuenta aplica las funciones hash a esos elementos y elimina el valor mínimo de todas las ranuras a las que se cuestionan.

los Documento original en el boceto de la ministra cuenta menciona que la estructura de datos requiere funciones hash independientes por pares para obtener las garantías necesarias sobre su rendimiento esperado. Sin embargo, mirando la estructura, no veo por qué es necesaria la independencia por pares. Intuitivamente, creo que todo lo que se requeriría sería que la función hash sea una función de hash universal, dado que las funciones de hash universal son funciones hash con bajas probabilidades de colisiones. El análisis de las probabilidades de colisión en el boceto de la ministra cuenta se ve notablemente similar al análisis de las probabilidades de colisión en una tabla de hash encadenada (que solo requiere una familia de funciones de hash universal, no funciones hash independientes por pares), y no puedo detectar La diferencia en los análisis.

¿Por qué es necesario que las funciones hash en el bosquejo de minuto sean independientes por pares?

¡Gracias!

Answer 1

Tienes razón: el hashing universal es suficiente. La independencia por pares, aunque más fuerte, es el método habitual para construir una familia de hash universal. Además, la independencia por pares se contrasta en el documento con la independencia de 4 sabios requeridos por métodos anteriores, como el boceto AMS.