मैं सोच रहा था कि Google/bing नक्शे जैसे किसी एप्लिकेशन में डेटा संरचना क्या है। दिशानिर्देशों की खोज करते समय परिणाम कितनी जल्दी लौटाए जाते हैं? इस जानकारी को निर्धारित करने के लिए किस प्रकार के एल्गोरिदम का उपयोग किया जा रहा है?Google/bing नक्शे का समर्थन करने के लिए डेटा संरचना
धन्यवाद
मैं सोच रहा था कि कौन सा डेटा संरचना गूगल/बिंग मैप्स की तरह एक आवेदन में है।
उपयोगकर्ता के लिए: एक्सएचटीएमएल/सीएसएस/जावास्क्रिप्ट। किसी भी वेबसाइट की तरह।
सर्वर पर: कौन जानता है? यहां कोई भी Google देवता है? यह निश्चित रूप से PHP या ASP.net ... नहीं है
कैसे यह है कि परिणाम इतनी जल्दी वापस आ रहे हैं जब दिशाओं के लिए खोज है?
क्योंकि Google ने सबसे तेज़ सर्वर प्रतिक्रिया समय प्राप्त करने के लिए आर्किटेक्चर के निर्माण पर वर्षों, जनशक्ति और लाखों डॉलर खर्च किए हैं?
इस जानकारी को निर्धारित करने के लिए किस प्रकार के एल्गोरिदम का उपयोग किया जा रहा है?
मैं आंतरिक डेटा संरचना के बारे में सुनिश्चित नहीं कर रहा हूँ, लेकिन यह 2 डी किसी तरह का समन्वय आधारित वृक्ष संरचना है कि केवल स्तरों की एक निश्चित संख्या को प्रदर्शित करता है हो सकता है। स्तर ज़ूम कारकों के अनुरूप होंगे, इसलिए आप नीचे के महत्वहीन चीजों के रूप में अनदेखा कर सकते हैं, कहें, मौजूदा स्तर से 5 स्तर, और वर्तमान स्तर से ऊपर की चीजें।
यह कैसे संरचित है के बावजूद, यहाँ कैसे आप इसका इस्तेमाल कर सकते हैं:
http://code.google.com/apis/maps/documentation/reference.html
आवेदन की इस तरह के लिए, आप डेटाबेस नक्शा सुविधाओं और उन दोनों के बीच कनेक्शन का प्रतिनिधित्व करने के कुछ प्रकार चाहेगा, और इसके बाद:
1 के लिए, एक उदाहरण R-tree डेटा संरचना होगी।
2 के लिए, आपको ग्राफ खोज एल्गोरिदम की आवश्यकता है, जैसे कि A*।
मैं इसे एक कम्प्यूटेशनल ज्यामिति समस्या के रूप में सोचूंगा। जब आप मानचित्र में किसी विशेष समन्वय पर क्लिक करते हैं और उस जानकारी का उपयोग करते हैं, तो उस स्थान का अक्षांश और देशांतर प्राप्त कर सकते हैं। अक्षांश और देशांतर और ज़ूम के स्तर के आधार पर, स्थान की पहचान की जा सकती है।
एक बार जब आप दो स्थानों की पहचान कर लेंगे, तो आपके लिए एकमात्र समस्या निकटतम मार्ग की पहचान करना है। अब यह समस्या दो बिंदुओं के बीच सबसे छोटा रास्ता ढूंढ रही है, जिसमें उनके बीच बहुभुज ब्लॉक हैं (जो उन जगहों से मेल खाते हैं जिनमें कोई सड़कों नहीं हैं) और केवल संभावित कनेक्शन सड़कों हैं। यह एक ज्ञात समस्या है और इसे हल करने के लिए कुशल एल्गोरिदम मौजूद हैं।
मुझे यकीन नहीं है कि यह Google क्या कर रहा है, लेकिन मुझे आशा है कि वे इन पंक्तियों पर कुछ करें।
मैं इस सेमेस्टर में कम्प्यूटेशनल ज्यामिति ले रहा हूं। पाठ्यक्रम लिंक यहां दिया गया है: http://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html। यदि आप रुचि रखते हैं तो उन्हें जांचें।
Google लेखकों से राजमार्ग आयाम के बारे में एक पेपर देखें। विचार महत्वपूर्ण नोड्स के बीच सबसे कम पथ को प्रीकंप्यूट करना है और फिर उन सभी के माध्यम से सबकुछ रूट करना है। आप एलए से शिकागो जाने के लिए आवासीय सड़कों का उपयोग नहीं करेंगे, दोनों सिरों पर फ्रीवे चालू और बंद करने के लिए।
आपके सवाल का दो भागों हैं:
, मैं एक और सवाल जोड़ना होगा:
मैं प्रत्येक प्रश्न को क्रम में संबोधित करने का प्रयास करूंगा। ध्यान दें, कि मैं Google मानचित्र या बिंग टीम के लिए काम नहीं करता, इसलिए जाहिर है, यह जानकारी पूरी तरह सटीक नहीं हो सकती है। मैं डेटा संरचनाओं और एल्गोरिदम के बारे में एक अच्छा सीएस पाठ्यक्रम से प्राप्त ज्ञान के इस आधार पर आधारित हूं।
उत्तर 1) नक्शा एक एज भारित निर्देशित ग्राफ में संग्रहीत है। मानचित्र पर स्थान वर्टिसेस हैं और एक स्थान से दूसरे स्थान पर पथ (एक कशेरुक से दूसरे तक) एज हैं।
स्पष्ट रूप से, चूंकि लाखों शिखर और परिमाण के किनारों का क्रम हो सकता है, वास्तव में दिलचस्प बात इस एज भारित अंक का प्रतिनिधित्व होगी।
मैं कहूंगा कि यह किसी प्रकार की एडजेंसी सूची द्वारा प्रदर्शित किया जाएगा और कारण मैं ऐसा कहता हूं क्योंकि, यदि आप मानचित्र की कल्पना करते हैं, तो यह अनिवार्य रूप से एक स्पैस ग्राफ है। एक स्थान से दूसरे स्थान पर जाने के कुछ ही तरीके हैं। अपने घर के बारे में सोचो! कितने सड़कों (हमारे मामले में किनारों) इसके लिए नेतृत्व करते हैं? आकस्मिक सूचियां स्पैस ग्राफ का प्रतिनिधित्व करने के लिए अच्छी हैं, और आसन्न मैट्रिक्स घने ग्राफ का प्रतिनिधित्व करने के लिए अच्छा है।
बेशक, भले ही हम मेमोरी में स्पैर ग्राफ का कुशलतापूर्वक प्रतिनिधित्व करने में सक्षम हैं, वर्टिस और एज की बड़ी संख्या के बाद, स्मृति में सब कुछ एक साथ स्टोर करना असंभव होगा। इसलिए, मैं कल्पना करता हूं कि नीचे किसी प्रकार की स्ट्रीमिंग लाइब्रेरी है।
इसके लिए एक समानता बनाने के लिए, यदि आपने कभी भी वर्ल्डक्राफ्ट/सीरिम/जीटीए जैसे ओपन-वर्ल्ड गेम खेला है, तो आप देखेंगे कि एक बड़े हिस्से में, कोई लोडिंग स्क्रीन नहीं है। लेकिन जाहिर है, सब कुछ एक ही समय में स्मृति में फिट करना असंभव है।इस प्रकार क्वाड-पेड़ और फ्रस्टम कल्लिंग एल्गोरिदम के संयोजन का उपयोग करके, ये गेम गतिशील रूप से संसाधन लोड कर सकते हैं (इलाके, sprites, meshes आदि)।
मैं कुछ समान कल्पना करता हूं, लेकिन ग्राफ के लिए। मैंने इस विशेष पहलू में बहुत कुछ नहीं सोचा है, लेकिन एक बहुत ही बुनियादी प्रणाली को पकाए जाने के लिए, कोई मेमोरी डेटाबेस में कल्पना कर सकता है, जिसे वे आवश्यकतानुसार रन-टाइम पर ग्राफ से चरम और किनारों को जोड़ते हैं और हटाते हैं। यह हमें एक और दिलचस्प बिंदु पर लाता है। चूंकि कोने और किनारों को हटाया जाना चाहिए और रन-टाइम पर जोड़ा जाना चाहिए, इसलिए एडजेंसी सूची का क्लासिक कार्यान्वयन इसे काट नहीं देगा।
क्लासिक कार्यान्वयन में, हम केवल एक सरणी के प्रत्येक तत्व में एक सूची (जावा में एक वेक्टर) स्टोर करते हैं: adj []। मैं कल्पना करूंगा, विज्ञापन [] सरणी के स्थान पर एक लिंक्ड सूची और सूची [एज] के स्थान पर एक बाइनरी खोज पेड़। द्विआधारी खोज पेड़ ओ (लॉग एन) सम्मिलन और नोड्स को हटाने की सुविधा प्रदान करेगा। सूची कार्यान्वयन में यह बेहद वांछनीय है, जबकि अतिरिक्त ओ (1) है, हटाने ओ (एन) है और जब आप लाखों किनारों से निपट रहे हैं, तो यह निषिद्ध है।
यहां ध्यान देने योग्य एक अंतिम बिंदु यह है कि जब तक आप वास्तव में नेविगेशन शुरू नहीं करते हैं, वहां "नहीं" ग्राफ होता है। चूंकि लाखों उपयोगकर्ता हो सकते हैं, इसलिए सभी के लिए एक विशाल ग्राफ बनाए रखने के लिए यह समझ में नहीं आता है (यह केवल स्मृति स्थान आवश्यकता के कारण असंभव होगा)। मैं कल्पना करता हूं कि जब आप नेविगेशन प्रक्रिया को स्टेट करते हैं, तो आपके लिए एक ग्राफ बनाया जाता है। जाहिर है, चूंकि आप स्थान ए से शुरू करते हैं और स्थान बी (और उसके बाद संभवतः अन्य स्थानों) पर जाते हैं, तो आपके लिए बनाए गए ग्राफ को बहुत बड़ी मात्रा में स्मृति नहीं लेनी चाहिए (बशर्ते स्ट्रीमिंग आर्किटेक्चर जगह पर हो)।
उत्तर 2) यह एक बहुत ही रोचक सवाल है। इस समस्या को हल करने के लिए सबसे बुनियादी एल्गोरिदम Dijkstra पथ ढूँढना एल्गोरिदम होगा। ए * अस्तित्व में तेज बदलाव। मैं कल्पना करता हूं कि डिजस्ट्रा पर्याप्त तेज़ होगा, अगर यह ऊपर चर्चा की स्ट्रीमिंग आर्किटेक्चर के साथ ठीक से काम कर सकता है। डिजस्ट्रा ई और एलजी वी के अनुपात आनुपातिक स्थान का उपयोग करता है, जो विशेष रूप से स्पैस ग्राफ के लिए बहुत अच्छे आंकड़े हैं। ध्यान रखें, अगर स्ट्रीमिंग आर्किटेक्चर को कम नहीं किया गया है, तो वी और ई विस्फोट हो जाएंगे और डिजस्ट्रा की स्पेस और रन-टाइम आवश्यकताएं इसे निषिद्ध बनाती हैं।
उत्तर 1) स्ट्रीमिंग प्रश्न: ऊपर चर्चा की गई स्ट्रीमिंग आर्किटेक्चर के साथ इस प्रश्न को भ्रमित न करें। यह मूल रूप से पूछ रहा है कि निर्बाध ज़ूम कैसे प्राप्त किया जाता है।
इसे प्राप्त करने के लिए एक अच्छा एल्गोरिदम क्वाड ट्री एल्गोरिदम है (आप इसे एन-पेड़ में सामान्यीकृत कर सकते हैं)। जब आप पेड़ को पार करते हैं तो आप पेड़ और उच्च रिज़ॉल्यूशन छवियों में उच्चतर कोरर्स छवियों को स्टोर करते हैं। यह वास्तव में केएमएल (कीहोल) ने अपने मानचित्रण एल्गोरिदम के साथ किया था। कीहोल एक ऐसी कंपनी थी जिसने कई वर्षों पहले एनवीआईडीआईए के साथ साझेदारी की, सॉफ्टवेयर की तरह पहली "Google धरती" में से एक का उत्पादन किया।
क्वाड ट्री कूलिंग के लिए प्रेरणा आधुनिक 3 डी गेम से आती है, जहां इसका उपयोग उस दृश्य के हिस्सों को तुरंत खींचने के लिए किया जाता है जो दृश्य में नहीं है।
इसे और स्पष्ट करने के लिए, कल्पना करें कि आप संयुक्त राज्य अमेरिका के मानचित्र को वास्तव में ऊपर से देख रहे हैं। इस स्तर पर, आप मूल रूप से मानचित्र को 4 वर्गों में विभाजित करते हैं और प्रत्येक अनुभाग को क्वाड ट्री के बच्चे बनाते हैं।
अब, जैसे ही आप ज़ूम इन करते हैं, आप अनुभागों में से एक पर ज़ूम इन करते हैं (जाहिर है कि आप केंद्र में सही ज़ूम कर सकते हैं, ताकि आपका ज़ूम वास्तव में सभी 4 अनुभागों को छू सके, लेकिन सादगी के लिए, मान लें कि आप ज़ूम इन करते हैं खंडों में से एक पर)। तो जब आप एक सेक्शन में ज़ूम इन करते हैं, तो आप उस सेक्शन के 4 बच्चों को पार करते हैं। इन 4 बच्चों में अपने माता-पिता का उच्च रिज़ॉल्यूशन डेटा होता है। तब तक आप ज़ूम डाउन करना जारी रख सकते हैं जब तक आप पत्तियों का एक सेट हिट न करें, जिसमें उच्चतम रिज़ॉल्यूशन डेटा होता है। एक संकल्प से अगले "निर्बाध" तक कूदने के लिए धुंध और लुप्तप्राय प्रभावों का संयोजन उपयोग किया जा सकता है।
इस पोस्ट के अनुवर्ती के रूप में, मैं यहां दी गई कई अवधारणाओं के लिंक जोड़ने का प्रयास करूंगा।
मुहम्मद: यदि आप कहीं अपना ईमेल पता (एस) जोड़ना चाहते हैं, तो मेरा सुझाव है कि आप इसे अपनी प्रोफ़ाइल में जोड़ें। आपको दो एसओ पहचान भी मिलती हैं, जो आपको और अन्य लोगों को भ्रमित कर देगी। –
जॉन: आप सही हैं, मैंने गलती से दो प्रोफाइल बनाए हैं। मैं दोनों को कैसे जोड़ सकता हूं? मुझे अपने अनियंत्रित प्रोफाइल पर "शिक्षक" बैज मिला: | –
मेरा सुझाव है कि आप अपनी समस्या बताते हुए [email protected] पर एक ईमेल भेजें। –
वाह। उस विकिपीडिया लेख में कई मुद्दे हैं। –