{"id":1819,"date":"2021-04-17T15:21:50","date_gmt":"2021-04-17T15:21:50","guid":{"rendered":"https:\/\/gauravw.com\/blog\/?p=1819"},"modified":"2021-04-17T15:26:23","modified_gmt":"2021-04-17T15:26:23","slug":"bloom-filters","status":"publish","type":"post","link":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/","title":{"rendered":"Bloom Filters"},"content":{"rendered":"\n
\"File:Comparing<\/figure>\n\n\n\n

They are a probabilistic data structure. It is just a bit array.<\/p>\n\n\n\n

This is used in conjunction with Disk. So every time instead of querying the disk once can check the bloom filter and know if it’s absent.<\/p>\n\n\n\n

Let’s take size as 8. <\/p>\n\n\n\n

_ _ _ _ _ _ _ _ _<\/p>\n\n\n\n

  1. If you get a string \u201cABC\u201d – we need to finds it Hash(\u201cABC\u201d) = 3<\/li><\/ol>\n\n\n\n

    _ _ 1 _ _ _ _ _ _<\/p>\n\n\n\n

    1. If you get a string \u201cABC\u201d – we need to finds it Hash(\u201cDEC\u201d) = 4<\/li><\/ol>\n\n\n\n

      _ _ 1 1_ _ _ _ _ _<\/p>\n\n\n\n

      Now the structure is basically used to tell the presence or absence of an element.
      IF the string is present then the hash produced by the string should be 1 else 0.<\/p>\n\n\n\n

      It is possible that there are collisions due to hash function giving the same value of string, so the presence is probabilistic but the absence is a surety.<\/p>\n\n\n\n

      To make it better, we use a much bigger size and multiple hash functions. <\/p>\n\n\n\n

      Use Cases<\/strong><\/p>\n\n\n\n

      1. To know if a username is taken or not<\/li>
      2. DBs use this on most queries columns to know if an element with such a value is present or not.<\/li>
      3. Google chrome also uses this to maintain a list of malicious websites. So it sends a long number which basically represents a bloom filter (123345435\u20261MB). This is checked before the user hits that website and display a warning.<\/li><\/ol>\n\n\n\n

        Advantages<\/strong><\/p>\n\n\n\n

        1. Size is very small <\/li>
        2. Faster to search this than a huge data structure.<\/li><\/ol>\n\n\n","protected":false},"excerpt":{"rendered":"

          They are a probabilistic data structure. It is just a bit array. This is used in conjunction with Disk. So every time instead of querying the disk once can check the bloom filter and know if it’s absent. Let’s take size as 8.  _ _ _ _ _ _ _ _ _ If you get […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[97],"tags":[],"class_list":["post-1819","post","type-post","status-publish","format-standard","hentry","category-tech-learnings"],"yoast_head":"\nBloom Filters » Gaurav Wadhwani<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Bloom Filters » Gaurav Wadhwani\" \/>\n<meta property=\"og:description\" content=\"They are a probabilistic data structure. It is just a bit array. This is used in conjunction with Disk. So every time instead of querying the disk once can check the bloom filter and know if it’s absent. Let’s take size as 8.  _ _ _ _ _ _ _ _ _ If you get […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/\" \/>\n<meta property=\"og:site_name\" content=\"Gaurav Wadhwani\" \/>\n<meta property=\"article:published_time\" content=\"2021-04-17T15:21:50+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-04-17T15:26:23+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png\" \/>\n<meta name=\"author\" content=\"Gaurav Wadhwani\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Gaurav Wadhwani\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/\"},\"author\":{\"name\":\"Gaurav Wadhwani\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#\\\/schema\\\/person\\\/9a05a9c3487f35f6b4577c6956cf252e\"},\"headline\":\"Bloom Filters\",\"datePublished\":\"2021-04-17T15:21:50+00:00\",\"dateModified\":\"2021-04-17T15:26:23+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/\"},\"wordCount\":230,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#\\\/schema\\\/person\\\/9a05a9c3487f35f6b4577c6956cf252e\"},\"image\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/upload.wikimedia.org\\\/wikipedia\\\/commons\\\/thumb\\\/b\\\/b1\\\/Comparing_de_brujin_graph_in_memory.svg\\\/512px-Comparing_de_brujin_graph_in_memory.svg.png\",\"articleSection\":[\"Tech Learnings\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/\",\"url\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/\",\"name\":\"Bloom Filters » Gaurav Wadhwani\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/upload.wikimedia.org\\\/wikipedia\\\/commons\\\/thumb\\\/b\\\/b1\\\/Comparing_de_brujin_graph_in_memory.svg\\\/512px-Comparing_de_brujin_graph_in_memory.svg.png\",\"datePublished\":\"2021-04-17T15:21:50+00:00\",\"dateModified\":\"2021-04-17T15:26:23+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#primaryimage\",\"url\":\"https:\\\/\\\/upload.wikimedia.org\\\/wikipedia\\\/commons\\\/thumb\\\/b\\\/b1\\\/Comparing_de_brujin_graph_in_memory.svg\\\/512px-Comparing_de_brujin_graph_in_memory.svg.png\",\"contentUrl\":\"https:\\\/\\\/upload.wikimedia.org\\\/wikipedia\\\/commons\\\/thumb\\\/b\\\/b1\\\/Comparing_de_brujin_graph_in_memory.svg\\\/512px-Comparing_de_brujin_graph_in_memory.svg.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/2021\\\/04\\\/bloom-filters\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Bloom Filters\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/\",\"name\":\"Gaurav Wadhwani\",\"description\":\"Where I write \\\/ scribble\",\"publisher\":{\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#\\\/schema\\\/person\\\/9a05a9c3487f35f6b4577c6956cf252e\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/gauravw.com\\\/blog\\\/#\\\/schema\\\/person\\\/9a05a9c3487f35f6b4577c6956cf252e\",\"name\":\"Gaurav Wadhwani\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g\",\"caption\":\"Gaurav Wadhwani\"},\"logo\":{\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g\"},\"sameAs\":[\"http:\\\/\\\/gauravw.com\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Bloom Filters » Gaurav Wadhwani","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/","og_locale":"en_US","og_type":"article","og_title":"Bloom Filters » Gaurav Wadhwani","og_description":"They are a probabilistic data structure. It is just a bit array. This is used in conjunction with Disk. So every time instead of querying the disk once can check the bloom filter and know if it’s absent. Let’s take size as 8.  _ _ _ _ _ _ _ _ _ If you get […]","og_url":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/","og_site_name":"Gaurav Wadhwani","article_published_time":"2021-04-17T15:21:50+00:00","article_modified_time":"2021-04-17T15:26:23+00:00","og_image":[{"url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png","type":"","width":"","height":""}],"author":"Gaurav Wadhwani","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Gaurav Wadhwani","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#article","isPartOf":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/"},"author":{"name":"Gaurav Wadhwani","@id":"https:\/\/gauravw.com\/blog\/#\/schema\/person\/9a05a9c3487f35f6b4577c6956cf252e"},"headline":"Bloom Filters","datePublished":"2021-04-17T15:21:50+00:00","dateModified":"2021-04-17T15:26:23+00:00","mainEntityOfPage":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/"},"wordCount":230,"commentCount":0,"publisher":{"@id":"https:\/\/gauravw.com\/blog\/#\/schema\/person\/9a05a9c3487f35f6b4577c6956cf252e"},"image":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#primaryimage"},"thumbnailUrl":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png","articleSection":["Tech Learnings"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/","url":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/","name":"Bloom Filters » Gaurav Wadhwani","isPartOf":{"@id":"https:\/\/gauravw.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#primaryimage"},"image":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#primaryimage"},"thumbnailUrl":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png","datePublished":"2021-04-17T15:21:50+00:00","dateModified":"2021-04-17T15:26:23+00:00","breadcrumb":{"@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#primaryimage","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png","contentUrl":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/b\/b1\/Comparing_de_brujin_graph_in_memory.svg\/512px-Comparing_de_brujin_graph_in_memory.svg.png"},{"@type":"BreadcrumbList","@id":"https:\/\/gauravw.com\/blog\/2021\/04\/bloom-filters\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/gauravw.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Bloom Filters"}]},{"@type":"WebSite","@id":"https:\/\/gauravw.com\/blog\/#website","url":"https:\/\/gauravw.com\/blog\/","name":"Gaurav Wadhwani","description":"Where I write \/ scribble","publisher":{"@id":"https:\/\/gauravw.com\/blog\/#\/schema\/person\/9a05a9c3487f35f6b4577c6956cf252e"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/gauravw.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/gauravw.com\/blog\/#\/schema\/person\/9a05a9c3487f35f6b4577c6956cf252e","name":"Gaurav Wadhwani","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g","caption":"Gaurav Wadhwani"},"logo":{"@id":"https:\/\/secure.gravatar.com\/avatar\/788ed9666a6c4e011516ae9c744df4be274dcf933161c99a4ec7e06311d2d416?s=96&d=mm&r=g"},"sameAs":["http:\/\/gauravw.com"]}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/posts\/1819","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/comments?post=1819"}],"version-history":[{"count":2,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/posts\/1819\/revisions"}],"predecessor-version":[{"id":1821,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/posts\/1819\/revisions\/1821"}],"wp:attachment":[{"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/media?parent=1819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/categories?post=1819"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gauravw.com\/blog\/wp-json\/wp\/v2\/tags?post=1819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}