2025-11-17T04:01:13.190278

Retroactive Monotonic Priority Queues via Range Searching

Castro, de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) and partially retroactive priority queues can cost $O(\log m)$ time per operation. So far, it is unknown whether this $O(\log m)$ bound can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue with a cost of $O(\log m + T(m))$ time per operation, where $T(m)$ is the maximum between the query and the update time of a specific range-searching data structure with $m$ elements. Finally, we design a fully retroactive monotonic priority queue that costs $O(\log m \log \log m)$ time per operation.

academic

श्रेणी खोज के माध्यम से पूर्वव्यापी एकदिष्ट प्राथमिकता कतारें

बुनियादी जानकारी

पेपर ID: 2508.09892
शीर्षक: श्रेणी खोज के माध्यम से पूर्वव्यापी एकदिष्ट प्राथमिकता कतारें
लेखक: लुकास कास्त्रो, रोजिएन डी फ्रीटास (कंप्यूटिंग संस्थान - UFAM, ब्राजील)
वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम), cs.CG (कम्प्यूटेशनल ज्यामिति)
प्रकाशन समय: arXiv प्रीप्रिंट, 14 अक्टूबर 2025 को अपडेट किया गया
पेपर लिंक: https://arxiv.org/abs/2508.09892

सारांश

ज्ञात सर्वोत्तम पूर्ण पूर्वव्यापी प्राथमिकता कतार प्रत्येक ऑपरेशन के लिए $O(\log^2 m \log \log m)$ समय की आवश्यकता है, जहां $m$ डेटा संरचना पर निष्पादित कुल ऑपरेशन की संख्या है। इसके विपरीत, मानक (गैर-पूर्वव्यापी) और आंशिक पूर्वव्यापी प्राथमिकता कतारें प्रत्येक ऑपरेशन के लिए केवल $O(\log m)$ समय की आवश्यकता है। यह स्पष्ट नहीं है कि पूर्ण पूर्वव्यापी प्राथमिकता कतारें $O(\log m)$ की सीमा तक पहुंच सकती हैं या नहीं। यह पेपर एकदिष्ट प्राथमिकता कतारों के इस प्रतिबंधित रूप का अध्ययन करता है, पहले यह साबित करता है कि पूर्वव्यापी एकदिष्ट प्राथमिकता कतार में न्यूनतम मान खोजना श्रेणी खोज समस्या का एक विशेष मामला है, फिर प्रत्येक ऑपरेशन के लिए $O(\log m + T(m))$ समय वाली एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार डिज़ाइन करता है, और अंत में प्रत्येक ऑपरेशन के लिए $O(\log m \log \log m)$ समय वाली एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार को लागू करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

पारंपरिक डेटा संरचनाएं केवल "वर्तमान" स्थिति पर काम कर सकती हैं, अतीत की स्थिति को क्वेरी या संशोधित नहीं कर सकती हैं। पूर्वव्यापी डेटा संरचनाएं Demaine और अन्य द्वारा प्रस्तुत की गई थीं, जो अतीत की स्थिति को संशोधित कर सकती हैं और संशोधन के परिणामों को वर्तमान स्थिति तक प्रसारित कर सकती हैं। कार्यक्षमता के आधार पर, इन्हें निम्नलिखित में विभाजित किया जा सकता है:

आंशिक पूर्वव्यापी: अतीत को संशोधित कर सकते हैं, लेकिन केवल वर्तमान स्थिति को क्वेरी कर सकते हैं
पूर्ण पूर्वव्यापी: अतीत को संशोधित भी कर सकते हैं और किसी भी समय बिंदु पर स्थिति को क्वेरी भी कर सकते हैं

अनुसंधान प्रेरणा

दक्षता अंतराल: पूर्ण पूर्वव्यापी प्राथमिकता कतार और मानक/आंशिक पूर्वव्यापी संस्करणों के बीच समय जटिलता में महत्वपूर्ण अंतर है
सैद्धांतिक चुनौती: यह स्पष्ट नहीं है कि पूर्ण पूर्वव्यापी प्राथमिकता कतारें $O(\log m)$ की सैद्धांतिक निचली सीमा तक पहुंच सकती हैं या नहीं
व्यावहारिक अनुप्रयोग: एकदिष्ट प्राथमिकता कतारें Dijkstra एल्गोरिदम जैसे परिदृश्यों में महत्वपूर्ण अनुप्रयोग मूल्य रखती हैं

मौजूदा विधियों की सीमाएं

सर्वोत्तम पूर्ण पूर्वव्यापी प्राथमिकता कतार की समय जटिलता $O(\log^2 m \log \log m)$ है
मानक प्राथमिकता कतार की $O(\log m)$ जटिलता से काफी बड़ा अंतराल है
प्रतिबंधित रूपों (जैसे एकदिष्ट प्राथमिकता कतारें) के लिए विशेष अनुसंधान की कमी है

मुख्य योगदान

सैद्धांतिक खोज: यह साबित किया कि पूर्वव्यापी एकदिष्ट प्राथमिकता कतार में न्यूनतम मान खोजना श्रेणी खोज समस्या के बराबर है
सामान्य ढांचा: $O(\log m + T(m))$ समय जटिलता के साथ एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार डिज़ाइन किया, जहां $T(m)$ श्रेणी खोज डेटा संरचना की क्वेरी/अपडेट समय है
ठोस कार्यान्वयन: 2D श्रेणी वृक्ष के आधार पर $O(\log m \log \log m)$ समय जटिलता के साथ एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार को लागू किया
ज्यामितीय दृष्टिकोण: पूर्वव्यापी प्राथमिकता कतारों को समझने के लिए एक नया ज्यामितीय दृष्टिकोण प्रदान किया

विधि विवरण

कार्य परिभाषा

निम्नलिखित ऑपरेशन का समर्थन करने वाली एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार डिज़ाइन करें:

Insert(insert(x), t): समय $t$ पर तत्व $x$ को सम्मिलित करें
Delete(insert(x), t): समय $t$ के सम्मिलन ऑपरेशन को हटाएं
Insert(extract-min, t): समय $t$ पर न्यूनतम निष्कर्षण ऑपरेशन को सम्मिलित करें
Delete(extract-min, t): समय $t$ के निष्कर्षण ऑपरेशन को हटाएं
GetMin(t): समय $t$ पर न्यूनतम तत्व लौटाएं

एकदिष्टता बाधा: निष्कर्षित तत्वों को गैर-घटते क्रम में बनाना चाहिए।

मुख्य सैद्धांतिक आधार

अस्तित्व की शर्त (लेम्मा 14)

एकदिष्ट प्राथमिकता कतार में, तत्व $x$ समय $t$ पर मौजूद है यदि और केवल यदि:

insertionTime(x) ≤ t
x > lastExtracted(t)

यह प्रत्येक तत्व के निष्कर्षण समय को बनाए रखने से बचाता है, पूर्वव्यापी ऑपरेशन की जटिलता को सरल करता है।

अंतिम निष्कर्षित तत्व की कुशल खोज (लेम्मा 16-17)

मुख्य अंतर्दृष्टि: एकदिष्ट प्राथमिकता कतार में, $k$ -वां सबसे छोटा तत्व val[k] केवल $k$ -वें निष्कर्षण ऑपरेशन em[k] द्वारा निष्कर्षित किया जा सकता है।

एल्गोरिदम:

निष्कर्षण समय वृक्ष में समय $t$ का पूर्ववर्ती ऑपरेशन खोजें
उस ऑपरेशन की अनुक्रमणिका $k$ निर्धारित करें
$k$ -वां सबसे छोटा तत्व लौटाएं

समय जटिलता: $O(\log m)$

ज्यामितीय प्रतिनिधित्व (लेम्मा 18)

एकदिष्ट प्राथमिकता कतार को 2D समतल पर बिंदुओं के रूप में प्रस्तुत करें:

प्रत्येक तत्व $e$ को बिंदु (insertionTime(e), e) के रूप में प्रस्तुत किया जाता है
GetMin(t) क्वेरी को आयत $R(t) = (-\infty, t] \times (\text{lastExtracted}(t), \infty)$ में $y$ निर्देशांक न्यूनतम बिंदु खोजने में परिवर्तित किया जाता है

यह प्रतिनिधित्व प्राथमिकता कतार क्वेरी समस्या को पूरी तरह से ज्यामितीय श्रेणी खोज समस्या में परिवर्तित करता है।

डेटा संरचना डिज़ाइन

तीन सहायक डेटा संरचनाएं:

$T_{el}$ : सभी सम्मिलित तत्वों के क्रम सांख्यिकी वृक्ष को संग्रहीत करता है
$T_{em}$ : सभी निष्कर्षण समय के क्रम सांख्यिकी वृक्ष को संग्रहीत करता है
$T_{ins}$ : सभी (सम्मिलन समय, तत्व मान) जोड़ी के न्यूनतम-y श्रेणी खोज डेटा संरचना को संग्रहीत करता है

ऑपरेशन कार्यान्वयन:

GetMin(t): पहले lastExtracted(t) खोजें, फिर $T_{ins}$ में आयत श्रेणी को क्वेरी करें
Insert/Delete(insert(x), t): $T_{el}$ और $T_{ins}$ को अपडेट करें
Insert/Delete(extract-min, t): $T_{em}$ को अपडेट करें

प्रायोगिक सेटअप

सैद्धांतिक विश्लेषण ढांचा

यह पेपर मुख्य रूप से सैद्धांतिक विश्लेषण करता है, निम्नलिखित तरीकों से विधि की सही्ता को सत्यापित करता है:

गणितीय प्रमाण: सभी मुख्य लेम्मा और प्रमेयों का कठोर प्रमाण
जटिलता विश्लेषण: विभिन्न ऑपरेशन की समय और स्थान जटिलता का विस्तृत विश्लेषण
सही्ता सत्यापन: ज्यामितीय अंतर्दृष्टि और एल्गोरिदम तर्क के माध्यम से विधि सही्ता का सत्यापन

श्रेणी खोज डेटा संरचना चयन

Mehlhorn और Näher के 2D श्रेणी वृक्ष को अंतर्निहित डेटा संरचना के रूप में चुना गया:

अपडेट समय: $O(\log n \log \log n)$ (परिशोधित, सबसे खराब स्थिति में परिवर्तनीय)
क्वेरी समय: $O(\log n \log \log n)$
स्थान जटिलता: $O(n \log n)$

प्रायोगिक परिणाम

मुख्य सैद्धांतिक परिणाम

प्रमेय 20 (सामान्य ढांचा): निम्नलिखित जटिलता के साथ एक पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार मौजूद है:

निष्कर्षण ऑपरेशन: $O(\log m)$
सम्मिलन ऑपरेशन: $O(\log m + U(m))$
क्वेरी ऑपरेशन: $O(\log m + Q(m))$
स्थान जटिलता: $O(m + S(m))$

जहां $U(m)$ , $Q(m)$ , $S(m)$ क्रमशः श्रेणी खोज डेटा संरचना के अपडेट, क्वेरी और स्थान जटिलता हैं।

प्रमेय 21 (ठोस कार्यान्वयन): 2D श्रेणी वृक्ष के आधार पर कार्यान्वयन में निम्नलिखित जटिलता है:

निष्कर्षण ऑपरेशन: $O(\log m)$
सम्मिलन ऑपरेशन: $O(\log m \log \log m)$
क्वेरी ऑपरेशन: $O(\log m \log \log m)$
स्थान जटिलता: $O(m \log m)$

जटिलता तुलना

डेटा संरचना प्रकार	समय जटिलता
मानक प्राथमिकता कतार	$O(\log m)$
आंशिक पूर्वव्यापी प्राथमिकता कतार	$O(\log m)$
पूर्ण पूर्वव्यापी प्राथमिकता कतार (ज्ञात सर्वोत्तम)	$O(\log^2 m \log \log m)$
यह पेपर: पूर्ण पूर्वव्यापी एकदिष्ट प्राथमिकता कतार	$O(\log m \log \log m)$

यह पेपर पूर्ण पूर्वव्यापी प्राथमिकता कतार जटिलता में एक महत्वपूर्ण सुधार (एकदिष्ट बाधा के तहत) को लागू करता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

