YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Hindi subtitles

← 07-12 Getting To Point B

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. हमारे अगले मेहमान एंड्रयू Goldberg है।
  2. वह Microsoft अनुसंधान, सिलिकॉन वैली में एक प्रमुख शोधकर्ता है,
  3. और अपने काम के असली दुनिया की समस्याओं के लिए एल्गोरिदम बनाने पर केंद्रित है।
  4. एक दिलचस्प समस्या उन्होंने अध्ययन किया है
  5. वास्तव में, में सबसे छोटा रास्ता खोजने के लिए है microseconds, में वास्तव में बड़ा नेटवर्क
  6. तो वह हमें करने के लिए एल्गोरिदम के बारे में थोड़ा बताओ करने के लिए जा रहा है।
  7. [एंड्रयू Goldberg] [प्रमुख शोधकर्ता, माइक्रोसॉफ्ट रिसर्च] मैं हाल ही में किया गया है
  8. बहुत कम से कम पथ एल्गोरिदम पर काम कर रहे,
  9. जीपीएस नेविगेशन अनुप्रयोग द्वारा विशेष रूप से प्रेरित,
  10. तो मूल रूप से A से b. करने के लिए प्राप्त करने के लिए कैसे
  11. यह बढ़िया है.
  12. जब आप इस समस्या का विश्लेषण करते हैं, कि समस्या अपने आप काफी प्रतिष्ठित का अध्ययन किया है।
  13. क्या नया झुर्रियों में यह कि ऊपर आ, और वे क्यों आए हैं?
  14. तो, जब तक नया झुर्रियाँ आया जीपीएस नेविगेशन
  15. बहुत, बहुत ही व्यापक रूप से इस्तेमाल हो गया,
  16. और भी जीपीएस मैप्स महाद्वीप आकार और विस्तृत, डिजिटल बने मानचित्र।
  17. और फिर तुम सच में रेखीय समय बहुत तेजी से समस्या को हल करने के लिए चाहता था।
  18. मूल रूप से जब Bing Maps या Google Maps जाता एक अनुरोध है
  19. यह पूरे मानचित्र को देखने के लिए समय नहीं है,
  20. तो रेखीय समय एल्गोरिदम अपनी शास्त्रीय Dijkstra के एल्गोरिथ्म की तरह बहुत अच्छा नहीं कर रहे हैं,
  21. और नए शिकन preprocessing था,
  22. तो आप सवाल का जवाब करने के लिए सक्षम होना करने के लिए अपने ग्राफ preprocess करना चाहते हैं
  23. यदि आप अपने सिद्धांत टोपी पर डाल करने के लिए चाहते हैं बहुत, बहुत जल्दी, के polylogarithmic समय में सॉर्ट।
  24. पिछले 15 वर्षों के दौरान या तो वहाँ अनुसंधान के एक बहुत कुछ था
  25. दोनों हमारे समूह और कई अन्य स्थानों में भी,
  26. और वहाँ बहुत अच्छा एल्गोरिदम विकसित किया गया है
  27. जो 10 साल पहले मैंने माना है नहीं होता है कि यह संभव है,
  28. लेकिन मूल रूप से इन एल्गोरिदम में microseconds प्रश्नों जवाब कर सकते हैं
  29. कॉनटिनेंटल-आकार नेटवर्क पर।
  30. वाह, और यह सब संभव जोड़ी वार - pre-store नहीं करता
  31. नहीं, तो तुम बड़े पैमाने पर एक विचार दे करने के लिए बस
  32. एक महाद्वीप आकार नेटवर्क नोड्स के लाखों लोगों के दसियों है,
  33. तो 10 अरब चुकता भी आज की बहुत बड़ी डिस्क के लिए बहुत बड़ा है।
  34. कि आप रेखांकन के प्रकार के बीच किसी भी रिश्ते हैं
  35. राजमार्गों और रेखांकन की तरह में कि एक सामाजिक नेटवर्क से बाहर आना होगा?
  36. हम अब सबमिशन के तहत हाल ही में भिन्नता अध्ययन किया था,
  37. और हम सार्वजनिक रूप से उपलब्ध नेटवर्क के कुछ का अध्ययन किया,
  38. और sub-labeling कलन विधि मैं अगला के बारे में बात करना चाहता हूँ
  39. वास्तव में काफी अच्छी तरह से नेटवर्क के इस तरह के लिए काम किया है
  40. तिमाही की तरह नेटवर्क है और इतने पर।
  41. लेकिन उदाहरण के लिए, यह इतनी अच्छी तरह से छोटी सी दुनिया के लिए नेटवर्क की तरह काम नहीं करता।
  42. ठीक है, दिलचस्प है।
  43. सब अच्छा है, इसलिए यदि आप मुझे एल्गोरिथ्म के बारे में एक छोटा सा बता मन नहीं होगा ठीक है,
  44. मुझे लगता है कि वास्तव में दिलचस्प होगा।
  45. चलो बस दूरी oracle को लागू करने के बारे में बात करते हैं,
  46. तो मूल रूप से दी 2 अंक, तुम बताओ कि उन 2 अंकों के बीच की दूरी के लिए चाहते हैं।
  47. एल्गोरिथ्म पहली बार ग्राफ preprocesses,
  48. और के लिए प्रत्येक शीर्ष यह लेबल गणना करता है,
  49. और चलो अनिर्दिष्ट ग्राफ़ है सादगी के लिए कहते हैं।
  50. तब कोई शिरोबिंदु के लेबल वर्टेक्स का एक सेट है
  51. जो हम केन्द्र और दूरी के लिए केन्द्र से शिरोबिंदु कहते हैं।
  52. प्रत्येक वर्टेक्स एक लेबल है, और इन लेबल निम्न गुण होना आवश्यक है।
  53. अगर आप किसी भी 2 वर्टेक्स ले, केन्द्रों की स्थापना की एक दूसरे को काटना है,
  54. और उन दोनों के बीच सबसे छोटा रास्ता पर कोई शिरोबिंदु चौराहे के निशान होते हैं।
  55. और क्यों यह महत्वपूर्ण है कि के लिए यह शीर्ष है
  56. यदि आप 2 हब, जो आपके पास है, के लिए दूरी संक्षेप
  57. आप पथ दूरी कम से कम हो जाएगा।
  58. योग ताकि सभी केन्द्र दूरी कम से कम पथ संग्रहीत है परिणाम, के?
  59. नहीं, के लिए प्रत्येक शीर्ष तुम केन्द्रों का एक सेट है।
  60. यह उपगम्यता से दूर एक हब के लिए।
  61. [पुरुष] ओह, मैं देख रहा हूँ, और वे एक हब का हिस्सा है।
  62. कम से कम पथ पर।
  63. जो भी मैं देख रहा हूँ कम से कम पथ पर, है।
  64. ठीक है, तो यह एक काफी मजबूत, संपत्ति, तो सबसे आसान तरीका
  65. यह करने के लिए आप कहते हैं, ठीक है, के लिए प्रत्येक शीर्ष है
  66. अन्य सभी वर्टेक्स केन्द्रों पर कर रहे हैं।
  67. [पुरुष] तो आप की गारंटी रहे हैं।
  68. और तब गुण रखती है, लेकिन फिर एक समय में अपने कतार n का क्रम है,
  69. और क्या तुम सच में चाहते हैं छोटे लेबल है,
  70. और यह पता चला है कि कुछ रेखांकन और अधिक लेबल है,
  71. और कारण है क्यों यह सड़क नेटवर्क में अच्छी तरह से काम करता है
  72. है कि हम लेबल गणना कर सकते हैं
  73. कहते हैं, ग्राफ पश्चिमी यूरोप के लिए, लगभग 18 लाख वर्टेक्स के साथ।
  74. हम लेबल आकार लगभग 70 की गणना कर सकते हैं।
  75. 70, 7-0. >> [एंड्रयू Goldberg] हाँ।
  76. कितने लाख से बाहर तुम कहा था? 16 लाख?
  77. 18. >> [पुरुष] 18 लाख।
  78. आप केवल 70 की जरूरत है।
  79. यह बहुत, बहुत तेजी से है।
  80. यदि आपको लगता है कि के बारे में अगर आप इन केन्द्रों नोड ID द्वारा सॉर्ट करें
  81. हम 2 arrays है, और तुम सिर्फ इन 2 arrays आकार 70 के दो टुकड़े करने के लिए की जरूरत है,
  82. जो आप कर सकते हैं एक मर्ज सॉर्ट करें कि है बहुत ही अच्छे इलाके की तरह।
  83. इस समय एक microsecond नीचे हो जाता है।
  84. यह है बहुत, बहुत, तेजी से।
  85. लेकिन यह मुझे तो क्या 70 - हैं एक बहुत ही सहज ज्ञान युक्त अवधारणा नहीं है
  86. तो हम के बारे में यूरोप, सही में अलग-अलग चौराहों की तरह बात कर रहे हैं?
  87. इस Piccadilly वर्ग या कुछ और की तरह की तरह है कि है
  88. या Piccadilly स्क्वायर के पूर्वोत्तर कोने,
  89. और आप केवल वहाँ से पता करने की आवश्यकता
  90. दूरी 70 यूरोप में अन्य स्थानों के लिए।
  91. यह कमाल की बात है, और इसलिए लोगों को विचार
  92. कि यह व्यावहारिक नहीं होगा क्योंकि
  93. यदि आप इसके बारे में लगता है कि शायद कर रहे हैं हजारों,
  94. लेकिन आश्चर्यजनक बात यह है कि आप केवल एक बहुत छोटी संख्या की आवश्यकता थी,
  95. तो अगर आप इस समय सीमा के बारे में, लगता है कि
  96. यह मूल रूप से प्रमुख राजमार्गों के चौराहों है,
  97. और वहाँ नहीं है कि कई उन लोगों के, और की तरह स्थानीय स्तर पर
  98. यह के चौराहों के राज्य राजमार्गों और अधिक स्थानीय रूप से
  99. यह प्रमुख सड़कों के चौराहों के है।
  100. कलन विधि की इस तरह की बुरी रेखांकन ग्रिड हैं,
  101. लेकिन सौभाग्य से वहाँ नक्शे में कोई बड़ी ग्रिड हैं,
  102. और फिर भी कर रहे हैं मैनहट्टन में ग्रिड की तरह
  103. यह केवल 10 रास्ते चौड़ा है, है तो यह बहुत बड़ा नहीं है,
  104. और ब्रॉडवे, जो संतुलन टूट जाता है,
  105. इतनी बातें बुरा के रूप में के रूप में एक लगता है कि हो सकता है नहीं कर रहे हैं।
  106. यह आकर्षक है।
  107. 70 स्थानों की, मैं कल्पना कर सकते हैं कि उनमें से कुछ अंश हैं
  108. सच में लम्बी दूरी की यात्रा के लिए, देशों के बीच की तरह,
  109. और उनमें से कुछ अन्य अंश देश के भीतर के लिए हैं
  110. लेकिन दूर दूर है, और उनमें से फिर एक और अंश
  111. के लिए देश के क्षेत्र के भीतर कर रहे हैं, और यह की तरह समान बाल्टी है प्रत्येक के लिए,
  112. या वास्तव में दूर दूर के लिए आप केवल एक छोटी संख्या की आवश्यकता है, लेकिन स्थानीय के लिए आप की जरूरत है और अधिक?
  113. वितरण की तरह क्या है?
  114. आप पैमाने पर तेजी से वृद्धि के रूप में यह लगभग एक समान है।
  115. [पुरुष] वाह, वाह।
  116. कि वास्तव में जहां देश में आप हैं पर निर्भर करता है
  117. क्योंकि उस घनी आबादी वाले क्षेत्र में आप और अधिक स्थानीय चीजों की जरूरत है।
  118. अगर तुम कहीं नहीं के बीच में हैं-
  119. [पुरुष] वहाँ बाहर एक ही रास्ता है।