Блум сүзгісін санау - Counting Bloom filter

A Блум сүзгісін санау жалпыланған болып табылады мәліметтер құрылымы туралы Блум сүзгісі, бұл берілгеннің санау санын тексеру үшін қолданылады элемент элементтер тізбегі берілген кезде берілген шектен кіші болады. Жалпыланған түрі ретінде Блум сүзгісі, жалған оң матчтар болуы мүмкін, бірақ жалған негативтер жоқ - басқаша айтқанда, сұрау «шектен үлкен немесе тең болуы мүмкін» немесе «шекті мәннен кішірек» болып шығады.

Алгоритмді сипаттау

Параметрлердің көпшілігімен бірдей анықталады Блум сүзгісі, сияқты п, к. м - бұл Counting Bloom сүзгісіндегі санауыштардың саны, бұл кеңеюі м Блум сүзгісіндегі биттер. Ан Bloom Counting Bloom сүзгісі Бұл м санауыштар, барлығы 0-ге қойылған, Bloom сүзгісіне ұқсас болуы керек к әр түрлі хэш функциялары әрқайсысы анықталды карталар немесе жиынтық элементтің біреуіне хэш жасайды м біркелкі кездейсоқ үлестірімді тудыратын массивтің позициялары. Бұл ұқсас к тұрақты, әлдеқайда аз м, бұл қосылатын элементтер санына пропорционалды.

Bloom сүзгісінің негізгі қорытуы - элементті қосу. Кімге қосу элемент, оны әрқайсысына беріңіз к алу үшін хэш функциялары к массив позициялары және өсім барлық осы позицияларда 1 есептегіштер.

Кімге сұрау шегі бар элемент үшін θ (элементтің санау саны -дан кіші екенін тексеріңіз θ), оны әрқайсысына беріңіз к алу үшін хэш функциялары к қарсы позициялар. Егер осы позициялардағы есептегіштердің кез-келгені аз болса θ, элементтің санау саны анық θ - егер ол көп және тең болса, онда барлық сәйкес есептегіштер үлкен немесе тең болар еді θ. Егер барлығы үлкен немесе тең болса θ, демек, санау шынымен үлкен немесе тең θнемесе санауыштар кездейсоқ үлкен немесе тең болған θ. Егер барлығы үлкен болса немесе θ-ге тең болса да, санау одан кіші θ, бұл жағдай келесідей анықталады жалған оң. Мұны Bloom сүзгісі сияқты азайту керек.

Хэштеу проблемалары мен артықшылықтары туралы қараңыз Блум сүзгісі.

Жалған позитивтердің ықтималдығы

Сол жорамалдар Блум сүзгісі, хэш-функциялар кірістіруді біркелкі кездейсоқ етеді, мұнда да қарастырылған. Ішінде м кәстрөлдер, кн шарлар кездейсоқ енгізіледі. Сондықтан Bloom Counting фильтріндегі санауыштың біреуінің ықтималдығы есептеледі л болып табылады

${ displaystyle b (l, kn, { frac {1} {m}}) = {kn select l} ({ frac {1} {m}}) ^ {l} (1 - { frac {) 1} {м}}) ^ {кн-л}}$,

қайда б биномдық үлестіру болып табылады.^[1] Айтпақшы, Bloom Counting сүзгісі элементтің үлкен не тең екендігін анықтайды θ тиісті кезде к санауыштар үлкен немесе тең θ. Демек, Counting Bloom сүзгісінің элементті анықтау ықтималдығы үлкен немесе тең θ болып табылады

${ displaystyle p_ {fp} ( theta, k, n, m) = (1- sum limitler _ {l < theta} b (l, kn, { frac {1} {m}})) ^ {к}}$.

Бұл ресми анықтамадан өзгеше жалған оң Bloom Counting сүзгісінде. Алайда, Блум сүзгісіндегі болжамнан кейін, жоғарыдағы ықтималдылық Counting Bloom сүзгісінің жалған оң ретінде анықталады. Егер θ= 1, теңдеу Блум сүзгісінің жалған оңына айналады.

Хэш функциясының оңтайлы саны

Үлкен, бірақ бекітілген n және м, жалған оң k = 1-ден анықталған нүктеге дейін азаяды ${ displaystyle k_ {opt}}$, және өседі ${ displaystyle k_ {opt}}$оң шексіздікке.^[2]

Ким және басқалар. (2019) сандық мәндерін көрсетеді ${ displaystyle k_ {opt}}$ішінде ${ displaystyle 1 leq theta leq 30}$. Егер θ 30-дан үлкен, олар пайдалануды ұсынды ${ displaystyle k_ {opt} = lfloor { frac {m} {n}} (0.2037 theta +0.9176) rfloor}$немесе ${ displaystyle k_ {opt} = lceil { frac {m} {n}} (0.2037 theta +0.9176) rceil}$.

Әдебиеттер тізімі