सैद्धांतिक योगदान: पहली बार पूर्वव्यापी प्राथमिकता कतार समस्या को श्रेणी खोज से जोड़ा
एल्गोरिदम सुधार: एकदिष्ट बाधा के तहत पूर्ण पूर्वव्यापी प्राथमिकता कतार की दक्षता में महत्वपूर्ण सुधार
सामान्य ढांचा: विभिन्न श्रेणी खोज डेटा संरचनाओं के आधार पर डिज़ाइन के लिए एक सामान्य ढांचा प्रदान किया

सीमाएं

बाधा सीमा: केवल एकदिष्ट प्राथमिकता कतारों पर लागू, सामान्य स्थिति तक सीधे विस्तार नहीं कर सकते
सैद्धांतिक परिणाम: मुख्य रूप से सैद्धांतिक विश्लेषण, वास्तविक कार्यान्वयन और प्रायोगिक सत्यापन की कमी
जटिलता अंतराल: मानक प्राथमिकता कतार के साथ अभी भी $\log \log m$ कारक का अंतराल है

भविष्य की दिशाएं

लेखकों ने स्पष्ट रूप से तीन अनुसंधान दिशाएं प्रस्तावित की हैं:

अन्य प्रतिबंधित प्राथमिकता कतार रूपों के पूर्ण पूर्वव्यापी संस्करणों का अध्ययन
सामान्य पूर्ण पूर्वव्यापी प्राथमिकता कतारों की ऊपरी सीमा का अध्ययन
पूर्वव्यापी प्राथमिकता कतारों की निचली सीमा का अध्ययन

गहन मूल्यांकन

शक्तियां

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

कमियां

अनुप्रयोग सीमा: केवल एकदिष्ट प्राथमिकता कतारों तक सीमित, सामान्यता सीमित है
प्रयोग अनुपस्थित: वास्तविक कार्यान्वयन और प्रदर्शन परीक्षण की कमी है
निचली सीमा विश्लेषण: संबंधित निचली सीमा विश्लेषण प्रदान नहीं किया गया है
स्थिरांक कारक: सैद्धांतिक विश्लेषण स्थिरांक कारकों के प्रभाव पर विचार नहीं करता है

प्रभाव

सैद्धांतिक योगदान: पूर्वव्यापी डेटा संरचना अनुसंधान के लिए एक नया ज्यामितीय दृष्टिकोण प्रदान करता है
पद्धति मूल्य: दिखाता है कि समस्या की विशेष संरचना का लाभ कैसे उठाया जाए
प्रेरणा महत्व: अन्य प्रतिबंधित डेटा संरचनाओं के पूर्वव्यापी संस्करणों के अनुसंधान को प्रेरित कर सकता है

लागू परिदृश्य

Dijkstra एल्गोरिदम: गतिशील ग्राफ में सबसे छोटा पथ समस्या
घटना अनुसूचन: ऐतिहासिक घटनाओं को सुधारने की आवश्यकता वाली अनुसूचन प्रणाली
डेटा सुधार: डेटा को पूर्वव्यापी रूप से सुधारने की आवश्यकता वाले अनुप्रयोग परिदृश्य

संदर्भ

पेपर 13 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से:

Demaine et al. (2007) - पूर्वव्यापी डेटा संरचना का अग्रणी कार्य
Demaine et al. (2015) - वर्तमान सर्वोत्तम पूर्ण पूर्वव्यापी प्राथमिकता कतार
Mehlhorn & Näher (1990) - 2D श्रेणी वृक्ष का शास्त्रीय कार्य
Agarwal (2018) - श्रेणी खोज समस्या सर्वेक्षण

समग्र मूल्यांकन: यह सैद्धांतिक कंप्यूटर विज्ञान का एक उच्च गुणवत्ता वाला पेपर है, जो चतुर ज्यामितीय दृष्टिकोण के माध्यम से पूर्वव्यापी डेटा संरचना में एक महत्वपूर्ण समस्या को हल करता है। हालांकि परिणाम केवल एकदिष्ट स्थिति पर लागू होते हैं, विधि नई है, सिद्धांत कठोर है, और इस क्षेत्र के आगे के अनुसंधान के लिए मूल्यवान विचार और उपकरण प्रदान करता है।