Достаточно ли независимы перекрывающиеся подмассивы массива байтов, чтобы их можно было использовать в качестве хеш-функций для фильтра Блума?

У меня следующий вопрос в контексте BloomFilter. BloomFilters должны иметь k независимых хеш-функций. Назовем эту функцию h1, h2, ... hk. Независимость в этом контексте означает, что их значение будет иметь очень небольшую корреляцию (надеюсь, нулевую) при применении к одному и тому же набору. См. описание алгоритма на странице http://en.wikipedia.org/wiki/Bloom_filter (но не конечно, вы уже знаете эту страницу наизнанку :).

Теперь предположим, что я хочу определить свои хэш-функции, используя некоторые n бита (исходя из криптографической функции, если вам нужно знать, но это не имеет отношения к вопросу), которые сами по себе независимы друг от друга. Если вам нужен дополнительный контекст, вы можете прочитать http://bitworking.org/news/380/bloom-filter-resources, который делает что-то подобное.

Например, предположим, что я хочу определить каждый h как (извините за мой псевдокод):

bytes = MD5(value)
h1 = bytes[0-3] as Integer
h2 = bytes[4-7] as Integer
h3 = bytes[8-11] as Integer
...

Конечно, у нас очень быстро закончатся хеш-функции. В этом примере MD5 мы получаем только четыре.

Одна из возможностей состоит в том, чтобы позволить хеш-функциям перекрываться друг с другом и не требовать, чтобы четыре байта были последовательными. Таким образом, у нас есть много хеш-функций, поскольку массив байтов допускает перестановки. Для простоты, что, если мы определим хэш-функции следующим образом:

bytes = MD5(value)
h1 = bytes[0-3] as Integer
h2 = bytes[1-4] as Integer
h3 = bytes[2-5] as Integer
...

Легко заметить, что в случае MD5 теперь у нас 12 функций хэширования вместо четырех.

Наконец, мы подошли к вопросу THE. Являются ли эти хеш-функции независимыми? Спасибо!

ОБНОВЛЕНИЕ: я решил попытаться ответить на вопрос с практической точки зрения, поэтому я создал небольшую программу, которая будет проверять гипотезу. Смотри ниже.


correlation statistics bloom-filter
person Andres Rodriguez    schedule 11.07.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Как это часто бывает с умными вопросами, ответ и да, и нет.

Да, в том смысле, что есть 16 бит, которые не используются совместно между h1 и h2. Нет, в тех смыслах, которые важны для вас (если вы на самом деле не используете только восемь битов хеш-функции, что, я полагаю, не так).

Проблема здесь меньше связана с зависимостью между двумя функциями, применяемыми к одному и тому же вставляемому элементу, и больше (в данном случае, на мой взгляд) с функциями, применяемыми к нескольким элементам.

Подумайте об этом так. Предположим, в первом примере используется g1-g4, а во втором — h1-h4. Два элемента, чья MD5sum (или любая другая хеш-функция) перекрывается только в 5 последовательных байтах (маловероятно, но статистически выполнимо, особенно если вы пытаетесь), будут иметь шанс столкнуться, если просто использовать h1 и h2, h2 и h3, или h3 и h4. Между тем g1-g4 устойчива к этой возможности.

Теперь коллизии с фильтрами Блума не так серьезны, как другие применения хеш-функций, но вы должны иметь в виду, что перекрывающиеся байты умаляют полезность хеш-функций. Честно говоря, я немного удивлен, что вам нужно больше четырех независимых хеш-функций.

Кроме того, если вы используете только последние 8 бит каждого числа (фильтр Блума 256 бит) или последние 16 бит (фильтр Блума 2 ^ 16 бит) или что-то еще, тогда вы можете «перекрывать» биты, которые у вас есть. t использовать с опрометчивой самоотверженностью и без риска.

Отказ от ответственности: я довольно хорошо знаю криптографию и фильтры Блума, потому что они чертовски круты, но мои практические знания о фильтрах Блума ограничены; то, что вы описываете, может хорошо работать для вашего варианта использования.

person Slartibartfast    schedule 13.07.2011
comment
Спасибо за Ваш ответ. Я думаю, что понимаю компромиссы, которые вы описываете. Однако я не уверен, что понимаю вашу точку зрения о хеш-коллизиях. В примере, который я привел, байты поступали из MD5, но с тем же успехом они могли поступать и из Random.nextBytes. В этом случае возникает вопрос: когда мы генерируем массивы байтов последовательности b1, b2, b3 ... и интерпретируем подцепь как целое число (например, b2[3-7]), будут ли две подцепи иметь высокий или низкий коэффициент корреляции? - person Andres Rodriguez; 14.07.2011

arrow_upward
0
arrow_downward

Запуск приведенной ниже программы проверит гипотезу с помощью генераторов случайных чисел.

public static void main(String[] args) {
    int R = 100, N = 10000, W = 8;
    double[] totals = new double[33];
    Random r = new Random();

    for (int k = 0; k < R; k++) {
        // Generate 10,000 random byte arrays
        byte[][] bytes = new byte[N][W];
        for (int i = 0; i < N; i++) r.nextBytes(bytes[i]);

        double[] a1 = new double[N], a2 = new double[N];
        for (int i = 0; i <= 32; i++) {

            // Extract arrays
            for (int j = 0; j < N; j++) {
                a1[j] = readInt(bytes[j], 0, 31);
                a2[j] = readInt(bytes[j], 32 - i, 31);
            }

            double c = (new PearsonsCorrelation()).correlation(a1, a2);
            totals[i] += c;
        }
    }
}

Интересные биты в том, что только когда есть только один перекрывающийся бит, корреляция становится значимой. Ниже приведены коэффициенты корреляции Пирсона для каждого количества перекрывающихся битов. Мы начинаем очень низко (то есть близко к случаю перекрытия 0) и получаем 1, когда они полностью перекрываются.

0   -0.001883705757299319
1   -0.0019261826793995395
2   -0.0018466135577488883
3   -0.001499114477250019
4   -0.0010874727770462341
5   -1.1219111699336884E-5
6   -0.001760700583842139
7   3.6545455908216937E-4
8   0.0014823972050436482
9   0.0014809963180788554
10  0.0015226692114697182
11  0.00199027499920776
12  0.001720451344380218
13  -2.0219121772336676E-4
14  6.880004078769847E-4
15  8.605949344202965E-4
16  -0.0025640320027890645
17  -0.002552269654230886
18  -0.002550425130285998
19  -0.002522446787072504
20  -0.00320337678141518
21  -7.554573868921899E-4
22  -6.463448718890875E-4
23  -3.4709181348336335E-4
24  0.0038077518094915912
25  0.0037865326140343815
26  0.0038728464390708982
27  0.0035091958914765407
28  0.005099109955591643
29  0.016993434043779915
30  0.06120260114179265
31  0.25159073855202346
32  1.0

Итог: кажется, что сдвиг на один байт (имеется в виду значение 24 выше) должен быть вполне безопасным с точки зрения генерации хеш-функции.

person Andres Rodriguez    schedule 19.07.2011