Bloom-Filter-Implementierung

Question

Mit Hilfe des Bloom-Filters können wir den Speicherplatz optimieren. Das Cassandra-Framework verfügt ebenfalls über eine Implementierung des Bloom-Filters. Aber wie wird diese Platzoptimierung im Detail erreicht?

Answer 1

Bloom-Filter sind probabilistische Datenstrukturen, die in O(1)-Zeit sagen können, ob ein Eintrag in einer Datenbank vorhanden ist oder nicht. Sie können jedoch einige falsch-positive Ergebnisse liefern. Bei richtiger Auswahl der Hash-Funktionen und der Größe des Bit-Arrays kann der Prozentsatz der richtigen Ergebnisse jedoch bis zu 99,99 % betragen. Jedes Mal, wenn ein Eintrag in einer Datenbank vorhanden ist, füllen Sie auch den Bloom auf, indem Sie die Bits auf den Indizes, die von den Hash-Funktionen zurückgegeben werden, auf 1 setzen. Die Hash-Funktionen geben einen Wert zwischen dem Start- und dem Endindex des Bit-Arrays zurück. Welcher Wert auch immer von den Hash-Funktionen zurückgegeben wird, die Bits im Bit-Array werden auf 1 gesetzt. Beim Nachschlagen wird der Abfrageparameter erneut durch dieselben Hash-Funktionen geleitet. Wenn alle Bits auf 1 gesetzt sind, besteht eine Wahrscheinlichkeit, dass die Daten in der Datenbank vorhanden sind. Wenn eines der Bits 0 ist, dann ist der Eintrag definitiv nicht in der Datenbank vorhanden. Nachfolgend der Code für einen einfachen Bloom-Filter

import java.util.HashSet;
import java.util.Random;

public class Bloom {

static int bloom[]= new int[10000];
static HashSet<Integer> set=new HashSet<Integer>();
static int result[]= new int[4];

// truepositive,truenegative,falsepositive,falsenegative
public static void main(String[] args) {
    populate();
    getLookUpResult();
    for(int i : result){
        System.out.println(i);
    }
}
static void populate(){
    for(int i=0;i<1000;i++){
        int numb=getRandom(0,2000);
        set.add(numb);
        int h1=(numb*numb*3)%2000;
        bloom[h1]=1;
        int h2=(numb*19)%2000;
        bloom[h2]=1;
        int h3=(numb*numb)%2000;
        bloom[h3]=1;
    }
}
public static int getRandom(int l,int h){
    Random r = new Random();
    int low = l;
    int high = h;
    int result = r.nextInt(high-low) + low;
    return result;
}
public  static void getLookUpResult(){
    for(int i=0;i<2000;i++){

        if(isPresent(i)){
            if(set.contains(i)){ // true positive
                result[0]++;
            }
            else{  // false positive
                result[2]++;
            }
        }else{
            if(set.contains(i)){ // falsenegative
                result[3]++;
            }
            else{
                result[1]++;  //true negative
            }
        }
    }
}
public static boolean isPresent(int number){
    int h1=(number*number*number)%2000;
    int h2=(number*19)%2000;
    int h3=(number*number)%2000;
    return (bloom[h1]==1 && bloom[h2]==1 && bloom[h3]==1);
}

} `