उदाहरण के ज़रिए Bloom filter को समझना

 (llimllib.github.io)
2 पॉइंट द्वारा GN⁺ 2025-07-01 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Bloom filter एक data structure है जो बड़े set में किसी element की मौजूदगी को कम memory में तेज़ी से filter करता है, और सिर्फ़ “पक्का नहीं है” तथा “हो भी सकता है” में फ़र्क करता है
  • इसका मुख्य आधार bit vector और कई hash functions हैं; insertion के समय hash result जिन positions की ओर इशारा करते हैं, उन bits को 1 कर दिया जाता है
  • lookup के समय वही positions जाँची जाती हैं; अगर उनमें से एक भी 0 हो तो element को बाहर किया जा सकता है, लेकिन सब 1 हों तब भी false positive की संभावना बनी रहती है
  • hash functions स्वतंत्र, लगभग uniformly distributed, और तेज़ होने चाहिए; md5 से murmur पर बदलने से लगभग 800% speed improvement मिलने का एक उदाहरण है
  • filter की accuracy और cost, अनुमानित elements की संख्या n, bits की संख्या m, और hashes की संख्या k के संतुलन पर निर्भर करती है; insertion और lookup दोनों ही लगभग O(k) स्तर के होते हैं

Bloom filter कैसे काम करता है

  • Bloom filter एक probabilistic data structure है जो यह तेज़ी से और memory-efficient तरीके से तय करता है कि कोई element set में शामिल है या नहीं
  • इसका result दो ही प्रकार का होता है
    • element set में पक्का नहीं है
    • element set में हो सकता है
  • इसकी internal structure एक bit vector होती है, और element जोड़ते समय input को कई hash functions से गुज़ारा जाता है
  • हर hash value जिस bit index की ओर इशारा करती है, उसे 1 पर set कर देने से insertion पूरा हो जाता है
  • उदाहरण में Fnv और Murmur को simple hash functions के रूप में इस्तेमाल किया गया है

membership जाँच और false positive

  • lookup में भी insertion के समय वाले वही hash functions इस्तेमाल होते हैं
  • अगर hash values जिन bits की ओर इशारा करती हैं, उनमें से एक भी 0 हो, तो वह element पक्का set में नहीं है
  • अगर संबंधित bits सभी 1 हों, तो वह element हो सकता है मौजूद हो
    • संभव है कि वही bits किसी दूसरे element या कई elements के मेल से पहले ही set हो चुकी हों
  • इसी collision की वजह से Bloom filter में false positive की संभावना रहती है

hash function चुनने के मानदंड

  • Bloom filter के hash functions independent होने चाहिए, उनका वितरण uniform के क़रीब होना चाहिए, और वे जितने हो सकें उतने तेज़ होने चाहिए
  • sha1 जैसे cryptographic hashes काफ़ी इस्तेमाल होते हैं, लेकिन Bloom filter के लिए वे हमेशा सबसे अच्छा विकल्प नहीं होते
  • तेज़ और simple hash के कुछ उदाहरण:
  • Bloom filter implementation में md5 से murmur पर बदलने के बाद लगभग 800% speed improvement मिलने का एक उदाहरण है

वास्तविक implementations में इस्तेमाल होने वाले hash

  • अलग-अलग implementations Bloom filter में अलग hash functions इस्तेमाल करती हैं
    • Chromium: murmur का उपयोग
    • Plan9: Mitzenmacher 2005 में प्रस्तावित simple hash का उपयोग
    • Sdroege Bloom filter: fnv1a का उपयोग
    • Squid: MD5 का उपयोग
    • RedisBloom: murmur का उपयोग
    • Apache Spark: murmur का उपयोग
    • influxdb: xxhash का उपयोग
    • bloomd: पहले दो hashes murmur, अगले दो SpookyHash, और उसके बाद के hashes दोनों के संयोजन का उपयोग करते हैं
    • fleur, flor, bloom: fnv का उपयोग
    • Sqlite: analytical queries के लिए Bloom filter जोड़ा गया
    • RocksDB: configurable है, और source में बताया गया है कि xxhash परिवार का xxh3 सबसे अच्छा रहा
    • ScyllaDB: murmur का उपयोग

