Сколько независимости требуется для отдельного сцепления?

13

Если шаров равномерно размещены в n корзинах случайным образом, то в самой тяжелой загруженной корзине с высокой вероятностью будет O ( lg n / lg lg n ) шариков. В «Сложности простого хэширования табуляции» Патрашку и Торуп упоминают, что «границы Черноффа-Хёффдинга для приложений с ограниченной независимостью» ( зеркало ) показывают, что эта граница для совокупности наиболее загруженного бина сохраняется и в том случае, если шары распределены Ω ( lg n / lg lg n ) -независимая хеш-функция.NNО(Л.Г.N/Л.Г.Л.Г.N)Ω(Л.Г.N/Л.Г.Л.Г.N)

В «Шариках и корзинах: меньшие хэш-семейства и более быстрая оценка» , Celis et al. обратите внимание, что неизвестно, существует ли семейство хеш-функций, где

  1. Хеш-функции могут быть представлены битами пространстваО(Л.Г.N)
  2. Хеш-функции могут быть оценены за разО(1)
  3. Нагрузка максимальна является с высокой вероятностью.О(Л.Г.N/Л.Г.Л.Г.N)

Если существует константа такая, что для # 3 достаточно любого k- независимого семейства, тогда полиномиальная конструкция k -независимых семейств будет соответствовать # 1 и # 2.ККК

К

О(N2/К)

О(Л.Г.сN)

jbapple
источник

Ответы: