💻 computer science

TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

यह शोध पत्र मौजूदा डिस्क्रीट-स्पेस (discrete-space) विधियों की सीमाओं को संबोधित करते हुए TraCS का प्रस्ताव देता है, जो निरंतर स्थानों (continuous spaces) में लोकल डिफरेंशियल प्राइवेसी (Local Differential Privacy) के तहत प्रक्षेपवक्र डेटा (trajectory data) एकत्र करने के लिए एक नया फ्रेमवर्क है, जो स्थान के आकार से स्वतंत्र रहते हुए गोपनीयता और उपयोगिता की गारंटी देता है और अत्याधुनिक विधियों से बेहतर प्रदर्शन करता है।

मूल लेखक: Ye Zheng, Yidan Hu

प्रकाशित 2026-03-03

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

CC BY 4.0

मूल लेखक: Ye Zheng, Yidan Hu

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

कल्पना कीजिए कि आप एक शहर में टहल रहे हैं, और हर कुछ मिनटों में, आपका फोन ठीक उस जगह की तस्वीर लेता है जहाँ आप हैं। यह एक "ट्रैजेक्टरी" (trajectory) बनाता है—आपके दैनिक जीवन का एक डिजिटल पदचिह्न। यह डेटा उन कंपनियों के लिए सोना है जो मैप, ट्रैफिक ऐप्स या फिटनेस ट्रैकर बना रही हैं। लेकिन इसमें एक पेंच है: यदि कोई इस निशान को चुरा लेता है, तो वे पता लगा सकते हैं कि आप कहाँ सोते हैं, कहाँ काम करते हैं, और यहाँ तक कि आपकी चिकित्सा संबंधी आदतें भी।

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

समस्या: "पिक्सेलेटेड मैप" का जाल

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

समस्या: यदि आपका शहर बहुत बड़ा है, तो इस ग्रिड में लाखों वर्ग होंगे। आपको सुरक्षित रखने के लिए, गोपनीयता उपकरण को इतना अधिक "धुंध" (noise) जोड़ना होगा कि आपका रास्ता एक बेकार, भटकते हुए मलबे जैसा बन जाए।
रुकावट: यह एक लाख घरों वाले शहर में किसी विशिष्ट घर को खोजने के लिए बेतरतीब ढंग से अनुमान लगाने जैसा है। जितने अधिक घर होंगे, सही अनुमान लगाना उतना ही कठिन होगा, और आपको अपनी गोपनीयता बनाए रखने के लिए उत्तर को उतना ही अधिक विकृत करना होगा।

समाधान: TraCS (कंटीन्यूअस स्पेस में ट्रैजेक्टरी कलेक्शन)

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

इसे इस तरह सोचें:

पुराना तरीका (डिस्क्रीट): आप एक विशिष्ट सड़क के कोने पर हैं। प्राइवेसी टूल पूछता है, "आप इन 10,000 कोनों में से किस पर हैं?" और फिर जासूस को भ्रमित करने के लिए बेतरतीब ढंग से एक अलग कोना चुन लेता है।
TraCS का तरीका (कंटीन्यूअस): आप एक चिकनी सड़क पर एक विशिष्ट बिंदु पर हैं। प्राइवेसी टूल यह नहीं पूछता कि "कौन सा वर्ग?" इसके बजाय, यह बस कहता है, "मैं आपकी लोकेशन को थोड़ा बाईं ओर और थोड़ा आगे बढ़ा दूँगा," जो एक गुप्त गणितीय नियम पर आधारित है।

TraCS कैसे काम करता है: दो नए उपकरण

लेखकों ने इस सुचारू स्थान को संभालने के लिए दो अलग-अलग "फॉग मशीनें" बनाई हैं:

1. TraCS-D: "कंपास और रूलर" विधि

कल्पना कीजिए कि आप अपने दोस्त को दिशा निर्देश दे रहे हैं। "मैं 5th और मेन पर हूँ" कहने के बजाय, आप कहते हैं, "मैं पार्क से 30 डिग्री उत्तर-पूर्व और 500 मीटर दूर हूँ।"

