Quanta independência é necessária para o encadeamento separado?

13

Se bolas forem colocadas em bandejas uniformemente aleatoriamente, a bandeja carregada mais pesada terá bolas com alta probabilidade. Em "O poder do hash de tabulação simples" , Pătraşcu e Thorup mencionam que "Chernoff-Hoeffding limita para aplicativos com independência limitada" ( espelho ) mostra que esse limite para a população do compartimento carregado mais pesado também é válido se as bolas forem distribuídas por um Função de hash independente de .nnO(lgn/lglgn)Ω(lgn/lglgn)

Em "Bolas e caixas: famílias menores de hash e avaliação mais rápida" , Celis et al. note que não se sabe se existe uma família de funções hash em que

  1. As funções de hash podem ser representadas com bits de espaçoO(lgn)
  2. As funções hash pode ser avaliada em horaO(1)
  3. A carga máxima é com alta probabilidade.O(lgn/lglgn)

Se existe uma constante tal que qualquer família independente de é suficiente para # 3, então a construção polinomial de famílias independentes de atenderia aos números 1 e 2.kkk

O que Vinculadas que temos para o mais pesado bin carregado com hashing independente de?k

Usando o Teorema 4.III de "limites de Chernoff-Hoeffding ..." e o limite de união, acho que posso obter um limite de no peso do compartimento mais pesado whpO(n2/k)

Isso pode ser reduzido a usando outras técnicas?O(lgcn)

jbapple
fonte

Respostas: