자바스크립트의 블룸 필터

데이터 구조 및 알고리즘 학습 중에 새로운 데이터 구조 Bloom Filter를 소개받았습니다. 이것은 단순히 놀랍고 실제로 작동하는 것을 보는 것이 매우 궁금했습니다. 그래서 자바스크립트에 내용을 넣으려고 했는데 결과가 마음에 와닿지 🤯. 이건 미쳤어.

소개해주시고 설명해주셔서 감사합니다.

다음은 블룸 필터의 간단한 구현입니다.

const names = ['Abhin', 'Pai', ......]; // n names
const noOfHashFunction = 6; // number of hash functions

const storage = Array(Math.pow(2, 22) - 1).fill(0); // Bllom filter bit

const hash = (key) => {
  let hashNumbers = [];
  for (let i = 1; i <= noOfHashFunction; i++) {
    hashNumbers.push(
      Math.abs(
        key.split("").reduce((a, b) => ((a << i) - a + b.charCodeAt(0)) | 0, 0)
      )
    );
  }
  return hashNumbers;
};

// Initilizing bloom filter bit for a hash index
names.forEach((name) => {
  let indexes = hash(name);
  indexes.forEach((index) => (storage[index] = 1));
});

// Traditional single name search 
console.time("Single Traditional Search");
const isValueContain = (searchString) => {
  let result;
  names.forEach((name) => {
    if (name === searchString) {
      result = true;
      return;
    }
  });
  return result ? true : false;
};
console.log(isValueContain("Pai"));
console.timeEnd("Single Traditional Search");
// End of traditional Search

let result = [];
// Bloom filter single name search
console.time("Single Bloom Filter Search");
const isValueContainInBloom = (searchString) => {
  let hashes = hash(searchString);
  let result = hashes.filter((index) => !storage[index]);
  return result.length > 0 ? false : true;
};
console.log(isValueContainInBloom("Pai"));
console.timeEnd("Single Bloom Filter Search");
// End of Bloom Filter Search

// Tranditional Search for 1000 names
console.time("Traditional Search");
names.forEach((name) => {
  result.push(isValueContain(name));
});
console.log(result.filter((res) => !res));
console.timeEnd("Traditional Search");
// End of tranditional Search for 1000 names

// Boolm filter search for 1000 names
console.time("Bloom Filter");
names.forEach((name) => {
  result.push(isValueContainInBloom(name));
});
console.log(result.filter((res) => !res));
console.timeEnd("Bloom Filter");
// End of Boolm filter search for 1000 names

그리고 여기 블룸필터가 얼마나 빠른지 증명이 있습니다 😍

단일 전통적 검색: 19.371ms

단일 블룸 필터 검색: 0.239ms

기존 검색: 18.968ms

블룸 필터: 5.940ms

참고: 이 코드는 Macbook Pro 2017 2.3GHz 듀얼 코어 Intel Core i5 및 8GB RAM에서 실행되었으며 시스템에 따라 다를 수 있습니다.

이 post에 주어진 공식에 따르면

가양성을 얻을 확률은 항목 1000개당 1이지만 해시 함수의 수와 블룸 비트 크기에 따라 다릅니다.