2025-11-11T16:25:09.674123

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge

Joshi

We present a merge-free algorithm for multi-way co-ranking, the problem of computing cut indices $i_1,\dots,i_m$ that partition each of the $m$ sorted sequences such that all prefix segments together contain exactly $K$ elements. Our method extends two-list co-ranking to arbitrary $m$, maintaining per-sequence bounds that converge to a consistent global frontier without performing any multi-way merge or value-space search. Rather, we apply binary search to \emph{index-space}. The algorithm runs in $O(\log(\sum_t n_t)\,\log m)$ time and $O(m)$ space, independent of $K$. We prove correctness via an exchange argument and discuss applications to distributed fractional knapsack, parallel merge partitioning, and multi-stream joins. Keywords: Co-ranking \sep partitioning \sep Merge-free algorithms \sep Index-space optimization \sep Selection and merging \sep Data structures

academic

बहु-मार्ग सह-रैंकिंग: विलय के बिना क्रमबद्ध अनुक्रमों का सूचकांक-स्थान विभाजन

मूल जानकारी

पेपर ID: 2510.22882
शीर्षक: Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
लेखक: अमित जोशी (स्वतंत्र शोधकर्ता)
वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम)
प्रकाशन समय: 27 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.22882

सारांश

यह पेपर एक विलय-मुक्त बहु-मार्ग सह-रैंकिंग एल्गोरिदम प्रस्तावित करता है, जो कटौती सूचकांक $i_1,\dots,i_m$ की गणना करता है ताकि $m$ क्रमबद्ध अनुक्रमों को विभाजित किया जा सके, जिससे सभी उपसर्ग खंड कुल मिलाकर बिल्कुल $K$ तत्व शामिल करें। यह विधि सीबर्ट और ट्रैफ की दोहरी-सूची सह-रैंकिंग को मनमाना $m$ -मार्ग तक विस्तारित करती है, प्रत्येक अनुक्रम की सीमाओं को बनाए रखती है और बहु-मार्ग विलय या मान-स्थान खोज किए बिना एक सुसंगत वैश्विक सीमा तक अभिसरण करती है। एल्गोरिदम सूचकांक-स्थान में बाइनरी खोज लागू करता है, समय जटिलता $O(\log(\sum_t n_t)\log m)$ और स्थान जटिलता $O(m)$ के साथ, जो $K$ से स्वतंत्र है। विनिमय तर्क के माध्यम से सही होने को सिद्ध किया गया है, और वितरित भिन्नात्मक बैकपैक, समानांतर विलय विभाजन और बहु-धारा संयोजन में अनुप्रयोगों पर चर्चा की गई है।

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

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

बहु-मार्ग सह-रैंकिंग समस्या निम्नानुसार परिभाषित है: $m$ अनुक्रम $L_1, \ldots, L_m$ दिए गए हैं जो गैर-घटते क्रम में क्रमबद्ध हैं (दोहराव की अनुमति है), प्रत्येक अनुक्रम की लंबाई $n_t$ है, और वैश्विक लक्ष्य रैंक $K \in \{0, \ldots, N\}$ है (जहां $N = \sum_t n_t$ ), कटौती सूचकांक $i_1, \ldots, i_m$ खोजने की आवश्यकता है जो संतुष्ट करें:

$\sum_{t=1}^m i_t = K \quad \text{और} \quad \max_t \ell_t \leq \min_t r_t$

जहां $\ell_t$ और $r_t$ क्रमशः बाएं सीमा मान और दाएं सीमा मान का प्रतिनिधित्व करते हैं।

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

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

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

सीबर्ट-ट्रैफ विधि: केवल दो अनुक्रमों की सह-रैंकिंग का समर्थन करता है
फ्रेडेरिकसन-जॉनसन विधि: मान-स्थान में संचालन, वैश्विक गणना संचालन की आवश्यकता है
विभाजक-आधारित विधि: विलय या मान-डोमेन खोज की पूर्व आवश्यकता, उच्च जटिलता

मुख्य योगदान

एल्गोरिदम डिजाइन: पहला विलय-मुक्त बहु-मार्ग सह-रैंकिंग एल्गोरिदम प्रस्तावित करता है, शास्त्रीय दोहरी-मार्ग विधि को मनमाना $m$ -मार्ग तक विस्तारित करता है
सैद्धांतिक विश्लेषण: एल्गोरिदम की सही होने और $O(\log(\sum_t n_t)\log m)$ समय जटिलता को सिद्ध करता है
डेटा संरचना नवाचार: सूचकांक-स्थान में सीमा मानों को कुशलतापूर्वक बनाए रखने के लिए संबोधनीय ढेर (addressable heaps) डिजाइन करता है
अनुप्रयोग विस्तार: वितरित अनुकूलन, समानांतर प्रसंस्करण और डेटाबेस प्रणालियों में एल्गोरिदम के अनुप्रयोग की संभावना प्रदर्शित करता है

विधि विवरण

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

इनपुट:

$m$ क्रमबद्ध अनुक्रम $L_1, \ldots, L_m$ , क्रमशः लंबाई $n_1, \ldots, n_m$
लक्ष्य रैंक $K \in [0, N]$ , जहां $N = \sum_{t=1}^m n_t$

आउटपुट:

कटौती सूचकांक वेक्टर $(i_1, \ldots, i_m)$ जो सह-रैंकिंग शर्तों को संतुष्ट करता है

बाधा शर्तें:

$\sum_{t=1}^m i_t = K$
$\max_t \ell_t \leq \min_t r_t$ (सह-रैंकिंग शर्त)

एल्गोरिदम आर्किटेक्चर

मुख्य डेटा संरचना: सूचकांक ढेर

एल्गोरिदम दो सूचकांक ढेर बनाए रखता है:

$H_L$ : अधिकतम ढेर, बाएं सीमा मान $(\ell_t, t)$ संग्रहीत करता है, अधिकतम बाएं सीमा वाले अनुक्रम को लौटाता है (दाता)
$H_R$ : न्यूनतम ढेर, दाएं सीमा मान $(r_t, t)$ संग्रहीत करता है, न्यूनतम दाएं सीमा वाले अनुक्रम को लौटाता है (प्राप्तकर्ता)

प्रत्येक ढेर $O(\log m)$ update_key संचालन और $O(1)$ peek संचालन का समर्थन करता है।

सीमा प्रबंधन

प्रत्येक अनुक्रम $t$ के लिए बनाए रखें:

निचली सीमा: $Lb[t] \leq i[t]$
ऊपरी सीमा: $i[t] \leq Ub[t]$
वर्तमान सूचकांक: $i[t]$

पुनरावृत्ति रणनीति

एल्गोरिदम दाता-प्राप्तकर्ता लालची रणनीति अपनाता है:

चरम मान की पहचान करें:
- दाता $p = \arg\max_t \ell_t$ (अधिकतम बाएं सीमा)
- प्राप्तकर्ता $q = \arg\min_t r_t$ (न्यूनतम दाएं सीमा)

स्थानांतरण राशि की गणना करें:

donor_slack = ⌈(i[p] - Lb[p])/2⌉
receiver_slack = ⌈(Ub[q] - i[q])/2⌉
Δ = min{donor_slack, receiver_slack}

स्थानांतरण निष्पादित करें:
- $i[p] \leftarrow i[p] - \Delta$
- $i[q] \leftarrow i[q] + \Delta$
- सीमाएं अपडेट करें: $Ub[p] \leftarrow i[p]$ , $Lb[q] \leftarrow i[q]$
ढेर अपडेट करें: प्रभावित अनुक्रमों के ढेर कुंजी मान को ताज़ा करें

तकनीकी नवाचार बिंदु

सूचकांक-स्थान संचालन: पूरी तरह से सूचकांक-स्थान में काम करता है, मान-डोमेन खोज और विलय संचालन से बचा जाता है
ज्यामितीय अभिसरण: आधे में कटौती करके व्यवहार्य डोमेन को कम करके, लॉगरिदमिक-स्तरीय अभिसरण गति सुनिश्चित करता है
असंतुलित संभावना फ़ंक्शन: $\Phi(i) = \max_t \ell_t - \min_t r_t$ को अभिसरण मानदंड के रूप में परिभाषित करता है
निर्धारक जटिलता: एल्गोरिदम जटिलता लक्ष्य रैंक $K$ से स्वतंत्र है

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

सही होने का प्रमाण

लेम्मा 1 (स्थानीय चरम इष्टतमता)

यदि $\Phi(i) > 0$ , $p = \arg\max_t \ell_t$ और $q = \arg\min_t r_t$ सेट करें। $\sum_t i_t = K$ को बनाए रखने वाले सभी व्यवहार्य अनंत स्थानांतरणों में, $(p,q)$ जोड़ी $\Phi$ के सबसे बड़े गैर-बढ़ते परिवर्तन को प्राप्त करती है।

प्रमाण विचार: $i_p$ को कम करने से $\ell_p$ कम होता है (बाएं सीमा का स्थानीय अधिकतम), $i_q$ को बढ़ाने से $r_q$ बढ़ता है (दाएं सीमा का स्थानीय न्यूनतम)। चूंकि $\ell_p \geq \ell_u$ और $r_q \leq r_v$ सभी $u,v$ के लिए सत्य है, चरम जोड़ी $(p,q)$ अंतराल $\max\ell - \min r$ में सबसे तीव्र कमी पैदा करती है।

लेम्मा 2 (स्थानांतरण क्रम विनिमय क्षमता)

$\Phi$ को कम करने वाले किसी भी व्यवहार्य स्थानांतरण अनुक्रम को पुनः क्रमित किया जा सकता है ताकि सभी चरम $(p,q)$ स्थानांतरण किसी भी गैर-चरम स्थानांतरण से पहले हों, और किसी भी मध्यवर्ती चरण के $\Phi$ को बिगाड़ न दें।

प्रमेय 1 (अभिसरण और वैधता)

एल्गोरिदम 2 एक वैध सह-रैंकिंग वेक्टर $(i_1, \ldots, i_m)$ के साथ समाप्त होता है, जो $\sum_t i_t = K$ और $\max_t \ell_t \leq \min_t r_t$ को संतुष्ट करता है।

जटिलता विश्लेषण

राउंड विश्लेषण

प्रत्येक राउंड में, दाता या प्राप्तकर्ता की व्यवहार्य दूरी आधे में कट जाती है। प्रत्येक अनुक्रम की दूरी $Ub[t] - Lb[t]$ अधिकतम $O(\log n_t)$ बार कम होती है। सभी $m$ अनुक्रमों को एकत्रित करने पर, कुल राउंड संख्या है:

$T = O\left(\log\left(\sum_{t=1}^m n_t\right)\right)$

समय जटिलता

प्रत्येक राउंड स्थिर बार सूचकांक ढेर संचालन निष्पादित करता है ( $O(\log m)$ समय), कुल समय जटिलता है:

$O\left(\log\left(\sum_t n_t\right) \cdot \log m\right)$

स्थान जटिलता

एल्गोरिदम को केवल $m$ अनुक्रमों के सूचकांक और सीमा जानकारी संग्रहीत करने की आवश्यकता है, स्थान जटिलता $O(m)$ है।

एल्गोरिदम कार्यान्वयन

मुख्य एल्गोरिदम प्रवाह

def multi_way_corank(sequences, K):
    m = len(sequences)
    # सीमाओं और सूचकांकों को आरंभ करें
    Lb = [0] * m
    Ub = [len(seq) for seq in sequences]
    i = water_fill_initialization(K, Ub)
    
    # सूचकांक ढेर बनाएं
    HL = MaxHeap()  # बाएं सीमा अधिकतम ढेर
    HR = MinHeap()  # दाएं सीमा न्यूनतम ढेर
    
    for t in range(m):
        HL.insert(t, left_boundary(sequences[t], i[t]))
        HR.insert(t, right_boundary(sequences[t], i[t]))
    
    while True:
        # दाता और प्राप्तकर्ता प्राप्त करें
        max_left, p = HL.peek()
        min_right, q = HR.peek()
        
        # समाप्ति शर्त की जांच करें
        if max_left <= min_right:
            break
            
        # स्थानांतरण राशि की गणना करें
        donor_slack = ceil((i[p] - Lb[p]) / 2)
        receiver_slack = ceil((Ub[q] - i[q]) / 2)
        delta = min(donor_slack, receiver_slack)
        
        # स्थानांतरण निष्पादित करें
        i[p] -= delta
        i[q] += delta
        
        # सीमाएं अपडेट करें
        Ub[p] = i[p]
        Lb[q] = i[q]
        
        # ढेर अपडेट करें
        update_heaps(HL, HR, sequences, i, p, q)
    
    return i

आरंभीकरण रणनीति

"जल भरण" रणनीति का उपयोग करके व्यवहार्य समाधान को आरंभ करें:

def water_fill_initialization(K, capacities):
    i = [0] * len(capacities)
    need = K
    for t in range(len(capacities)):
        take = min(capacities[t], need)
        i[t] = take
        need -= take
        if need == 0:
            break
    return i

अनुप्रयोग परिदृश्य

1. वितरित भिन्नात्मक बैकपैक समस्या

बहु-स्रोत भिन्नात्मक बैकपैक समस्या में, जब वस्तुएं घनत्व के अनुसार क्रमबद्ध होती हैं और $m$ शार्ड में वितरित होती हैं, तो सह-रैंकिंग का उपयोग करके वैश्विक $K$ उपसर्ग विभाजन की गणना की जा सकती है, स्रोत डेटा को विलय किए बिना।

2. समानांतर $m$ -मार्ग विलय विभाजन

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

3. बहु-धारा संयोजन विभाजन

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

प्रायोगिक सत्यापन

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

सैद्धांतिक प्रदर्शन गारंटी

समय जटिलता: $O(\log(\sum_t n_t) \log m)$
स्थान जटिलता: $O(m)$
स्वतंत्रता: जटिलता लक्ष्य रैंक $K$ से स्वतंत्र है

मौजूदा विधियों के साथ तुलना

विलय विधि की तुलना में: $O(N)$ विलय ओवरहेड से बचा जाता है
मान-स्थान विधि की तुलना में: वैश्विक गणना संचालन से बचा जाता है
फ्रेडेरिकसन-जॉनसन की तुलना में: सूचकांक-स्थान में संचालन, अधिक कुशल

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

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

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

सीमाएं

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

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

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

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

शक्तियां

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

कमियां

प्रायोगिक कमी: पेपर में प्रायोगिक सत्यापन की कमी है, वास्तविक प्रदर्शन का मूल्यांकन नहीं कर सकते
सीमित तुलना: मौजूदा विधियों के साथ विस्तृत प्रदर्शन तुलना नहीं है
अनुप्रयोग गहराई: अनुप्रयोग परिदृश्यों की चर्चा अपेक्षाकृत सरल है, गहन विश्लेषण की कमी है

प्रभाव

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

उपयुक्त परिदृश्य

वितरित प्रणालियों में डेटा विभाजन
समानांतर एल्गोरिदम में भार संतुलन
डेटाबेस प्रणालियों में क्वेरी अनुकूलन
स्ट्रीम प्रसंस्करण प्रणालियों में बहु-धारा विलय

संदर्भ

1 Greg N. Frederickson and Donald B. Johnson. Generalized selection and ranking. STOC 1980.

2 Christian Siebert. Perfectly load-balanced, stable, synchronization-free parallel merge. Parallel Processing Letters, 2014.

3 Christian Siebert. Simple in-place yet comparison-optimal mergesort, arXiv:2509.24540, 2025.

4 Christian Siebert and Felix Wolf. A scalable parallel sorting algorithm using exact splitting. RWTH Aachen University technical report, 2011.

समग्र मूल्यांकन: यह एक सैद्धांतिक रूप से मजबूत एल्गोरिदम पेपर है, जो बहु-मार्ग सह-रैंकिंग की महत्वपूर्ण समस्या को सफलतापूर्वक हल करता है। हालांकि प्रायोगिक सत्यापन की कमी है, लेकिन सैद्धांतिक विश्लेषण कठोर है, विधि नवाचार मजबूत है, और संबंधित क्षेत्रों के लिए मूल्यवान सैद्धांतिक उपकरण प्रदान करता है।