filter size और hash functions की संख्या तय करना

  • Bloom filter में false positive rate को adjust किया जा सकता है
    • बड़ा filter false positives कम करता है
    • छोटा filter false positives बढ़ाता है
  • false positive rate का लगभग अनुमान (1-e^-kn/m)^k से लगाया जाता है
    • n: insert किए जाने वाले expected elements की संख्या
    • m: filter में bits की संख्या
    • k: hash functions की संख्या
  • hash functions जितने ज़्यादा होंगे, lookup और insertion उतने धीमे होंगे और filter भी उतनी जल्दी भर जाएगा
  • इसके उलट, अगर hash functions बहुत कम हों तो false positives बहुत ज़्यादा हो सकते हैं
  • दिए गए m और n के लिए optimal k को (m/n)ln(2) से चुना जा सकता है
  • filter size को इस क्रम में तय किया जा सकता है
    • expected n का एक मोटा अनुमान लगाएँ
    • m चुनें
    • optimal k निकालें
    • चुने गए n, m, k के साथ error rate की गणना करें
    • अगर error rate स्वीकार्य न हो तो m बदलकर फिर से गणना करें

performance और उपयुक्त उपयोग की शर्तें

  • m bits और k hash functions वाले Bloom filter में insertion और membership check, दोनों O(k) होते हैं
  • element जोड़ते या जाँचते समय, element को k hash functions से गुज़ारकर संबंधित bits को set या check करना होता है
  • space efficiency स्वीकार्य error rate पर निर्भर करती है
  • अगर insert किए जा सकने वाले elements की range बहुत सीमित हो, तो deterministic bit vector बेहतर हो सकता है
  • अगर insert होने वाले elements की संख्या का मोटा अनुमान भी नहीं लगाया जा सकता, तो hash table या scalable Bloom filter ज़्यादा उपयुक्त हो सकता है

