¿Cuánta independencia se requiere para encadenar por separado?

13

Si se colocan bolas en n contenedores de manera uniforme al azar, el contenedor cargado más pesado tiene O ( lg n / lg lg n ) bolas con alta probabilidad. En "The Power of Simple Tabulation Hashing" , Pătraşcu y Thorup mencionan que "los límites de Chernoff-Hoeffding para aplicaciones con independencia limitada" ( espejo ) muestran que esto limitado a la población del contenedor cargado más pesado también se cumple si las bolas son distribuidas por un Función hash independiente de Ω ( lg n / lg lg n ) .nnO(lgn/lglgn)Ω(lgn/lglgn)

En "Balls and Bins: Smaller Hash Families and Faster Evaluation" , Celis et al. tenga en cuenta que no se sabe si hay una familia de funciones hash donde

  1. Las funciones hash se pueden representar con bits de espacioO(lgn)
  2. Las funciones hash se pueden evaluar en tiempoO(1)
  3. La carga máxima es con alta probabilidad.O(lgn/lglgn)

Si hay una constante tal que cualquier familia independiente de k es suficiente para # 3, entonces la construcción polinómica de las familias independientes de k cumpliría con # 1 y # 2.kkk

k

O(n2/k)

O(lgcn)

jbapple
fuente

Respuestas: