💻 संगणक विज्ञान

Shift-Safe EStream-OPF: Reusable Top-K Forgetting Queries over Order-Preserving Index Streams

यह शोध पत्र Shift-Safe EStream-OPF को प्रस्तुत करता है, जो ऑर्डर-प्रिजर्विंग इंडेक्स स्ट्रीम्स के लिए एक पुन: प्रयोज्य क्वेरी फ्रेमवर्क है, जो एक्सपोनेंशियल फॉरगेटिंग के तहत बार-बार होने वाली ग्लोबल टॉप- $K$ रैंकिंग को कुशलतापूर्वक कंप्यूट करने के लिए एक संख्यात्मक रूप से स्थिर शिफ्ट-सेफ फैक्टराइजेशन का उपयोग करता है, और इंडेक्स पुन: उपयोग तथा ऑक्युरेंस-इक्विवेलेंट कम्प्रेशन का लाभ उठाते हुए बेसलाइन विधियों की तुलना में महत्वपूर्ण विलंबता सुधार प्रदर्शित करता है।

मूल लेखक: Khac-Chien Nguyen, Nhut-Minh Bui, Cong-Phat Tran

प्रकाशित 2026-11-10

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Khac-Chien Nguyen, Nhut-Minh Bui, Cong-Phat Tran

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

टाइम सीरीज़ डेटा समय के साथ चीजों के बदलने का रिकॉर्ड है: जैसे दैनिक तापमान, किसी स्टॉक की प्रति घंटा कीमत, या एक नदी का वार्षिक प्रवाह। दशकों से, कंप्यूटर वैज्ञानिकों ने इन संख्याओं की धाराओं में पैटर्न खोजने के तरीके विकसित किए हैं। एक शक्तिशाली दृष्टिकोण सटीक मानों (values) को अनदेखा करता है और इसके बजाय गति के आकार (shape) पर ध्यान केंद्रित करता है। यदि एक रेखा ऊपर जाती है, फिर नीचे आती है, और फिर से ऊपर जाती है, तो वह आकार वही रहता है चाहे संख्याएँ छोटी हों या बड़ी। यह "ऑर्डर-प्रिजर्विंग" (क्रम-संरक्षण) दृष्टिकोण उन रुझानों (trends) को मिलाने की अनुमति देता है जो एक जैसे दिखते हैं, भले ही वे अलग-अलग पैमानों पर हों। हालाँकि, इन पैटर्नों को आंकने के तरीके में एक नई चुनौती उभर कर आई है। वास्तविक दुनिया में, कल जो हुआ वह दस साल पहले जो हुआ था, उससे अधिक महत्वपूर्ण है। इसे दर्शाने के लिए, शोधकर्ता "फॉरगेटिंग" (भूलने वाले) भार का उपयोग करते हैं, जो हाल की घटनाओं को बहुत अधिक महत्व देते हैं जबकि पुरानी घटनाओं को पृष्ठभूमि में धुंधला कर देते हैं। समस्या यह है कि जब आप इस लुप्त होते प्रभाव को लागू करते हुए एक विशाल डेटासेट में सर्वोत्तम पैटर्न खोजने का प्रयास करते हैं, तो कंप्यूटर का गणित विफल हो सकता है। पुराने आयोजनों का प्रतिनिधित्व करने वाली संख्याएँ इतनी छोटी हो जाती हैं कि वे लुप्त हो जाती हैं, जबकि लुप्त होने वाले प्रभाव को दर्शाने वाली संख्याएँ इतनी बड़ी हो जाती हैं कि वे विस्फोट कर देती हैं, जिससे कंप्यूटर के पास न तो कोई संख्या बचती है और न ही कोई वैध उत्तर, बल्कि एक गणितीय त्रुटि (error) मिल जाती है।

वियतनाम के पीपल्स पुलिस यूनिवर्सिटी के शोधकर्ताओं की एक टीम ने इस विशिष्ट गणितीय जाल को हल किया है और एक ऐसी प्रणाली बनाई है जो बार-बार पूरे मानचित्र को फिर से बनाए बिना सर्वोत्तम पैटर्न के लिए बार-बार पूछ सकती है। उनका कार्य, जिसका शीर्षक 'शिफ्ट-सेफ ईस्ट्रीम-ओपीएफ' (Shift-Safe EStream-OPF) है, एक ऐसी स्थिति को संबोधित करता है जहाँ एक उपयोगकर्ता डेटा के एक निश्चित संग्रह (archive) को बार-बार एक्सप्लोर करना चाहता है, शायद इस आधार पर कि अतीत को कितनी तेज़ी से भुलाया जाना चाहिए। डेटा को हर बार शुरू से स्कैन करने के बजाय, जो धीमा और अपव्ययी है, उनकी विधि एक विशेष इंडेक्स बनाती है। यह इंडेक्स उन पैटर्नों को एक साथ समूहित करता है जो उनके प्रकट होने के बिल्कुल समान इतिहास को साझा करते हैं। शोधकर्ताओं ने इन समूहों के महत्व की गणना करने का एक चतुर तरीका खोजा जो इस गणितीय विस्फोट से बचता है। इन गणनाओं को एक पैटर्न की सबसे हालिया उपस्थिति से जोड़कर, वे यह सुनिश्चित करते हैं कि गणित का प्रत्येक चरण सुरक्षित और प्रबंधनीय सीमाओं के भीतर रहे। यह सिस्टम को "फेडिंग" (लुप्त होने वाले) प्रभाव को सही ढंग से संभालने की अनुमति देता है, जिससे पुराना डेटा शून्य में गायब होने से बच जाता है और नया डेटा सिस्टम को क्रैश होने से बचाता है।

शोधकर्ताओं ने दस अलग-अलग वास्तविक दुनिया के डेटासेट्स का उपयोग करके, जिनमें दैनिक सनस्पॉट काउंट से लेकर घरेलू ऊर्जा उपयोग के रिकॉर्ड तक शामिल थे (जिनमें 5,00,000 डेटा पॉइंट्स तक थे), मौजूदा कई विधियों के विरुद्ध इस नए दृष्टिकोण का परीक्षण किया। उन्होंने पाया कि उनकी विधि इन प्रश्नों को संभालने के मानक तरीके की तुलना में लगातार तेज़ थी, अक्सर आवश्यक समय को एक महत्वपूर्ण अंतर से कम कर देती है। उदाहरण के लिए, साप्ताहिक कार्बन डाइऑक्साइड स्तरों को ट्रैक करने वाले एक डेटासेट पर, उनका सिस्टम अगले सबसे अच्छे प्रतिस्पर्धी की तुलना में लगभग दोगुना तेज़ था। घरेलू ऊर्जा उपयोग के एक विशाल डेटासेट पर, इसने सबसे मजबूत मौजूदा विधि के समान प्रदर्शन किया, जिससे सिद्ध हुआ कि यह गति खोए बिना बहुत बड़े पैमाने को संभाल सकता है। हालाँकि, शोधकर्ताओं ने सावधानीपूर्वक यह भी नोट किया कि उनका समाधान हर स्थिति में पूरी तरह से काम करने वाला कोई जादुई समाधान नहीं है। गति का लाभ इस बात पर बहुत अधिक निर्भर करता है कि डेटा कैसे संरचित है और उपयोगकर्ता कितने परिणाम मांग रहा है। कुछ मामलों में, जहाँ डेटा पैटर्न बहुत उथले हैं या अनुरोध परिणामों की एक बहुत बड़ी संख्या के लिए है, वहाँ नई विधि ने पुराने तरीकों की तुलना में कोई लाभ नहीं दिया।

उनकी खोज का मूल एक दो-भाग वाली रणनीति है। पहला, उन्होंने महसूस किया कि समान उपस्थिति के इतिहास को साझा करने वाले पैटर्नों को एक एकल इकाई के रूप में माना जा सकता है, जिससे कंप्यूटर पूरे समूह के लिए केवल एक बार भारी गणित कर सकता है, न कि प्रत्येक व्यक्तिगत उदाहरण के लिए। दूसरा, उन्होंने एक "शिफ्ट-सेफ" गणना लागू की जो गणित को पुनर्व्यवस्थित करती है ताकि सभी संख्याएँ सकारात्मक और छोटी रहें, जिससे बहुत पुराने डेटा के साथ काम करते समय कंप्यूटर क्रैश होने से बच जाता है। यह संयोजन सिस्टम को हजारों अलग-अलग प्रश्नों के लिए उसी इंडेक्स का पुन: उपयोग करने की अनुमति देता है, जिससे यह इंटरैक्टिव विश्लेषण के लिए अत्यधिक कुशल हो जाता है जहाँ एक उपयोगकर्ता नियमों को बदलकर तुरंत नए परिणाम देखना चाह सकता है। शोधकर्ताओं ने प्रदर्शित किया कि जब एक उपयोगकर्ता क्रमवार में कई प्रश्न पूछता है, तो प्रति प्रश्न बचाया गया समय बढ़ता जाता है, जिससे अंततः नया सिस्टम एक हज़ार प्रश्नों के लिए प्रतिस्पर्धा की तुलना में लगभग चालीस प्रतिशत तेज़ हो जाता है।

यह कार्य यह दावा नहीं करता कि इसने डेटा का प्रारंभिक मानचित्र बनाने का नया तरीका आविष्कार किया है, न ही यह डेटा माइनिंग की हर समस्या को हल करने का वादा करता है। इसके बजाय, यह समय के महत्व वाले पैटर्न को रैंक करने के लिए एक मजबूत और विश्वसनीय इंजन प्रदान करता है। टीम ने दिखाया है कि यह सावधानीपूर्वक प्रबंधित करके कि कंप्यूटर पुराने सूचना के लुप्त होने को कैसे संभालता है, यह संभव है कि सिस्टम को सुचारू रूप से और तेज़ी से चलते रहने दिया जाए, भले ही डेटा अतीत में बहुत पीछे तक फैला हो। उनके निष्कर्ष उन विश्लेषकों के लिए एक व्यावहारिक उपकरण प्रदान करते हैं जिन्हें बार-बार समय-आधारित डेटा के बड़े अभिलेखागारों को एक्सप्लोर करने की आवश्यकता होती है, यह सुनिश्चित करते हुए कि सबसे प्रासंगिक, हालिया पैटर्न शीर्ष पर आएं बिना सिस्टम के गणितीय त्रुटियों या अनावश्यक पुनरावृत्ति के फंसने के।

तकनीकी सारांश: शिफ्ट-सेफ ईस्ट्रीम-ओपीएफ (Shift-Safe EStream-OPF)

समस्या विवरण
यह शोध पत्र एक निश्चित, भौतिक रूप से निर्मित (materialized) ऑर्डर-प्रिजर्विंग (OP) इंडेक्स पर एंडपॉइंट एक्सपोनेंशियल फॉरगेटिंग (endpoint exponential forgetting) के तहत बार-बार किए जाने वाले, वैश्विक टॉप-के (Top-K) रैंकिंग की समस्या को संबोधित करता है। जबकि मौजूदा OP माइनिंग विधियाँ (जैसे, OPF-Miner) फॉरगेटिंग को संभालती हैं, वे आमतौर पर थ्रेशोल्ड-संचालित और सिंगल-शॉट होती हैं, जिन्हें प्रत्येक क्वेरी के लिए कच्चे टाइम सीरीज़ से कैंडिडेट जनरेशन की आवश्यकता होती है। इसके विपरीत, मौजूदा टॉप-के विधियाँ OP इंडेक्स के संरचनात्मक गुणों का लाभ नहीं उठाती हैं जहाँ कई पैटर्न लोकाई (loci) समान उपस्थिति-आरंभ सेट (occurrence-start sets) साझा करते हैं।

मुख्य चुनौती एक "एक बार निर्माण/कई बार क्वेरी" (build-once/query-many) मॉडल को सक्षम करने की है जहाँ एक पूर्व-निर्धारित इंडेक्स विभिन्न फॉरगेटिंग दरों ( $k$ ), परिणाम गणनाओं ( $K$ ), और लंबाई श्रेणियों (length ranges) के साथ बार-बार होने वाली क्वेरी का समर्थन कर सके। एक विशिष्ट तकनीकी बाधा पहचानी गई है: संख्यात्मक सुदृढ़ता (numerical robustness): फॉरगेटिंग स्कोर ( $M_k(A) \cdot e^{k(d-1)}$ ) का सीधा उत्पाद-रूप गुणनखंड (product-form factorization) फ्लोटिंग-पॉइंट विफलता मोड का कारण बन सकता है जहाँ एक पुराना-उपस्थिति द्रव्यमान (mass) शून्य की ओर अंडरफ्लो हो जाता है जबकि एक सकारात्मक गहराई वाला एक्सपोनेंशियल इन्फिनिटी की ओर ओवरफ्लो हो जाता है, जिसके परिणामस्वरूप NaN ( $0 \cdot \infty$ ) प्राप्त होता है, भले ही वास्तविक स्कोर वैध हो।

कार्यप्रणाली (Methodology)
प्रस्तावित समाधान, शिफ्ट-सेफ ईस्ट्रीम-ओपीएफ (Shift-Safe EStream-OPF), एक क्वेरी लेयर पेश करता है जो मैक्सिमल ऑक्युरेंस-इक्विवेलेंट स्ट्रीम्स (maximal occurrence-equivalent streams) पर कार्य करता है।

संरचनात्मक अमूर्तता (Structural Abstraction): यह विधि OP लोकाई को ऐसी स्ट्रीम्स में समूहित करती है जहाँ स्ट्रीम का प्रत्येक लोकस बिल्कुल समान उपस्थिति आरंभ सेट ( $A$ ) साझा करता है। यह पूरी स्ट्रीम के लिए एक साझा "शिफ्ट-सेफ मास" (shift-safe mass) की गणना करने की अनुमति देता है, न कि प्रत्येक लोकस के लिए अलग से।
शिफ्ट-सेफ फैक्टराइजेशन (Shift-Safe Factorization): संख्यात्मक अस्थिरता को हल करने के लिए, लेखक स्ट्रीम के सबसे दाहिने उपस्थिति आरंभ (rightmost occurrence start) ( $a = \max A$ $a = max A$ ) पर आधारित एक गुणनखंड व्युत्पन्न करते हैं।
- फॉरगेटिंग सपोर्ट को इस प्रकार पुनर्गठित किया गया है:
  $fsup_k(A, d) = e^{-k(n - (a + d - 1))} \cdot R_k(A)$
  जहाँ $R_k(A) = \sum_{s \in A} e^{-k(a-s)}$ ।
- यह सुनिश्चित करता है कि मास टर्म के लिए एक्सपोनेंशियल तर्क हमेशा गैर-धनात्मक (non-positive) हो (चूंकि $a \ge s$ ), और डेप्थ-डिपेंडेंट डिके टर्म $e^{-k(n - (a + d - 1))}$ भी गैर-धनात्मक हो। $s=a$ के लिए टर्म ठीक 1 है। यह बिना किसी मनमाने परिशुद्धता (arbitrary-precision) अंकगणित की आवश्यकता के $0 \cdot \infty$ विफलता मोड को रोकता है।
क्वेरी प्रोसेसिंग पाइपलाइन:
- स्ट्रीम हेड्स (Stream Heads): प्रत्येक पात्र स्ट्रीम के लिए, एल्गोरिदम शिफ्ट-सेफ स्कोर का उपयोग करके "हेड" (कुल तुलनाकार के तहत सर्वश्रेष्ठ लोकस) की पहचान करता है।
- के-हेड प्रूनिंग (K-Head Pruning): सख्त टोटल ऑर्डर के आधार पर, केवल शीर्ष $\min(K, E)$ स्ट्रीम हेड्स को रखा जाता है (जहाँ $E$ पात्र स्ट्रीम्स की संख्या है)। वे लोकी जो उन स्ट्रीम्स में हैं जिनके हेड्स टॉप $K$ में नहीं हैं, उन्हें हटा दिया जाता है।
- मल्टीवे प्रिव (Multiway Merge): एक प्रायोरिटी क्यू (priority queue) रिटेन की गई स्ट्रीम्स के बीच एक कंपैरेटर-कंसिस्टेंट मर्ज करता है ताकि अंतिम ग्लोबल टॉप-के सूची बनाई जा सके।

प्रमुख योगदान

औपचारिक क्वेरी मॉडल: वीक-ऑर्डर पैटर्न लोकाई पर एक पुन: प्रयोज्य इंडेक्स्ड टॉप-के फॉरगेटिंग क्वेरी की परिभाषा, जिसमें कैनोनिकल वीक-ऑर्डर आइडेंटिटी, मैक्सिमल ऑक्युरेंस-इक्विवेलेंट स्ट्रीम्स, और एक नियत (deterministic) टोटल-ऑर्डर कंपैरेटर शामिल है।
शिफ्ट-सेफ फैक्टराइजेशन: दाईं ओर के उपस्थिति आरंभ पर केंद्रित एक गणितीय रूप से सिद्ध रूपांतरण, जो मानक IEEE 754 बाइनरी64 अंकगणित में संख्यात्मक सुरक्षा (कोई NaN या Infinity नहीं) की गारंटी देता है और सटीक-रियल सेमेंटिक्स को सुरक्षित रखता है।
कंपैरेटर-कंससिस्टेंट स्ट्रीम ऑर्डरिंग: राउंडेड-स्कोर प्लेटो (rounded-score plateaus) को नियत रूप से संभालने के लिए एक एल्गोरिथमिक दृष्टिकोण, जो सुनिश्चित करता है कि मशीन ऑर्डरिंग सुसंगत और पुनरुत्पादक (reproducible) है।
व्यापक कार्यान्वयन और मूल्यांकन: प्रस्तावित विधि (B6) और पांच बेसलाइन्स/एब्लेशन (B1–B5) को लागू करने वाला एक स्व-निहित जावा 21 आर्टिफैक्ट। इसमें शामिल हैं:
- दस वास्तविक दुनिया के बेंचमार्क इंस्टेंस (अधिकतम $n=500,000$ तक)।
- टाई-रिच (tie-rich) परिदृश्यों के लिए नियंत्रित सिंथेटिक जेनरेटर्स।
- सिमेंटिक वैलिडेशन के लिए एक स्वतंत्र पायथन डेसिमल ओरैकल (Decimal oracle)।
- एक "एक बार निर्माण/कई बार क्वेरी" वर्कलोड विश्लेषण।

प्रायोगिक परिणाम
मूल्यांकन पूर्ण सॉर्ट (B1), क्षमता-K हीप (B2), और फैक्टराइजेशन (B4) तथा प्रूनिंग (B5) को अलग करने वाले एब्लेशन सहित बेसलाइन्स के विरुद्ध B6 की तुलना करता है।