संदर्भ सामग्री और उपयोग के उदाहरण

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-07-01
Hacker News टिप्पणियां

  • यह लेख बिल्कुल मेरे जैसे लोगों के लिए लिखा गया है। Bloom filter नाम सुना था, और हर बार इसका ज़िक्र होने पर सोचता था कि कभी पढ़ूंगा; यह लेख देखकर आखिरकार पढ़ा, और यह वैसा ही परफेक्ट शुरुआती परिचय निकला जैसा मैं चाहता था :)

    • 10 साल से भी पहले iBooks search feature के लिए इसे implement करने का काम मिला था, तभी Bloom filter के बारे में पता चला
    • इसकी संरचना वाकई दिलचस्प है। जब कोई ऐसा problem आता है जहां Bloom filter चाहिए, तो बड़ा मज़ा आता है; अफसोस, domain के हिसाब से ऐसे मौके कम हो सकते हैं

  • 2009 में university में CUDA से Bloom filter बनाया था, और मेरे advisor पहले Nvidia में थे। लेकिन उसके बाद career में कभी GPU programming नहीं की
    अगर उस समय अलग choice ली होती, तो शायद 100 million dollars कमा लेता

    • मेरे साथ भी कुछ ऐसा ही था। 2009 में curiosity में GeForce 8 पर CUDA v1 इस्तेमाल करके शायद GPU-optimized bioinformatics toolkit का बहुत शुरुआती रूप बनाया था
      फिर दूसरे काम में चला गया, और बड़ा पैसा हाथ से निकल गया
    • यह देखते हुए कि यह 1970 का computer science idea है, इसकी संभावना कम लगती है। general-purpose GPU पर आज़माने लायक ideas पर पहले से ही सबकी नज़र रही होगी
      10 साल पहले GPU पर hashcash implementation बनाया था, लेकिन आज शायद उसकी लगभग कोई value नहीं होगी
    • undergraduate honors project में machine learning algorithm को CUDA में port किया, फिर बस कंधे उचकाए और embedded programming में चला गया
    • Bitcoin खरीदा होता तो उससे भी कहीं ज़्यादा कमा सकता था

  • author के लिए note: interactive part सच में बहुत अच्छा है। core idea को और पक्का दिखाने के लिए अच्छा होगा कि दो strings का example दें जिनमें hash collision होता हो; एक को पहले input box में डालने को कहें और दूसरी को दूसरे box में check करने को
    इससे दिखेगा कि जवाब हमेशा “set में हो सकता है” क्यों है, “है” क्यों नहीं

    • "bloom" और "demonstrators " collide करते हैं। दूसरी string के आखिर में space character पर ध्यान दें
      दोनों fnv: 7, murmur: 12 पर collide करते हैं

  • मेरी एक पसंदीदा trick है। अगर किसी ऐसे set पर बहुत membership checks करने हों जो कभी-कभी छोटा हो सकता है, तो बहुत simple hash function के साथ 64-bit Bloom filter speculative तरीके से जोड़ सकते हैं
    सुनने में बहुत बेवकूफी लगती है, लेकिन cost इतनी कम है कि gamble की तरह आज़माने लायक है। अगर fit न भी बैठे, तो insertion और membership check में करीब 10ns ही जोड़ता है; और अगर fit बैठ जाए, तो भारी काम बचा सकता है

    • Chromium भी कई जगह ऐसा करता है। लेख में Safe Browsing के murmur इस्तेमाल करने वाले example का ही link है, लेकिन renderer Blink आम तौर पर rapidhash इस्तेमाल करता है और ऐसे micro filters कई जगह लगाता है
      जैसे कुछ cases में querySelector(), CSS buckets में hash lookup की pre-filtering, और accessibility के लिए खास Aria attributes ढूंढते समय elements को जल्दी reject करना। यह हैरानी की बात है कि 32-bit या 64-bit के इतने छोटे filters काम करते हैं, लेकिन असल में अक्सर असरदार होते हैं। कुछ बड़े Bloom filters भी हैं। इनमें से कुछ मैंने add किए थे

  • ChatGPT से Python में एक बनाने को कहा, और उसने default md5 digest को काटकर कई hashes की तरह इस्तेमाल करने वाला तरीका use किया। non-critical use के लिए ठीक लगता है

  • Bloom filter का एक और visualization इस page के अंत में देखा जा सकता है:
    https://www.chrislaux.com/hashtable.html

  • मुझे लगा था कि यह पहले देखा है, लेकिन असल में वह यह दूसरा page था: https://bdupras.github.io/filter-tutorial/
    यह page Bloom filter और cuckoo filter की तुलना करता है, इसलिए थोड़ी और जानकारी मिलती है

  • हाल ही में Bloom filter से log message spam रोकने वाला feature implement किया। logger में message को hash करके filter में डालता था, और item मौजूद हो तो message print नहीं करता था
    हर कुछ seconds में filter पर iterate करके सभी bits clear कर देता था, और यह अच्छा fit था क्योंकि filter के सभी bits को atomically clear करने की समस्या की चिंता नहीं करनी पड़ी। messages आते समय उनमें से कुछ bits clear हो जाना ही message को फिर से log में दिखाने के लिए काफी था। पिछला implementation देखे गए messages की संख्या count करता था और N पर saturate हो जाता था; उसका असर यह था कि अगर कोई खास message बार-बार print होता, तो वह filter clear होने की speed से कम ही दिखाई देता
    Bloom filter के बारे में बस जानता था, और इस तरह naturally उसका real use case मिलकर बड़ा improvement बनाना काफी satisfying था

  • और पढ़ना चाहें तो Eli Bendersky का Bloom filter पर लेख भी अच्छा था:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Bloom filter, set, और hash table समझने के लिए ज़रूरी concepts महसूस में करीब 95% overlap करते हैं। set असल में membership checks के लिए hash table है, जहां value नहीं बल्कि सिर्फ key मायने रखती है; और Bloom filter ऐसा set है जो इस तथ्य का फायदा उठाता है कि many-to-one hashing collisions के जरिए key space को “compress” करती है
    यानी जानबूझकर बहुत collisions देने वाला hash function इस्तेमाल करने जैसा है। अगर कोई key कभी hash हुई है तो result ज़रूर positive आएगा, लेकिन उसी hash वाली कोई दूसरी key भी हो सकती है। यह bug नहीं, feature है

    • अच्छा लगा कि Bloom filter को ऐसी hash table जो actual data track नहीं करती, सिर्फ उन buckets को track करती है जहां data है के रूप में समझने वाला मैं अकेला नहीं हूं
    • इस explanation में छूटा हुआ core point यह है कि Bloom filter collisions कम करने के लिए multiple hash functions इस्तेमाल करता है। उदाहरण के लिए अगर 3 hashes हैं, तो किसी key को set में मानने के लिए तीनों hashes match होने चाहिए
      इससे false positive collision की संभावना घटती है, जबकि false negatives न होने की guarantee बनी रहती है
    • अगर आपने Bloom filter ठीक से समझ लिया है, तो random projection और locality-sensitive hashing के कुछ implementations समझने के भी काफी करीब हैं