चाल: TraCS आपके स्थान को दो सरल भागों में तोड़ता है: दिशा (Direction) और दूरी (Distance)।
जादू: यह आपके कंपास के कोण (angle) में थोड़ी सी "नॉइज़" जोड़ता है और आपके रूलर की लंबाई में थोड़ी सी "नॉइज़" जोड़ता है। क्योंकि यह दिशा और दूरी को अलग-अलग मानता है, इसलिए यह केवल उतनी ही धुंध जोड़ सकता है जितनी आपको छिपाने के लिए आवश्यक है, बिना आपके रास्ते को एक अजीब से टेढ़े-मेढ़े चित्र में बदले।
उपमा: यह पूरी तरह से अलग शहर में होने का नाटक करने के बजाय अपनी दिशा के बारे में झूठ बोलने ("मैं वास्तव में जितना पूर्व की ओर हूँ, उससे थोड़ा अधिक पूर्व की ओर जा रहा हूँ") और अपनी दूरी के बारे में झूठ बोलने ("मैं वास्तव में जितना करीब हूँ, उससे थोड़ा दूर हूँ") जैसा है।

2. TraCS-C: "ग्राफ पेपर" विधि

कल्पना कीजिए कि एक विशाल ग्राफ पेपर है। आपका स्थान केवल एक X और एक Y निर्देशांक (coordinate) है।

चाल: TraCS-C बस आपके X निर्देशांक को लेता है और उसमें थोड़ी सी धुंध जोड़ता है, फिर आपके Y निर्देशांक को लेता है और उसमें भी थोड़ी सी धुंध जोड़ता है।
जादू: यह एक फोटो को क्षैतिज (horizontally) और लंबवत (vertically) रूप से थोड़ा धुंधला करने जैसा है। यह बहुत तेज़ और सरल है क्योंकि इसे कोणों या कंपास की दिशाओं की गणना करने की आवश्यकता नहीं होती है।

TraCS गेम चेंजर क्यों है?

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

2. यह बिजली की तरह तेज़ है
पुराने तरीकों को यह तय करने के लिए लाखों संभावनाओं की जांच करनी पड़ती थी कि धुंध कहाँ डाली जाए। TraCS बस एक त्वरित गणितीय गणना करता है।

उपमा: पुराना तरीका एक लाइब्रेरियन द्वारा एक मिलियन किताबों में से एक किताब खोजने जैसा है। TraS C एक ऐसे लाइब्रेरियन जैसा है जो जानता है कि किताब ठीक किस शेल्फ पर है और उसे तुरंत उठा लेता है।
परिणाम: TraCS मौजूदा सर्वोत्तम तरीकों की तुलना में 100 गुना तेज़ है। इसका मतलब है कि यह आपकी बैटरी खत्म किए बिना आपके फोन पर रीयल-टाइम में चल सकता है।

3. यह हर जगह काम करता है (ग्रिड पर भी)
यदि आप अभी भी पुराने "माइनक्राफ्ट" ग्रिड सिस्टम का उपयोग करना चाहते हैं, तो भी TraCS मदद कर सकता है। यह पहले सुचारू स्थान (smooth location) की गणना करता है, और फिर उसे निकटतम ग्रिड वर्ग पर सेट कर देता है। क्योंकि गणित सुचारू स्थान पर किया गया था, परिणाम अभी भी बहुत अधिक सटीक और निजी होता है यदि इसे ग्रिड पर ही किया गया होता।

निष्कर्ष

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

यहाँ शोध पत्र "TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

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

डिस्क्रीट स्पेस की सीमा (Discrete Space Constraint): वर्तमान विधियाँ (जैसे NGram, L-SRR, ATP) डिस्क्रीट लोकेशन स्पेस (ग्रिड या पॉइंट्स ऑफ इंटरेस्ट) पर कार्य करती हैं।
स्केलेबिलिटी संबंधी मुद्दे (Scalability Issues): डिस्क्रीट विधियाँ अक्सर एक्सपोनेंशियल मैकेनिज्म (Exponential Mechanism) पर निर्भर करती हैं, जिसमें कैंडिडेट लोकेशन्स की संख्या $m$ के सापेक्ष रैखिक समय जटिलता ( $\Theta(m)$ ) होती है। यह बड़े पैमाने या सूक्ष्म-स्तरीय (fine-grained) स्पेस के लिए कम्प्यूटेशनल रूप से निषेधात्मक हो जाता है।
प्राइवेसी-यूटिलिटी ट्रेड-ऑफ (Privacy-Utility Trade-off): डिस्क्रीट स्पेस में, गोपनीयता की गारंटी लोकेशन सेट के आकार से जुड़ी होती है। एक बड़ा सेट प्रभावी गोपनीयता को कमजोर करता है या अत्यधिक शोर (noise) की आवश्यकता होती है, जिससे उपयोगिता (utility) घट जाती है।
निरंतर डेटा के लिए अनुपयुक्तता (Inapplicability to Continuous Data): कई वास्तविक दुनिया के अनुप्रयोग (जैसे उड़ते हुए ड्रोन, वियरेबल सेंसर, नौकायन) कंटीन्यूअस स्पेस (वास्तविक मान वाले निर्देशांक) में डेटा उत्पन्न करते हैं। इन स्पेसों को डिस्क्रीट करने से मनमाने ग्रैनुलैरिटी विकल्प आते हैं जो गोपनीयता और उपयोगिता दोनों को नकारात्मक रूप से प्रभावित करते हैं।

लक्ष्य: ऐसे LDP मैकेनिज्म विकसित करना जो मूल रूप से 2D कंटीन्यूअस स्पेस में कार्य कर सकें, जो कठोर गोपनीयता, उच्च उपयोगिता और प्रत्येक लोकेशन के लिए स्वतंत्र रूप से निरंतर-समय ( $\Theta(1)$ ) दक्षता सुनिश्चित करें।

2. कार्यप्रणाली: TraCS (Methodology: TraCS)

लेखक TraCS (Trajectory Collection in Continuous Space) प्रस्तावित करते हैं, जो अनुकूलित पीसवाइज़-आधारित (piecewise-based) पर्टर्बेशन मैकेनिज्म लागू करने के लिए 2D कंटीन्यूअस स्पेस को 1D सबस्पेस में विभाजित करता है। वे विभिन्न ज्यामितीय विखंडन (geometric decompositions) के आधार पर दो वेरिएंट पेश करते हैं:

A. TraCS-D (दिशा-दूरी विखंडन - Direction-Distance Decomposition)

अवधारणा (Concept): एक संदर्भ बिंदु के सापेक्ष दिशा में स्थान को दिशा ( $\varphi$ ) और दूरी ( $r$ ) का उपयोग करके निरूपित करता है।
मैकेनिज्म:
1. दिशा पर्टर्बेशन ( $M^\circ$ ): कोण $\varphi \in [0, 2\pi)$ को पर्टर्ब करता है। चूंकि डोमेन गोलाकार (circular) है, इसलिए मानक लाप्लास शोर (Laplace noise) अनुपयुक्त है। लेखक विशेष रूप से सर्कुलर डोमेन के लिए एक पीसवाइज़-आधारित मैकेनिज्म (OGPM से प्रेरित) को अनुकूलित करते हैं। यह एक "डोमिनेंट सेक्टर" को परिभाषित करता है जो उच्च संभावना के साथ वास्तविक दिशा के केंद्र में होता है, जहाँ सेक्टर की चौड़ाई $\varepsilon$ बढ़ने के साथ गतिशील रूप से कम होती जाती है।
2. दूरी पर्टर्बेशन ( $M^-$ ): सामान्यीकृत दूरी $r \in [0, 1)$ को पर्टर्ब करता है। यह सीमित रैखिक डोमेन के लिए पीसवाइज़-आधारित मैकेनिज्म का उपयोग करता है।
3. कंपोजिशन (Composition): सीक्वेंशियल कंपोजिशन थ्योरम द्वारा, इन दोनों मैकेनिज्म को मिलाने से 2D लोकेशन के लिए $\varepsilon$ -LDP सुनिश्चित होता है।
वर्कफ़्लो: यह ट्रैजेक्टरी के माध्यम से पुनरावृत्ति करता है, पिछले पर्टर्ब किए गए स्थान से अगले संवेदनशील स्थान तक दिशा और दूरी को पर्टर्ब करता है।

B. TraCS-C (कार्टेशियन विखंडन - Cartesian Decomposition)

अवधारणा (Concept): स्थान को एक निश्चित मूल बिंदु (जैसे बाउंडिंग बॉक्स का निचला-बायां कोना) के सापेक्ष दो स्वतंत्र दूरी स्पेस ( $D_a$ और $D_b$ ) के कार्टेशियन उत्पाद के रूप में निरूपित करता है।
मैकेनिज्म:
1. कोऑर्डिनेट पर्टर्बेशन: देशांतर (longitude) और अक्षांश (latitude) या $x, y$ निर्देशांकों को दो स्वतंत्र 1D बाउंडेड डोमेन के रूप में मानता है।
2. प्रक्रिया: निर्देशांकों को $[0, 1)$ तक सामान्यीकृत (normalize) करता है, प्रत्येक निर्देशांक के लिए स्वतंत्र रूप से पीसवाइज़-आधारित मैकेनिज्म $M^-$ लागू करता है (प्रत्येक के लिए $\varepsilon/2$ के रूप में $\varepsilon$ को विभाजित करता है), और फिर मूल स्पेस में वापस डी-नॉर्मलाइज़ करता है।
लाभ: यह सर्कुलर डोमेन की जटिलता से बचकर सरल कार्यान्वयन प्रदान करता है।

C. डिस्क्रीट स्पेस के लिए अनुप्रयोग (Application to Discrete Spaces)

TraCS को पर्टर्ब किए गए कंटीन्यूअस कोऑर्डिनेट्स को निकटतम डिस्क्रीट पॉइंट (ग्रिड सेल या POI) में राउंड (round) करके डिस्क्रीट स्पेस पर लागू किया जा सकता है।

गोपनीयता: LDP गारंटी कंटीन्यूअस डोमेन में स्थापित की गई है; राउंडिंग एक पोस्ट-प्रोसेसिंग स्टेप है जो गोपनीयता को कमजोर नहीं करता है।
दक्षता: जटिलता डिस्क्रीट पॉइंट्स की संख्या के बावजूद प्रति लोकेशन $\Theta(1)$ रहती है, जो एक्सपोनेंशियल मैकेनिज्म-आधारित विधियों के विपरीत है।

3. मुख्य योगदान (Key Contributions)

कंटीन्यूअस ट्रैजेक्टरीज के लिए प्रथम शुद्ध LDP: यह कंटीन्यूअस स्पेस के लिए विशेष रूप से ट्रैजेक्टरी कलेक्शन विधियों को विकसित करने वाला पहला कार्य है, जो डिस्क्रीटाइजेशन के दोषों से बचता है।
नवीन विखंडन रणनीतियाँ (Novel Decomposition Strategies):
- TraCS-D: एक दिशा-दूरी पर्टर्बेशन स्कीम पेश करता है जिसमें एक विशेष सर्कुलर-डोमेन मैकेनिज्म है जो Naive $k$ -RR विस्तारों में निहित फिक्स्ड-सेक्टर त्रुटियों को समाप्त करता है।
- TraCS-C: एक कार्टेशियन कोऑर्डिनेट पर्टर्बेशन स्कीम प्रस्तावित करता है जो कम्प्यूटेशनल रूप से कुशल और लागू करने में आसान है।
सैद्धांतिक गारंटी (Theoretical Guarantees):
- सिद्ध करता है कि दोनों विधियाँ पूरी ट्रैजेक्टरी के लिए $\varepsilon$ -LDP को संतुष्ट करती हैं।
- दर्शाता है कि मीन स्क्वायर एरर (MSE), $\varepsilon$ के साथ तेजी से (exponentially) शून्य की ओर अभिसरित (converge) होता है।
- प्रति लोकेशन $\Theta(1)$ समय जटिलता स्थापित करता है, जो इसे विशाल लोकेशन सेट्स के लिए स्केलेबल बनाता है।
बहुमुखी प्रतिभा (Versatility): ये विधियाँ मूल रूप से कंटीन्यूअस स्पेस में कार्य करती हैं और राउंडिंग के माध्यम से डिस्क्रीट स्पेस में निर्बाध रूप से अनुकूलित की जा सकती हैं, जो उपयोगिता और गति दोनों में स्टेट-ऑफ-द-आर्ट डिस्क्रीट विधियों से बेहतर प्रदर्शन करती हैं।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने सिंथेटिक और वास्तविक दुनिया के डेटासेट (टोक्यो और शिकागो) पर NGram, L-SRR, ATP और एक स्ट्रोमैन (Strawman) अप्रोच (नेइव $k$ -RR + यूनिफॉर्म सैंपलिंग) जैसे बेसलाइन्स के विरुद्ध TraCS का मूल्यांकन किया।

उपयोगिता (सटीकता - Utility/Accuracy):
- कंटीन्यूअस स्पेस: TraCS, स्ट्रोमैन अप्रोच और प्लानर लाप्लास मैकेनिज्म की तुलना में काफी बेहतर प्रदर्शन करता है, विशेष रूप से जैसे-जैसे $\varepsilon$ बढ़ता है। रेक्टेंगुलर स्पेस में रैंडम ट्रैजेक्टरीज के लिए TraCS-C, TraCS-D की तुलना में कम औसत त्रुटि (Average Error - AE) देता है।
- डिस्क्रीट स्पेस: TraCS, ट्रैजेक्टरी उपयोगिता (AE, रेंज क्वेरी प्रिजर्वेशन और हॉटस्पॉट प्रिजर्वेशन द्वारा मापा गया) में NGram, L-SRR और ATP से बेहतर प्रदर्शन करता है, विशेष रूप से जब $\varepsilon$ बड़ा होता है।
दक्षता (समय लागत - Efficiency/Time Cost):
- TraCS नाटकीय रूप से तेज़ है। TKY डेटासेट पर, TraCS-D और TraCS-C को L-SRR के समय लागत का 1% से भी कम और NGram एवं ATP के समय लागत का 0.05% से भी कम समय लगा।
- ऐसा इसलिए है क्योंकि TraCS एक्सपोनेंशियल मैकेनिज्म की $\Theta(m)$ सैंपलिंग लागत से बचता है।
स्केलेबिलिटी (Scalability): डिस्क्रीट लोकेशन्स ( $m$ ) की संख्या बढ़ने पर भी प्रदर्शन स्थिर रहता है, जबकि डिस्क्रीट विधियों का प्रदर्शन काफी गिर जाता है।

5. महत्व (Significance)

पैराडाइम शिफ्ट (Paradigm Shift): TraCS निरंतर डेटा को डिस्क्रीट करने के बजाय सीधे कंटीन्यूअस स्पेस में कार्य करने पर ध्यान केंद्रित करता है, जिससे ग्रिड साइज, प्राइवेसी और यूटिलिटी के बीच अंतर्निहित ट्रेड-ऑफ को हल किया जाता है।
वास्तविक दुनिया की प्रयोज्यता (Real-World Applicability): यह उन अनुप्रयोगों के लिए गोपनीयता-संरक्षण संग्रह को सक्षम बनाता है जो स्वाभाविक रूप से कंटीन्यूअस डेटा उत्पन्न करते हैं (जैसे स्वायत्त वाहन, ड्रोन, IoT सेंसर) बिना किसी मनमाने डिस्क्रीटाइजेशन के।
स्केलेबिलिटी: $\Theta(1)$ जटिलता TraCS को उच्च-रिज़ॉल्यूशन, बड़े पैमाने के ट्रैजेक्टरी डेटा संग्रह के लिए पहला व्यवहार्य LDP समाधान बनाती है, जो पिछले स्टेट-ऑफ-द-आर्ट तरीकों के कम्प्यूटेशनल बाधाओं को दूर करती है।
दोहरी उपयोगिता (Dual Utility): यह कंटीन्यूअस अनुप्रयोगों और डिस्क्रीट अनुप्रयोगों (राउंडिंग के माध्यम से) दोनों के लिए एक बेहतर विधि के रूप में कार्य करता है, जो एक एकीकृत, कुशल और उच्च-उपयोगिता ढांचा प्रदान करता है।