प्रदर्शन: 10 में से 8 वास्तविक दुनिया के डेटासेट्स पर, B6 ने प्रतिस्पर्धी क्षमता-K हीप बेसलाइन (B2) की तुलना में कम मीडियन लेटेंसी प्राप्त की। उल्लेखनीय स्पीडअप शामिल हैं:
- साप्ताहिक CO2: 1.72 $\times$
- SILSO दैनिक सनस्पॉट्स: 1.69 $\times$
- UCI हाउसहोल्ड 100k: 1.64 $\times$
- NASDAQ कंपोजिट: 1.43 $\times$
एब्लेशन अंतर्दृष्टि (Ablation Insights):
- फैक्टराइजेशन (B4) चार डेटासेट्स पर सबसे तेज़ विधि थी और उन चार में B6 के 6% के भीतर रही जहाँ B6 सबसे तेज़ था, जो दर्शाता है कि शिफ्टेड मास को साझा करना पोर्टेबल स्पीडअप का प्राथमिक स्रोत है।
- के-हेड प्रूनिंग (B6) तब अतिरिक्त लाभ प्रदान करती है जब कंप्रेशन अधिक हो और अनुरोधित परिणामों और पात्र स्ट्रीम्स का अनुपात ( $K/E$ ) छोटा हो।
- नेगेटिव बाउंड्रीज: UCI हाउसहोल्ड 500k डेटासेट (उथला कंप्रेशन, बड़ा $E$ ) पर, B6 और B2 व्यावहारिक समानता (1.00 $\times$ ) पर थे, जो दर्शाता है कि विधि के लाभ सशर्त हैं।
पुन: उपयोग: एक रिपीटेड-क्वेरी वर्कलोड (एक इंडेक्स पर 1,000 क्वेरी) में, B2 पर B6 का एमोर्टाइज्ड (amortized) लाभ 1.01 $\times$ (सिंगल क्वेरी) से बढ़कर 1.39 $\times$ हो गया, जो "एक बार निर्माण/कई बार क्वेरी" मॉडल को प्रमाणित करता है।

महत्व और दावे
यह शोध पत्र विनम्रतापूर्वक दावा करता है कि इसका योगदान सशर्त है और बार-बार ग्लोबल टॉप-के रैंकिंग, एंडपॉइंट एक्सपोनेंशियल फॉरगेटिंग, और वीक-ऑर्डर इंडेक्स स्ट्रक्चर के प्रतिच्छेदन के लिए विशिष्ट है।

कोई नया इंडेक्स निर्माण नहीं: लेखक स्पष्ट रूप से कहते हैं कि वे कोई नया प्रोडक्शन OPST निर्माण एल्गोरिदम प्रस्तावित नहीं करते हैं; वे मानते हैं कि एक भौतिक रूप से निर्मित इंडेक्स मौजूद है।
कोई नया जेनेरिक टॉप-के प्रमेय नहीं: हीप्स और मल्टीवे मर्ज का उपयोग मानक है; नवीनता OPF-विशिष्ट रूपांतरण (ऑक्युरेंस-इक्विवेलेंट फैक्टराइजेशन) में निहित है जो इन मानक उपकरणों को इस विशिष्ट संदर्भ में प्रभावी बनाता है।
संख्यात्मक सुदृढ़ता: शिफ्ट-सेफ फैक्टराइजेशन को इंटरैक्टिव क्वेरीज़ में मशीन-अंकगणित विफलताओं को रोकने के लिए एक आवश्यक इंजीनियरिंग फिक्स के रूप में प्रस्तुत किया गया है, न कि फॉरगेटिंग की अंतर्निहित गणितीय परिभाषा में बदलाव के रूप में।
दायरा: लाभ ऑक्युरेंस-इक्विवेलेंट कंप्रेशन, $K/E$ अनुपात, और इंडेक्स पुन: उपयोग पर निर्भर करते हैं। विधि सार्वभौमिक रूप से हीप-आधारित बेसलाइन्स से श्रेष्ठ नहीं है, विशेष रूप से उथले कंप्रेशन या सिंगल-शॉट क्वेरी वाले परिदृश्यों में जहाँ इंडेक्स निर्माण लेटेंसी का मुख्य हिस्सा होता है।

इसी तरह के और पेपर