🔢 mathematics

Frequency Sensitive Duplicate Detection Using Multi-Metric Spaces

यह शोधपत्र मल्टीसेट्स (multisets) पर आधारित और मल्टी-रियल नंबर्स (multi-real numbers) में मान वाले मल्टी-मैट्रिक स्पेस (multi-metric spaces) के एक नवीन ढांचे का प्रस्ताव करता है ताकि दूरी की गणनाओं में आवृत्ति संबंधी जानकारी को प्रभावी ढंग से शामिल किया जा सके, जिससे उन डेटा-गहन प्रणालियों में डुप्लिकेट डिटेक्शन की सटीकता में सुधार हो सके जहाँ शास्त्रीय मीट्रिक स्पेस विफल हो जाते हैं।

मूल लेखक: Debjyoti Chatterjee, Shashi Bajaj Mukherjee

प्रकाशित 2026-02-05

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

CC BY 4.0

मूल लेखक: Debjyoti Chatterjee, Shashi Bajaj Mukherjee

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

यहाँ इस शोध पत्र (paper) का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

बड़ी समस्या: जब "अधिक" का अर्थ "अलग" होता है

कल्पना कीजिए कि आप एक लाइब्रेरी व्यवस्थित कर रहे हैं। पुराने तरीके में (जिसे पेपर में "क्लासिकल मेट्रिक स्पेस" कहा गया है), यदि आपके पास दो किताबें हैं, तो सिस्टम केवल यह देखता है कि कवर पर क्या लिखा है।

किताब A: एक बिल्ली की कहानी।
किताब B: एक बिल्ली की कहानी।

पुराना सिस्टम कहता है, "ये दोनों एक जैसी हैं!" और उन्हें एक ही ढेर में रख देता है।

लेकिन क्या होगा अगर कहानी मायने रखती हो?

किताब A: एक कहानी जहाँ बिल्ली एक बार आती है।
किताब B: एक कहानी जहाँ बिल्ली दस बार आती है।

पुराना सिस्टम अभी भी कहता है, "ये एक ही हैं!" क्योंकि वह इस बात को अनदेखा कर देता है कि बिल्ली कितनी बार आई। वास्तविक दुनिया में, जैसे कि खरीदारी की रसीदों या सेंसर लॉग्स में, यह अंतर (आवृत्ति/frequency) बहुत बड़ा होता है। यदि आप एक ब्रेड खरीदते हैं, तो वह सामान्य है। यदि आप दस ब्रेड खरीदते हैं, तो वह एक पार्टी (या गलती) है। पुराना गणित इस अंतर को देख पाने में विफल रहता है।

समाधान: "मल्टी-मेट्रिक" स्पेस (Multi-Metric Space)

लेखक, देबज्योति चटर्जी और शशि बजाज मुखर्जी, डेटा के बीच की दूरी मापने का एक नया तरीका प्रस्तावित करते हैं। वे इसे मल्टी-मेट्रिक स्पेस कहते हैं।

उनके सिस्टम को एक साधारण स्केल (रूलर) के रूप में नहीं, बल्कि एक स्मार्ट तराजू के रूप में सोचें जो आइटम के प्रकार और आइटम की संख्या दोनों को तौलता है।

मल्टीसेट्स (आइटम्स का थैला): डेटा को केवल अद्वितीय वस्तुओं की एक साधारण सूची (सेट) के रूप में मानने के बजाय, वे इसे एक ऐसे थैले के रूप में मानते हैं जिसमें डुप्लिकेट्स हो सकते हैं।
- पुराना तरीका: एक थैला जिसमें {सेब, केला} है।
- नया तरीका: एक थैला जिसमें {सेब, सेब, सेब, केला} है।
- नया सिस्टम जानता है कि वहाँ तीन सेब हैं, न कि सिर्फ "एक सेब"।
मल्टी-रियल नंबर्स (स्कोरकार्ड): सामान्य गणित में, दो चीजों के बीच की दूरी केवल एक संख्या होती है (जैसे 5 मीटर)। इस नए सिस्टम में, दूरी संख्याओं का एक जोड़ा होती है।
- कल्पना कीजिए कि एक स्कोरकार्ड है जो कहता है: (मूल्य में अंतर, संख्या में अंतर)।
- यदि दो रिकॉर्ड समान हैं, तो स्कोर (0, 0) होगा।
- यदि उनके पास समान आइटम हैं लेकिन संख्या अलग है, तो स्कोर (0, 3) हो सकता है—जिसका अर्थ है "कोई अंतर नहीं कि वे क्या हैं, लेकिन इस मामले में अंतर है कि वे कितने हैं।"

यह "डुप्लिकेट्स" का पता कैसे लगाता है

यह पेपर इस सिस्टम का उपयोग एक विशिष्ट समस्या को हल करने के लिए करता है: डुप्लिकेट डिटेक्शन (Duplicate Detection)।

आमतौर पर, कंप्यूटर डेटाबेस में डुप्लिकेट रिकॉर्ड खोजने की कोशिश करते हैं (जैसे यह पता लगाना कि क्या दो ग्राहक प्रोफाइल एक ही व्यक्ति हैं)।

पुराना जाल: यदि ग्राहक A ने {दूध, ब्रेड} खरीदा और ग्राहक B ने {दूध, ब्रेड, ब्रेड, ब्रेड} खरीदा, तो पुराना कंप्यूटर सोचता है कि वे एक ही व्यक्ति हैं क्योंकि दोनों ने दूध और ब्रेड खरीदा।
नया दृष्टिकोण: मल्टी-मेट्रिक सिस्टम उनकी खरीदारी की सूचियों के बीच की "दूरी" की गणना करता है।
- वह देखता है कि दूध समान है।
- वह देखता है कि ब्रेड अलग है (1 बनाम 3)।
- वह उस अंतर के आधार पर एक "दूरी" की गणना करता है।
- परिणाम: यह सही ढंग से निर्णय लेता है, "ये डुप्लिकेट नहीं हैं," क्योंकि ब्रेड की आवृत्ति (frequency) बहुत अलग है।

सफलता का "नुस्खा" (The Recipe for Success)

पेपर इसे करने के लिए एक चरण-दर-चरण विधि (एल्गोरिदम) बताता है:

इसे तोड़ें: रिकॉर्ड के हर आइटम को देखें (जैसे रेसिपी में हर सामग्री)।
अंतर गिनें: हर सामग्री के लिए, गिनें कि रिकॉर्ड A में रिकॉर्ड B की तुलना में कितनी बार अधिक (या कम) आइटम मौजूद हैं।
सबको जोड़ें: कुल "दूरी" प्राप्त करने के लिए इन अंतरों को जोड़ें।
थ्रेशोल्ड (सीमा): आप एक नियम सेट करते हैं (threshold)। यदि कुल दूरी पर्याप्त रूप से कम है, तो वे डुप्लिकेट हैं। यदि दूरी बहुत अधिक है (संख्या के अंतर के कारण), तो वे अद्वितीय रिकॉर्ड हैं।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

लेखक दिखाते हैं कि इस "फ्रीक्वेंसी-सेंसिटिव" गणित का उपयोग करके:

आप उन गलतियों को रोकते हैं जहाँ आप सोचते हैं कि दो अलग चीजें एक ही हैं क्योंकि उनमें समान सामग्रियां शामिल हैं।
आप सिस्टम को ट्यून कर सकते हैं। आप कह सकते हैं, "मुझे फर्क नहीं पड़ता अगर ब्रेड की संख्या एक से कम या ज्यादा है, लेकिन अगर यह तीन का अंतर है, तो वे अलग हैं।"
यह स्ट्रीमिंग डेटा (जैसे लाइव सेंसर लॉग्स) के लिए काम करता है, जो सब कुछ शुरू से दोबारा जांचे बिना, पुराने डेटा के विरुद्ध नए डेटा की तुरंत जांच करता है।

सारांश उपमा (Summary Analogy)

कल्पित कीजिए कि आप दो स्मूदी रेसिपी का परीक्षण कर रहे हैं।

पुराना जज: फलों की सूची देखता है। "दोनों में स्ट्रॉबेरी और केला है। ये एक ही रेसिपी हैं!"
नया जज (मल्टी-मेट्रिक): सूची और मात्रा दोनों को देखता है। "रेसिपी A में 1 स्ट्रॉबेरी है। रेसिपी B में 10 स्ट्रॉबेरी हैं। ये अलग रेसिपी हैं।"

यह पेपर उस "नए जज" (मल्टी-मेट्रिक स्पेस) को बनाने के लिए गणितीय नियम प्रदान करता है ताकि कंप्यूटर समझ सके कि मात्रा उतनी ही महत्वपूर्ण है जितनी कि पहचान।

तकनीकी सारांश: मल्टी-मेट्रिक स्पेस का उपयोग करके आवृत्ति-संवेदनशील डुप्लिकेट डिटेक्शन

समस्या विवरण

आधुनिक डेटा-गहन प्रणालियाँ, जिनमें ट्रांजेक्शनल डेटाबेस, सेंसर नेटवर्क और लॉग फाइलें शामिल हैं, अक्सर ऐसे रिकॉर्ड उत्पन्न करती हैं जहाँ मानों की पुनरावृत्ति (repetition) आवृत्ति, तीव्रता या गणना के संबंध में महत्वपूर्ण अर्थ रखती है। हालाँकि, शास्त्रीय समानता (similarity) और दूरी (distance) मॉडल आमतौर पर सेट या निश्चित-लंबाई वाले वेक्टर्स पर आधारित मेट्रिक स्पेस पर निर्मित होते हैं। इन पारंपरिक ढांचों में, दोहराए गए तत्वों को या तो एकल उपस्थिति में समेट दिया जाता है या उन्हें सामान्यीकृत (normalize) कर दिया जाता है। फलस्वरूप, वे रिकॉर्ड जो अपनी आवृत्ति वितरण (frequency distributions) में पर्याप्त रूप से भिन्न होते हैं, उन्हें समान माना जा सकता है, जिससे सूचना की हानि होती है और त्रुटिपूर्ण समानता मूल्यांकन होता है। यह सीमा विशेष रूप से डुप्लिकेट डिटेक्शन, डेटा क्लीनिंग और रिकॉर्ड लिंकेज जैसे कार्यों में महत्वपूर्ण है, जहाँ सटीक विभेदन न केवल गुणों की उपस्थिति पर बल्कि उनकी बहुलता (multiplicity) पर भी निर्भर करता है।

कार्यप्रणाली

इन कमियों को दूर करने के लिए, लेखक मल्टीसेट्स (msets) पर परिभाषित मल्टी-मेट्रिक स्पेस पर आधारित एक ढांचा प्रस्तावित करते हैं, जहाँ दूरियों को मल्टी-रियल नंबर सिस्टम में मापा जाता है।

1. गणितीय आधार

मल्टीसेट्स (Msets): पेपर में डेटा रिकॉर्ड को एक सेट $X$ से प्राप्त मल्टीसेट्स $M$ के रूप में मॉडल किया गया है, जिसे एक काउंटिंग फंक्शन $C_M: X \to \mathbb{N}$ द्वारा परिभाषित किया गया है। यह तत्वों को विशिष्ट बहुलता ( $k/x$ ) के साथ प्रकट होने की अनुमति देता है। मानक सेट ऑपरेशन्स (यूनियन, इंटरसेक्शन, एडिशन, सबट्रैक्शन) को इन काउंट्स को संभालने के लिए पुनरपरिभाषित किया गया है।
मल्टी पॉइंट्स: एक "मल्टी पॉइंट" $P^k_x$ को एक मल्टीसेट के रूप में परिभाषित किया गया है जिसमें एक एकल तत्व $x$ उसकी बहुलता $k$ के साथ होता है। ऐसे सभी बिंदुओं का संग्रह दूरी गणनाओं के लिए आधार बनाता है।
मल्टी-रियल नंबर्स: दूरी के मान $m(\mathbb{R})$ से लिए जाते हैं, जहाँ एक मल्टी-रियल नंबर $R^k_a$ एक जोड़ा $(a, k)$ है। यहाँ, $a$ संख्यात्मक मान का प्रतिनिधित्व करता है, और $k$ बहुलता या आवृत्ति को एनकोड करता है। सेट $m(\mathbb{R})$ एक कम्यूटेटिव सेमिरिंग (commutative semiring) बनाता है जिसमें परिभाषित एडिशन ( $\oplus$ ) और मल्टीप्लिकेशन ( $\otimes$ ) ऑपरेशन्स और एक टोटल ऑर्डर ( $\leq$ ) है।
मल्टी-मेट्रिक स्पेस: एक मल्टी-मेट्रिक $d$ $d$ मल्टी-पॉइंट्स के जोड़ों से नॉन-नेगेटिव मल्टी-रियल नंबर्स ( $m(\mathbb{R}^+)$ $m (R^{+})$ ) तक का एक मैपिंग है। यह तीन अभिगृयों (axioms) को संतुष्ट करता है:
1. पहचान (Identity): $d(P^i_x, P^j_y) = R^0_0$ यदि और केवल यदि बिंदु समान हैं।
2. समरूपता (Symmetry): $d(P^i_x, P^j_y) = d(P^j_y, P^i_x)$ ।
3. त्रिकोण असमानता (Triangle Inequality): $d(P^i_x, P^k_z) \leq d(P^i_x, P^j_y) \oplus d(P^j_y, P^k_z)$ ।
  पेपर यह सिद्ध करता है कि ऐसे मेट्रिक द्वारा प्रेरित ओपन सेट्स का परिवार एक वैध टोपोलॉजी बनाता है।

2. डुप्लिकेट डिटेक्शन में अनुप्रयोग

यह कार्यप्रणाली इस ढांचे को एक परिमित एट्रिब्यूट यूनिवर्स पर मल्टीसेट्स के रूप में डेटाबेस रिकॉर्ड का प्रतिनिधित्व करके डुप्लिकेट डिटेक्शन पर लागू करती है।

दूरी गणना (Distance Computation): दो रिकॉर्ड $T_i$ और $T_j$ के बीच की दूरी प्रत्येक एट्रिब्यूट के लिए उनके संगत मल्टी-पॉइंट्स की मल्टी-मेट्रिक दूरियों को जोड़कर गणना की जाती है। एक एट्रिब्यूट $a$ के लिए मल्टी-पॉइंट $k$ और $\ell$ की प्रारंभिक दूरी को $d(P^k_a, P^\ell_a) = R^{|k-\ell|}_0$ के रूप में परिभाषित किया गया है।
डुप्लिकेट मानदंड: दो रिकॉर्ड्स को डुप्लिकेट घोषित किया जाता है यदि उनका कुल मल्टी-मेट्रिक अंतर $\delta(T_i, T_j)$ एक उपयोगकर्ता-निर्धारित टॉलरेंस थ्रेशोल्ड $\epsilon$ से कम है (जहाँ $\epsilon > R^0_0$ )। यह सुनिश्चित करता है कि डुप्लिकेशन का मूल्यांकन एट्रिब्यूट समानता और आवृत्ति वितरण की समानता दोनों के आधार पर किया जाता है।

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

पेपर $O(n^2m)$ की समय जटिलता (time complexity) के साथ एक पेयरवाइज तुलना एल्गोरिदम प्रस्तुत करता है, जहाँ $n$ रिकॉर्ड्स की संख्या है और $m$ एट्रिब्यूट्स की संख्या है। बड़े डेटाबेस के लिए स्केलेबिलिटी को संबोधित करने के लिए, लेखक प्रस्तावित करते हैं:

ब्लॉकिंग और इंडेक्सिंग: तुलनाओं को $O(nbm) $तक कम करने के लिए सपोर्ट सेट्स या सिग्नेचर के आधार पर रिकॉर्ड्स को विभाजित करना, जहाँ$ b$ औसत ब्लॉक साइज है।
स्ट्रीमिंग डिटेक्शन: स्लाइडिंग विंडोज़ और ब्लॉकिंग के माध्यम से कैंडिडेट रिट्रीवल का उपयोग करके डायनेमिक डेटा स्ट्रीम्स के लिए एक वृद्धिशील (incremental) दृष्टिकोण, जो प्रति रिकॉर्ड $O(bm)$ समय बनाए रखता है।

मुख्य योगदान

औपचारिक ढांचा (Formal Framework): पेपर मल्टी-मेट्रिक स्पेस और मल्टी-रियल नंबर्स के माध्यम से फ्रीक्वेंसी-सेंसिटिव डेटा को संभालने के लिए शास्त्रीय मेट्रिक स्पेस का एक कठोर गणितीय विस्तार पेश करता है।
आवृत्ति संरक्षण (Frequency Preservation): शास्त्रीय मेट्रिक्स (जैसे हैमिंग, जैकार्ड, यूक्लिडियन) के विपरीत जो दोहराए गए मानों को समेट देते हैं, प्रस्तावित विधि स्पष्ट रूप से दूरी गणनाओं में बहुलता को शामिल करती है।
टोपोलॉजिकल संरचना: लेखक प्रदर्शित करते हैं कि मल्टी-मेट्रिक स्पेस एक वैध टोपोलॉजी प्रेरित करते हैं, जो समानता प्रश्नों के लिए एक संरचित पड़ोस प्रणाली प्रदान करता है।
स्केलेबल एल्गोरिदम: पेपर बड़े पैमाने पर और गतिशील वातावरण में गणना-गहन पेयरवाइज तुलना को अनुकूलित करने के लिए विशिष्ट रणनीतियों (ब्लॉकिंग, प्रूनिंग, स्ट्रीमिंग) को रेखांकित करता है।

परिणाम और दृष्टांत उदाहरण

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

शास्त्रीय बनाम मल्टी-मेट्रिक: एक रिटेल ट्रांजेक्शन उदाहरण में, दो रिकॉर्ड $T_1 = \{Bread^2, Milk^1, Eggs^3\}$ और $T_2 = \{Bread^1, Milk^1, Eggs^3\}$ को शास्त्रीय सेट-आधारित मेट्रिक्स द्वारा समान ($distance = 0 $) माना जाता है। हालाँकि, मल्टी-मेट्रिक दृष्टिकोण एक गैर-शून्य दूरी ($ R^1_0$) की गणना करता है, जो ब्रेड खरीद की आवृत्ति में अंतर के कारण उन्हें सही ढंग से अलग पहचानता है।
डुप्लिकेट निर्णय: पेपर यह प्रदर्शित करता है कि $\epsilon$ थ्रेशोल्ड सेट करके, सिस्टम वास्तविक डुप्लिकेट (समान बहुलता) और निकट-डुप्लिकेट (अलग बहुलता) के बीच अंतर कर सकता है, जिससे डेटा क्लीनिंग कार्यों में फाल्स पॉजिटिव को रोका जा सकता है।

महत्व और दावे

पेपर का दावा है कि मल्टी-मेट्रिक स्पेस फ्रीक्वेंसी-सेंसिटिव डेटा के विश्लेषण के लिए एक गणितीय रूप से कठोर और एप्लिकेशन-ओरिएंटेड आधार प्रदान करते हैं। प्राथमिक महत्व निम्नलिखित को सक्षम करने में है:

सिमेंटिक अंतरों को बनाए रखना: दोहराव और तीव्रता के महत्व को बनाए रखना, जो अक्सर मानक सेट-आधारित मॉडलों में खो जाता है।
सटीकता में सुधार: एट्रिब्यूट पहचान के साथ-साथ आवृत्ति वितरण पर विचार करके डुप्लिकेट डिटेक्शन, क्लस्टरिंग और रिकॉर्ड लिंकेज की सटीकता को बढ़ाना।
ट्यूनेबिलिटी प्रदान करना: मल्टीप्लिसिटी मैपिंग फंक्शन और टॉलरेंस थ्रेशोल्ड के चयन के माध्यम से समायोज्य संवेदनशीलता (adjustable sensitivity) की अनुमति देना।

लेखक निष्कर्ष निकालते हैं कि जबकि यह दृष्टिकोण शास्त्रीय डुप्लिकेट डिटेक्शन को एक विशेष मामले के रूप में पुनः प्राप्त करता है (जब सभी मल्टीप्लिसिटीज 1 होती हैं), यह एक मजबूत विस्तार प्रदान करता है जो आधुनिक डेटा-गहन प्रणालियों के लिए आवश्यक है जहाँ पुनरावृत्ति सिमेंटिक महत्व रखती है। भविष्य के कार्य में स्केलेबल एल्गोरिदम और संभाव्य विस्तार (probabilistic extensions) का विकास शामिल है।