PathFinder: A unified approach for handling paths in graph query languages
यह शोध पत्र PathFinder को प्रस्तुत करता है, जो आधुनिक ग्राफ भाषाओं में पाथ क्वेरीज़ को प्रोसेस करने के लिए एक एकीकृत और अत्यधिक कुशल दृष्टिकोण है, जो स्थिर प्रदर्शन प्राप्त करने और मौजूदा ग्राफ इंजनों से एक क्रम (order of magnitude) बेहतर प्रदर्शन करने के लिए कॉम्पैक्ट पाथ रिप्रेजेंटेशन और पाइपलाइन्ड निष्पादन का लाभ उठाता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप ग्राफ सिटी (Graph City) नामक एक विशाल, जादुई शहर की खोज कर रहे हैं। इस शहर में, हर व्यक्ति एक इमारत (एक नोड) है, और उनके बीच के हर संबंध को एक सड़क (एक एज) के रूप में दर्शाया गया है जिस पर एक विशिष्ट संकेत लगा है, जैसे कि "फॉलो करता है" (follows), "रहता है" (lives), या "काम करता है" (works)।
वर्षों तक, इस शहर के टूर गाइडों (पुराने डेटाबेस इंजन) का एक अजीब नियम था: यदि आप उनसे पूछते, "मुझे दिखाओ कि मैं केवल 'फॉलो करता है' वाली सड़कों के माध्यम से जो (Joe) से एफिल टॉवर तक कैसे पहुँच सकता हूँ," तो गाइड बस इशारा करता और कहता, "ठीक है, आप वहाँ पहुँच सकते हैं!" और रुक जाता। वे आपको गंतव्य (destination) तो बता देते, लेकिन वे उस यात्रा का नक्शा (map) नहीं दिखाते थे।
यह जासूसों के लिए एक समस्या है। यदि आप किसी रहस्य को सुलझाने की कोशिश कर रहे हैं (जैसे मनी लॉन्ड्रिंग का पता लगाना या अफवाहों को ट्रैक करना), तो आप केवल यह नहीं जानना चाहते कि कौन किससे जुड़ा है; आपको वह पूरा रास्ता (path) भी देखना होता है जिसे उन्होंने तय किया है। क्या वे सीधे वहाँ पहुँचे? क्या वे तीन बार चक्कर लगाकर आए? क्या उन्होंने कोई छोटा रास्ता लिया?
यहाँ आता है पाथफाइंडर (PathFinder), एक नया, सुपर-स्मार्ट टूर गाइड जिसे बेंजामिन, विम, कार्लोस और डोमागोज द्वारा बनाया गया है। यह पेपर पाथफाइंडर का परिचय देता है, जो पहला ऐसा गाइड है जो न केवल यह बता सकता है कि कौन जुड़ा हुआ है, बल्कि वह आपको हर संभव मार्ग का सटीक नक्शा भी सौंप सकता है, चाहे नियम कितने भी जटिल क्यों न हों।
"प्रोडक्ट ग्राफ" (Product Graph) का जादू
पाथफाइंडर इस भूलभुलैया में बिना खोए यह कैसे करता है? कल्पना कीजिए कि आपके पास शहर का एक नियमित नक्शा है, और आपके पास एक छोटी, जादुई चेकलिस्ट (एक ऑटोमेटन) भी है जो कहती है, "आपको पहले एक 'फॉलो करता है' वाली सड़क लेनी है, फिर एक और 'फॉलो करता है' वाली सड़क, और फिर एक 'काम करता है' वाली सड़क।"
पाथफाइंडर केवल शहर में चलता नहीं है; यह एक छाया शहर (Shadow City) बनाता है (जिसे प्रोडक्ट ग्राफ कहा जाता है) जहाँ हर इमारत एक वास्तविक शहर की इमारत और चेकलिस्ट के एक चरण का संयोजन होती है।
- यदि आप "जो" (Joe) पर हैं और आपने शून्य कदम लिए हैं, तो आप
(Joe, Step 0)पर हैं। - यदि आप "पॉल" (Paul) तक पहुँचने के लिए एक "फॉलो करता है" वाली सड़क लेते हैं, तो आप
(Paul, Step 1)पर पहुँच जाते हैं।
इस छाया शहर में चलकर, पाथफाइंडर तुरंत देख सकता है कि कौन से मार्ग आपकी चेकलिस्ट से मेल खाते हैं। यह एक ऐसे जीपीएस (GPS) की तरह है जो केवल उन्हीं सड़कों को रोशन करता है जिन पर आपको गाड़ी चलाने की अनुमति है, बाकी को अनदेखा कर देता है।
चलने के 27 तरीके
पेपर बताता है कि ग्राफ सिटी में चलने के लिए 27 अलग-अलग नियम (जिन्हें "मोड्स" कहा जाता है) हैं। पाथफाइंडर पहला इंजन है जो इन सभी 27 को संभाल सकता है। यहाँ कुछ उदाहरण दिए गए हैं:
- वॉक (WALK): आप कहीं भी जा सकते हैं, भले ही आप चक्कर काटें या एक ही घर को दो बार देखें। (यह सबसे आसान है, लेकिन इससे अनंत लूप बन सकते!)
- ट्रेल (TRAIL): आप एक ही घर को दो बार देख सकते हैं, लेकिन आप एक ही सड़क पर दो बार नहीं चल सकते।
- सिंपल (SIMPLE): आप एक ही घर को दो बार नहीं देख सकते (जब तक कि आप उसी स्थान से शुरू और समाप्त न करें)। यह नियम का पालन करना सबसे कठिन है क्योंकि संभावित रास्तों की संख्या बहुत अधिक बढ़ सकती है।
- एनी शॉर्टेस्ट (ANY SHORTEST): मुझे बस सबसे तेज़ रास्तों में से एक दे दो।
- ऑल शॉर्टेस्ट (ALL SHORTEST): मुझे सबसे तेज़ वाले प्रत्येक मार्ग को दें।
- शॉर्टेस्ट k ग्रुप्स (SHORTEST k GROUPS): मुझे सबसे तेज़ मार्ग दें, फिर दूसरा-सबसे तेज़ समूह के मार्ग दें, और इसी तरह समूहों तक।
लेखक बताते हैं कि जबकि इनमें से कुछ नियम (जैसे "सिंपल" पथ खोजना) सैद्धांतिक रूप से बहुत कठिन हैं—इतने कठिन कि कंप्यूटर आमतौर पर बड़े मानचित्रों पर हार मान लेते हैं—पाथफाइंडर वास्तविक दुनिया में उन्हें आश्चर्यजनक रूप से अच्छी तरह से संभालता है।
"अनंत लूप" (Infinite Loop) की समस्या
ग्राफ सिटी में एक बड़ी समस्या यह है कि यदि कोई लूप है (जैसे जो पॉल को फॉलो करता है, और पॉल जो को फॉलो करता है), तो आप उस लूप में अनंत काल तक घूम सकते हैं। यदि आप "सभी वॉक" (all walks) मांगते हैं, तो उत्तर अनंत होगा!
इसे ठीक करने के लिए, GQL और SQL/PGQ मानक (इन भाषाओं के नियम) आपको "सिंपल" या "ट्रेल" जैसा मोड चुनने की अनुमति देते हैं ताकि अनंत लיםों को रोका जा सके। पाथफाइंडर इन नियमों का पूरी तरह से सम्मान करता है। वह बिल्कुल जानता है कि पथों की खोज को कब रोकना है ताकि वह अंतहीन चक्र में न फंस जाए, जबकि वह अभी भी आपके द्वारा मांगे गए सभी वैध पथों को खोज रहा है।
स्पीड टेस्ट: पाथफाइंडर बनाम अन्य
लेखकों ने केवल पाथफाइंडर बनाया ही नहीं; उन्होंने इसे उद्योग के बड़े नामों के खिलाफ परखा है: Neo4j, Nebula, Kuzu, Jena, Blazegraph, और Virtuoso।
उन्होंने तीन अलग-अलग परिदृश्यों पर परीक्षण किए:
- पोेक (Pokec): 1.6 मिलियन लोगों और 30 मिलियन कनेक्शन वाला एक मध्यम आकार का सोशल नेटवर्क।
- विकीडाटा (Wikidata): एक विशाल वास्तविक दुनिया का नॉलेज ग्राफ जिसमें 364 मिलियन नोड्स और 1.257 बिलियन एजेस हैं।
- डायमंड (Diamond): एक जटिल, गणितीय रूप से निर्मित ग्राफ जिसे विशेष रूप से पथों की घातांकीय (exponential) संख्या होने के लिए डिज़ाइन किया गया है।
परिणाम:
- गति: पाथफाइंडर लगभग हर परीक्षण में अन्य इंजनों की तुलना में 10 से 100 गुना तेज़ था।
- स्थिरता: जब अन्य इंजन लंबे या अधिक जटिल होने पर क्रैश होने लगे या टाइम आउट (हार मान लेने) लगे, तब भी पाथफाइंडर काम करता रहा।
- "इंट्रैक्टेबल" (Intractable) का आश्चर्य: "सिंपल" और "ट्रेल" मोड्स के लिए, सिद्धांत कहता है कि कंप्यूटर को उत्तर खोजने में बहुत समय लगेगा—इतना समय कि कंप्यूटर हार मान ले—लेकिन वास्तविक दुनिया के परीक्षणों (जैसे विकीडाटा पर) में, पाथफाइंडर ने 100,000 पथ जल्दी से खोज लिए। लेखक सुझाव देते हैं कि ऐसा इसलिए है क्योंकि वास्तविक दुनिया के डेटा में आमतौर पर उन कनेक्शनों का "परफेक्ट स्टॉर्म" नहीं होता जो गणित को विस्फोट करने के लिए मजबूर कर दे।
पाथफाइंडर क्या नहीं करता (अभी तक)
यह जानना महत्वपूर्ण है कि यह पेपर क्या दावा नहीं करता है:
- यह यह दावा नहीं करता कि पाथफाइंडर जादुई है। यदि आप लूप वाले ग्राफ में हर एक पथ मांगते हैं, तो उत्तर अभी भी अनंत है, और कोई भी कंप्यूटर उसे प्रिंट नहीं कर सकता। पाथफाइंडर बस आपके द्वारा निर्धारित सीमा (जैसे 100,000 परिणाम) पर रुक जाता है।
- यह दावा नहीं करता कि इसने सभी संभावित ग्राफों के लिए "सिंपल पाथ" की समस्या को हल कर दिया है। पेपर स्वीकार करता है कि सबसे खराब सैद्धांतिक परिदृश्यों में, एक सरल पथ खोजना अभी भी NP-complete है (एक फैंसी तरीका यह कहने का कि यह "कंप्यूटेशनल रूप से बहुत कठिन" है)। पाथफाइंडर बस वास्तविक दुनिया में उपयोग किए जाने वाले ग्राफों पर बाकी सब से बेहतर काम करता है।
- यह दावा नहीं करता कि इसने RDF (डेटा का एक विशिष्ट प्रकार) के लिए "सिंपल" मोड को ठीक कर दिया है। लेखक कहते हैं कि उन्होंने अभी तक RDF के लिए "ट्रेल" मोड को लागू नहीं किया है क्योंकि यह स्पष्ट नहीं है कि "ट्रेल" को कैसे परिभाषित किया जाए जब किनारों (edges) के पास अद्वितीय नाम न हों।
निष्कर्ष
पाथफाइंडर एक नया इंजन है जो एक सुपर-पावर्ड टूर गाइड की तरह काम करता है। यह नियमों का एक जटिल सेट (जैसे "जो से ENS पेरिस तक के सभी पथ खोजें जो 'फॉलो करता है' फिर 'काम करता है' के पैटर्न का पालन करते हैं") ले सकता है और उन यात्राओं के वास्तविक नक्शे लौटा सकता है।
लेखकों ने वास्तविक डेटा पर इसका मापन किया और पाया कि पाथफाइंडर वर्तमान शीर्ष-स्तरीय ग्राफ डेटाबेस की तुलना में काफी तेज़ और अधिक स्थिर है। उन्होंने यह भी दिखाया है कि इसे मौजूदा सिस्टम (जैसे SPARQL इंजन) में जोड़ा जा सकता है ताकि उन्हें यह नई शक्ति मिल सके। जबकि गणित कहता है कि इनमें से कुछ कार्य तेजी से करना असंभव होना चाहिए, वास्तविक दुनिया की अव्यवस्था में, पाथफाइंडर साबित करता है कि इसे उल्लेखनीय गति के साथ किया जा सकता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।