अलग-अलग आइटमों की संख्या कुशलता से गिनने वाला नया एल्गोरिदम

 (quantamagazine.org)
2 पॉइंट द्वारा GN⁺ 2024-05-17 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • CVM एल्गोरिदम लंबे डेटा stream में अलग-अलग आइटमों की संख्या का approximation करता है, जिससे पूरी list को store किए बिना unique items की संख्या का estimate लगाया जा सकता है
  • यह distinct elements problem पर केंद्रित है, जहाँ पूरा input memory से बड़ा होता है; इसे बड़े logs या event streams पर लागू किया जा सकता है जिनमें duplicate inputs बहुत होते हैं
  • सीमित memory में केवल कुछ items रखकर, और space भरते ही बार-बार random deletion करके, हर item के बचे रहने की probability को बराबर रखा जाता है
  • Hamlet के उदाहरण में, 100 शब्दों की memory के साथ 5 runs का average estimate 3,955 था, जो वास्तविक unique word count 3,967 के क़रीब था; 1,000 शब्दों की memory पर average 3,964 तक बेहतर हुआ
  • memory जितनी बढ़ती है, accuracy उतनी बढ़ती है; और अगर सभी unique items रखने लायक पर्याप्त memory हो, तो 100% accuracy भी संभव है

लंबे डेटा stream में unique items गिनना

  • लक्ष्य ऐसी लंबी list में, जिसमें items एक-एक करके आते हैं, duplicates हटाने के बाद unique items की संख्या को कुशलता से estimate करना है
  • सबसे सरल तरीका है अब तक देखे गए सभी items को store करना और हर नए item के आने पर उसे मौजूदा list से compare करना
    • wildlife survey में पहले से देखी गई जानवरों की photos की list लगातार check करनी पड़ती है
    • Facebook के daily login users की संख्या जैसे मामले में, जब list अरबों तक पहुँच जाए, तो store करना और compare करना मुश्किल हो जाता है
  • CVM, Sourav Chakraborty, Vinodchandran Variyam और Kuldeep Meel के नामों पर रखा गया एल्गोरिदम है
  • यह शब्दों, conveyor belt पर products, या highway पर vehicles जैसी क्रम से आने वाली items की lists पर लागू हो सकता है

CVM एल्गोरिदम का मुख्य विचार

  • CVM सभी items को store नहीं करता, बल्कि सीमित memory में फिट होने वाले कुछ items ही बनाए रखता है
  • हर unique item के final list में बचे रहने की probability को control करने के लिए यह randomness का उपयोग करता है
  • Andrew McGregor का मानना है कि यह एल्गोरिदम बहुत सरल और implement करने में आसान है, इसलिए real-world distinct elements problem के लिए basic approach भी बन सकता है

Hamlet उदाहरण में यह कैसे काम करता है

  • Hamlet में कुल 30,557 शब्द हैं, और एल्गोरिदम इनमें से unique words की संख्या estimate करता है
  • मान लें memory 100 शब्दों वाले whiteboard जितनी है; शुरुआत में repeated words को skip करते हुए पहले 100 unique words लिखे जाते हैं
  • space भर जाने पर हर word के लिए coin toss किया जाता है
    • heads आए तो word रखा जाता है
    • tails आए तो word delete किया जाता है
    • इस preliminary step के बाद लगभग 50 unique words बचते हैं

rounds बढ़ने के साथ retention conditions और कड़े होते जाते हैं

  • Round 1 में नए words लगातार add किए जाते हैं, और अगर list में पहले से मौजूद word फिर से आता है, तो coin toss करके tails आने पर delete किया जाता है
  • list फिर से 100 words तक भरने पर, 100 coin tosses के results के आधार पर लगभग आधे words delete किए जाते हैं और Round 1 खत्म होता है
  • Round 2 से words का survive करना और कठिन हो जाता है
    • repeated word आने पर tails होने पर delete किया जाता है
    • heads आने पर coin एक बार और toss किया जाता है, और दूसरा toss भी heads होने पर ही रखा जाता है
  • तीसरे round में लगातार 3 heads चाहिए, और चौथे round में लगातार 4 heads चाहिए
  • सामान्यतः kवें round के अंत में हर word के बचे रहने की probability 1/2^k हो जाती है

estimate की गणना और experiment results

  • final list में बचे words की संख्या को उनके बचे रहने की probability से divide करने पर total unique words की संख्या estimate की जा सकती है
  • उदाहरण के लिए, 6 rounds के बाद 61 words बचे हों, तो probability 1/2^6 से divide करके 3,904 का estimate मिलता है
  • Hamlet में वास्तविक unique words की संख्या 3,967 है
  • memory size बढ़ने पर estimate वास्तविक value के करीब आता है
    • 100 शब्दों की memory के साथ 5 runs का average estimate 3,955 था
    • 1,000 शब्दों की memory के साथ average estimate 3,964 था
  • Variyam और उनके सहयोगियों ने mathematically prove किया कि इस technique की accuracy memory size के साथ scale होती है

सरल लेकिन non-obvious समाधान

  • CVM को 40 साल से अधिक समय से study किए जा रहे distinct elements problem में महत्वपूर्ण progress माना जा रहा है
  • William Kuszmaul का मानना है कि बहुत basic और अच्छी तरह researched problems में भी ऐसे solutions बचे हो सकते हैं जो सरल हों, लेकिन आसानी से दिमाग में न आएँ

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

1 टिप्पणियां

 
GN⁺ 2024-05-17
Hacker News की राय

  • इस algorithm के DNF volume counting version को implement करने में authors के साथ शामिल था। संबंधित पोस्ट यहां है: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
    Code यहां है: https://github.com/meelgroup/pepin
    Algorithm इतना बेतहाशा तेज़ है कि कई बार कुल समय का 30% तक file reading I/O में चला जाता है। संदर्भ के लिए, Knuth ने भी algorithm में योगदान दिया था, और उनके notes यहां हैं: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
    उन्होंने TAOCP के काम से पूरा एक महीना निकालकर यह किया, और जैसा आप सोच सकते हैं, वे अविश्वसनीय रूप से शानदार थे

    • सच में दिलचस्प है, और असाधारण प्रतिभा वाले लोगों में मेरी काफी रुचि है। जानना चाहूंगा कि Knuth को इतना महान क्यों महसूस किया। क्या कोई खास पल था, ideas समझने की उनकी speed थी, या आसानी से समझाने की क्षमता?
    • यह बेवकूफी जैसा लगता है। बहुत बेवकूफी भरा, लेकिन क्या मैं कुछ miss कर रहा हूं? यह counting नहीं, बस sampling है, और अगर सचमुच सभी distinct words गिनना चाहते हैं, तो simple counting की तुलना में memory usage अलग नहीं लगता
    • शायद आपको पता होगा, पर मैं सोच रहा हूं कि बड़े counts को पहले रखने के लिए sort करके, भर जाने पर निचला आधा हिस्सा discard करने का तरीका क्यों नहीं अपनाते। दूसरों को यह obvious लग सकता है, लेकिन वजह जानना चाहता हूं
    • सोच रहा हूं कि इस algorithm के मुख्य use cases क्या हैं
    • अब Knuth की अगली किताब देर से आने के लिए जिम्मेदार ठहराने को कोई मिल गया :)

  • यह algorithm paper में cite किए गए HyperLogLog जैसा दिखता है। यह लगातार heads/tails आने को track करके estimate पाने वाली वही insight इस्तेमाल करता है, लेकिन idea को उलटकर, coin outcomes की continuity के आधार पर याद रखी values को discard करने वाला ज्यादा simple algorithm बना देता है
    Streaming scenario में यह खास तौर पर efficiently काम करता है, जिससे error rate के साथ distinct elements की संख्या गिनने वाले “counter” जैसा कुछ maintain किया जा सकता है
    HyperLogLog का फायदा यह है कि कुछ मायनों में यह hash set की तरह behave करता है। आप items add कर सकते हैं, distinct items की संख्या count कर सकते हैं, और खास बात यह कि दो HLLs को merge करके union बना सकते हैं, जबकि अरबों items वाले sets में भी memory कुछ KB पर fixed रहती है। Distributed data stores में Elasticsearch/OpenSearch का cardinality agg, Redis/Redict के PFADD/PFMERGE/PFCOUNT इसी trick का इस्तेमाल करते हैं
    CVM algorithm HLL से ठीक-ठीक कैसे compare होता है, यह मुझे पक्का नहीं पता, लेकिन Knuth ने इसे review किया है और undergraduates भी इसे आसानी से implement कर सकते हैं, तो लगता है यह काफी अच्छा algorithm होगा

    • HLL दो HLLs के union और intersection दोनों का estimate कर सकता है, इसलिए इसे joins की cardinality estimation में भी इस्तेमाल किया जा सकता है
      http://oertl.github.io/hyperloglog-sketch-estimation-paper/
    • इन data structures को भी merge किया जा सकता है। जिन दो instances को merge करना है, अगर उनके “round” अलग हैं, तो earlier round वाले को round difference जितना आगे बढ़ा दें। यानी randomly आधा discard करें। उसके बाद एक list की values को दूसरी list में डालें और duplicates ignore करें। अगर result बहुत बड़ा हो जाए, तो randomly आधा discard करके round number बढ़ा दें
      पिछली नौकरी में मैंने ठीक यही algorithm implement किया था, और हर value के साथ उस value के appear होने की count का estimate भी store किया था। इससे सबसे common values की approximate list और हर value का estimated count बनाया जा सकता था
    • स्कूल के पुराने दिनों की याद के सहारे पूछ रहा हूं: यहां बताई गई HLL और CVM का उस reservoir sampling से क्या संबंध है जो हमने पहले पढ़ी थी?
      बहुत पहले hospital में काम करते समय, DAT tape में stored records का छोटा subset बनाने के लिए मैंने reservoir sampling इस्तेमाल की थी

  • पेपर पढ़ने में ब्लॉग पोस्ट पढ़ने जितना ही समय लगा, और पेपर ज़्यादा उपयोगी था
    https://arxiv.org/pdf/2301.10191
    यह stream से आए elements के set की cardinality estimate करने के बारे में है। algorithm इतना सरल है कि पेपर पढ़ते-पढ़ते आप खुद इसे code करके खेल सकते हैं
    authors साफ़ कहते हैं कि इस algorithm के लक्षित पाठक और उद्देश्य undergraduate students और textbooks हैं

    • पेपर का subtitle “An Algorithm for the (Text) Book” शायद Paul Erdős के उस मशहूर expression की ओर इशारा करता है कि कोई proof इतनी सरल और सुंदर हो कि लगे जैसे वह “The Book से निकला” हो
      Knuth ने खुद इसका review किया है, तो शायद उन्होंने भी इस algorithm को वैसा ही माना होगा। अगर ऐसा है, तो authors का इसे title में डालना थोड़ा गैर-विनम्र डींग जैसा लग सकता है, लेकिन यह डींग मारने लायक है
      मुझे पहले याद था कि यह expression Knuth ने कहा था, लेकिन मेरी याद गलत थी
    • ब्लॉग पोस्ट का आधे से ज़्यादा हिस्सा padding था। algorithm इतना सरल है कि उस पर लंबी ब्लॉग पोस्ट लिखना मुश्किल है—यह अच्छी बात ही है
    • मैं मानता हूँ कि पेपर ब्लॉग पोस्ट से बेहतर है, लेकिन CVM पेपर पर मेरी एक आलोचना यह है कि इसमें termination condition रखी गई है। दूसरे thread में आए Knuth के CVM notes में reservoir को आधा करने वाले step पर जगह और बने, इसके लिए बस एक loop रखा गया है
      https://en.wikipedia.org/wiki/Up_tack समझाने की तुलना में बस loop इस्तेमाल करना कम झंझट वाला लगता है। [1]
      [1] https://news.ycombinator.com/item?id=40388878
    • पहले computer science करता था, लेकिन शायद दिमाग अब चिकना हो गया है; यह जरूरत से ज़्यादा उलझाऊ लगता है
      पहले तो contradiction handling बस error या panic जैसी लगती है, समझ नहीं आया कि उसे ऐसे क्यों लिखा गया। फिर 1..m वाली assumption भी confusing है। पक्का नहीं था कि size पहले से जानना ज़रूरी है या नहीं, लेकिन आगे देखने पर लगता है कि नहीं। threshold चुना जाता है और stream size के हिसाब से probability बदलती है, लेकिन algorithm का description ऐसा है जैसे उसका एक ही output हो, इसलिए confusion होता है
      Chernoff bound और delta/epsilon भी पेपर में बिल्कुल explain नहीं किए गए, जिससे और उलझन हुई। Go में implement किया code यहाँ है: https://github.com/betamos/distinct
      threshold वाला हिस्सा helper में निकालना, गलती से बहुत ज़्यादा memory allocate करने से कहीं ज़्यादा sensible है। confidence या error rate estimate करने के methods भी होने चाहिए लगते हैं। stream size पहले से किसी को पता नहीं होता, इसलिए चलते-चलते इस value को update करना ज़्यादा natural है
    • अगर “undergraduate students और textbooks के लिए” का मतलब यह नहीं कि यह उनके लिए पर्याप्त सरल है, बल्कि सचमुच केवल वहीं useful है, तो अच्छा होगा कि वे explain करें कि यह experts के लिए useful क्यों नहीं और सिर्फ undergraduates के लिए ही क्यों useful है

  • पेपर के topic को देखते हुए footnote खास तौर पर आकर्षक है
    authors ने पुराने author-name alphabetical order convention के बजाय random order चुना, और उसे r⃝ से mark किया। randomization का publicly verifiable record यहाँ है: https://www.aeaweb.org/journals/policies/random-author-order...
    [0]: https://arxiv.org/pdf/2301.10191

  • क्या algorithm का explanation गलत नहीं लगता?
    “अगर list में पहले से मौजूद word मिले तो फिर से coin toss करें, और tails हो तो word हटा दें” वाले description के हिसाब से “पहले list में है या नहीं check करके फिर delete” implement करने पर करीब 20 iterations होती हैं और estimate 772800512 जैसा बेतुका आता है
    उल्टा, अगर पहले word store करें और फिर वही word delete करें, तो actual unique word count 7233 के करीब 7240 आता है। यानी description में order important है, लेकिन वह गलत तरह से communicate हुआ लगता है

    • मुझे भी यही problem आई। Quanta Magazine का explanation देखकर, arxiv paper देखे बिना implement करने पर हमेशा 461746372167462146216468796214962164 जैसा estimate आया
      पेपर पढ़ने के बाद सही estimate आया, और problem एक छोटे से else की थी। Quanta का explanation “list में नहीं है तो add करो, नहीं तो probability के हिसाब से remove करो” जैसा पढ़ा जाता है, जबकि सही implementation में add हुआ या नहीं, इससे independent होकर उसके बाद probability condition apply करनी चाहिए
    • अभी इसे solve करने की कोशिश कर रहा था और देखने आया कि क्या दूसरों को भी यही problem हुई है; हाँ, हुई है। description के हिसाब से करने पर गलत है; हर round में नया value add करने के बाद probabilistically pruning करनी चाहिए, और memory limit पर पहुँचने पर पूरे set से random आधा हिस्सा remove करना चाहिए

  • set के unique elements की संख्या estimate करना और set के unique elements की संख्या count करना बहुत अलग चीज़ें हैं। तरीका शानदार है, लेकिन title अच्छा नहीं है

    • दोनों इतने भी अलग नहीं हैं। real world में हर counting method में non-zero error rate होता है, इसलिए ज़्यादातर contexts में दोनों terms interchangeable तरीके से इस्तेमाल होते हैं
      उदाहरण के लिए election में कहते हैं “votes count करते हैं”, लेकिन close contest हो तो “recount” करते हैं और यह पूरी तरह expected है कि original count से थोड़ा अलग number आ सकता है। तब vote counting भी असल में vote estimation ही है, और recount सिर्फ़ एक estimation है जिसकी error bound संकरी होती है
      “countless stones” myth (https://en.wikipedia.org/wiki/Countless_stones) भी एक लोक-याद दिलाने जैसा लगता है कि इतने बड़े, ठोस और static standing stones जैसी चीज़ों को भी ठीक से count कर लिया गया है, इस पर बहुत ज़्यादा confidence नहीं होना चाहिए
      counting का estimation न होना लगभग mathematical situations तक सीमित है। जब guarantee कर सकें कि सभी items बिना छूटे process हुए हैं, और किसी item की identity को किसी और से confuse नहीं किया गया
    • relatively छोटे numbers के लिए सही है। लेकिन बहुत बड़े numbers में आम तौर पर estimation को counting के बराबर माना जाता है, और result integer नहीं बल्कि scientific notation, यानी floating point जैसा भी express किया जाता है
      उदाहरण के लिए mole एक integer है, लेकिन उसकी value केवल approximate रूप से ही जानी जाती है, और exact value की परवाह भी कोई नहीं करता
    • यह estimation नहीं, approximation है

  • मुझे इस तरह के डिब्बे से बाहर सोचने वाले उदाहरण सच में बहुत पसंद हैं। पेशेवर तौर पर भी यह ऐसी चीज़ है जिसमें मैं उतना अच्छा नहीं हूं, इसलिए और भी। सिर्फ़ समस्या हल करने का सही तरीका सीखना ही नहीं, बल्कि ऐसे सवाल खोजने की प्रक्रिया अहम है जो आपके पास मौजूद समस्या को आसान, और कभी-कभी संभव, बना दें
    यहां मुख्य सवाल यह है कि “सटीक संख्या की ज़रूरत नहीं है, परिभाषित parameters के भीतर probabilistic range तय कर देना काफ़ी है।” दूसरी समस्याओं के लिए दूसरे सवाल होंगे। उम्मीद है कि ऐसे पर्याप्त उदाहरण देखने से सोचने की प्रक्रिया अंदर तक बैठ जाएगी और उसे सही तरह लागू किया जा सकेगा

    • निष्पक्ष होकर कहें तो, यह काम एक university research team ने किया है। यानी सचमुच ऐसे लोगों की टीम जो पूरे दिन एक ही विषय को scientific method से बार-बार परख सकती है
      अगर किसी बड़ी company में आपको उतने ही होशियार engineers के साथ पूरे दिन whiteboard के सामने बैठने के पैसे मिलें, तो आप निश्चित रूप से कुछ ऐसा बना सकेंगे जो दुनिया को “डिब्बे से बाहर वाला समाधान” लगेगा
      लेकिन हममें से ज़्यादातर लोगों को JIRA factory line पर काम करने के पैसे मिलते हैं, इसलिए एक ही समस्या पर टिककर प्रयोग करने का समय सीमित होता है
    • आम तौर पर इसे शायद lateral thinking कहा जाता है। Edward de Bono ने इस पर कुछ किताबें लिखी हैं, जो दिलचस्प हो सकती हैं

  • “अगर आप Facebook पर रोज़ login करने वाले अलग-अलग users की संख्या गिनना चाहते हैं, और कुछ users कई devices और कई समयों पर login करते हैं?” वाला उदाहरण मुझे ऐसा scenario नहीं लगता जहां यह algorithm सच में बहुत उपयोगी हो
    अगर login process design करते समय आपको पहले से पता है कि यह जानकारी चाहिए, तो बात आसान है। हर account की last login date store करें, और stored value current date से अलग हो तभी unique user counter बढ़ाएं
    भले ही ऐसा न हो, बाद में database से login event stream को “replay” करके analysis कर सकते होंगे। हां, अगर कई सालों का data पहले से जमा हो, तो बात अलग हो सकती है

    • उस तरीके में “हर account की last login date” track करनी पड़ती है, इसलिए users की संख्या के बराबर memory चाहिए। इस algorithm की खास बात यह है कि यह बहुत कम और fixed memory में काम करता है

  • counting के संदर्भ में, मैं stream में top k items खोजने वाले एक efficient और implement करने में आसान algorithm का ज़िक्र करना चाहूंगा। लगता है यह जितना जाना जाना चाहिए, उतना नहीं है
    A Simple Algorithm for Finding Frequent Elements in Streams and Bags
    Karp, Shenker & Papadimitriou
    https://www.cs.umd.edu/~samir/498/karp.pdf

    • “stream में top k items” वाली अभिव्यक्ति abstract के description से अलग लगती है। abstract कहता है कि बड़े alphabet से आने वाली बहुत लंबी symbol sequence में ऐसे symbols जिनकी frequency दिए गए threshold से ऊपर हो खोजे जाते हैं
      आपका description ऐसा लगता है जैसे fixed k items खोजे जाते हैं और यह guarantee दी जाती है कि वे सचमुच top हैं। abstract ऐसा लगता है जैसे किसी specific value k से बड़ी condition पूरी करने वाले, पहले से unknown संख्या वाले items खोजे जाते हैं
      यह “सबसे ज़्यादा उम्र वाले 100 users खोजने” और “30 साल से ऊपर के सभी users खोजने” के फर्क जैसा दिखता है। क्या मैंने आपकी बात या abstract को गलत समझा है? English मेरी native language नहीं है, इसलिए उलझन हो रही है

  • Computer scientists ने subset size को memory-efficient तरीके से estimate करने का तरीका ईजाद कर लिया

    • अगर कम rounds के coin toss से ही estimate मिल सकता है, तो यह तेज़ भी लगता है। अलग-अलग words की संख्या estimate करने के लिए शायद पूरी “book” को आख़िर तक scan करने की ज़रूरत न पड़े
    • यहां subset अहम है। यानी unique elements का subset