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

सबसे पहले, हम औपचारिक रूप से समस्या को परिभाषित करते हैं:

प्रश्नों के निश्चित सेट को देखते हुए $$$क्यू$ आने वाला अनुरोध $$$q$ और पूर्णांक $$$k$ । इस तरह के प्रश्नों का एक सबसेट खोजने की जरूरत है $$$R = \ left \ {q0, q1, ..., qk \ right \} \ subset Q$ प्रत्येक अनुरोध के लिए $$$q_ {i} \ R $ मे$ अधिक पसंद था $$$q$ में किसी भी अन्य अनुरोध की तुलना में $$$Q ∖ R$ ।

उदाहरण के लिए, प्रश्नों के इस सेट के साथ $$$क्यू$ :

{tesla cybertruck, beginner bicycle gear, eggplant dishes, tesla new car, how expensive is cybertruck, vegetarian food, shimano 105 vs ultegra, building a carbon bike, zucchini recipes} 

और $$$k = 3$ आप इस परिणाम की उम्मीद कर सकते हैं:


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

शब्दों का सदिश प्रतिनिधित्व

शब्दों का वेक्टर प्रतिनिधित्व एक मशीन लर्निंग तकनीक है जिसका उपयोग प्राकृतिक भाषा प्रसंस्करण में पाठ या शब्दों को वैक्टर में बदलने के लिए किया जाता है। वेक्टर स्पेस में कार्य को आगे बढ़ाते हुए, हम वैक्टर के साथ गणितीय संचालन का उपयोग कर सकते हैं - दूरी की गणना और गणना। समान शब्दों के बीच लिंक स्थापित करने के लिए, आप वेक्टर क्लस्टरिंग के पारंपरिक तरीकों का उपयोग कर सकते हैं। मूल शब्द अंतरिक्ष में इन ऑपरेशनों का अर्थ स्पष्ट नहीं हो सकता है, लेकिन इसका फायदा यह है कि अब हमारे पास कई प्रकार के गणितीय उपकरण हैं। यदि आप शब्द वैक्टर और उनके आवेदन के बारे में विवरण में रुचि रखते हैं, तो word2vec और GloVe के बारे में पढ़ें।

हमारे पास शब्दों से वैक्टर उत्पन्न करने का एक तरीका है, अब हम उन्हें पाठ वैक्टर (दस्तावेजों या अभिव्यक्तियों के वैक्टर) में इकट्ठा करते हैं। ऐसा करने का सबसे आसान तरीका पाठ में सभी शब्दों के वैक्टर को जोड़ना (या औसत) है।


^{चित्र 1: क्वेरी क्षेत्र।}

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

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

अनुमानित निकटतम पड़ोसी खोज

अब हम अपनी मूल क्वेरी मिलान समस्या को परिष्कृत कर सकते हैं:

क्वेरी वैक्टर के एक निश्चित सेट को देखते हुए $$$क्यू$ आने वाले वेक्टर $$$q$ और पूर्णांक $$$k$ । आपको वैक्टर के ऐसे सबसेट को खोजना होगा $$$R = \ left \ {q0, q1, ..., qk \ right \} \ subset Q$ ताकि कोणीय दूरी से $$$q$ प्रत्येक वेक्टर के लिए $$$q_ {i} \ R $ मे$ में किसी भी अन्य वेक्टर की दूरी से कम था $$$Q ∖ R$ ।

इसे निकटतम पड़ोसी को खोजने का कार्य कहा जाता है। कम-आयामी स्थानों में इसके त्वरित समाधान के लिए कई एल्गोरिदम हैं । लेकिन जब शब्दों के वेक्टर प्रतिनिधित्व के साथ काम करते हैं, तो हम आमतौर पर उच्च-आयामी वैक्टर (100-1000 आयाम) के साथ काम करते हैं। और यहां बताए गए तरीके अब काम नहीं करते हैं।

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

पदानुक्रमित छोटी दुनिया

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


^{चित्र 2: बहुस्तरीय निकटता ग्राफ।}
HNSW में निकटतम पड़ोसियों को खोजने के लिए जूमिंग-इन विधि का उपयोग किया जाता है। यह उच्चतम स्तर के इनपुट नोड में शुरू होता है और प्रत्येक स्तर पर लालची ग्राफ ट्रैवर्सल को पुन: प्रदर्शित करता है जब तक कि यह एक स्थानीय न्यूनतम तक नहीं पहुंचता।

एल्गोरिथ्म और खोज तकनीक के बारे में विवरण वैज्ञानिक कार्यों में अच्छी तरह से वर्णित हैं। यह याद रखना महत्वपूर्ण है कि निकटतम पड़ोसियों के लिए प्रत्येक खोज चक्र में वैक्टर के बीच की दूरी की गणना के साथ रेखांकन के नोड्स का पता लगाना शामिल है। हम बड़े पैमाने पर सूचकांक बनाने के लिए इस पद्धति का उपयोग करने के लिए इन चरणों को देखेंगे।

अरबों प्रश्नों को अनुक्रमित करने की कठिनाई

मान लें कि हमें 4 बिलियन 200-आयामी क्वेरी वैक्टर को अनुक्रमित करने की आवश्यकता है, प्रत्येक आयाम के साथ एक चार-बाइट फ़्लोटिंग-पॉइंट संख्या द्वारा दर्शाया गया है (कार्य को रोचक बनाने के लिए 4 बिलियन पर्याप्त है, लेकिन आप नोड आईडी को नियमित चार-बाइट संख्या में संग्रहीत कर सकते हैं) । एक मोटा गणना हमें बताता है कि अकेले वैक्टर का आकार लगभग 3 टीबी होगा। चूंकि अधिकांश मौजूदा लाइब्रेरी निकटतम पड़ोसियों की अनुमानित खोज के लिए रैम क्षमता का उपयोग करते हैं, इसलिए हमें रैम में कम से कम वैक्टर को पुश करने के लिए एक बहुत बड़े सर्वर की आवश्यकता होगी। कृपया ध्यान दें कि यह अतिरिक्त खोज सूचकांक को ध्यान में नहीं रखता है, जो कि अधिकांश तरीकों के लिए आवश्यक है।

हमारे खोज इंजन के विकास के पूरे इतिहास में, हमने इस समस्या को हल करने के लिए कई अलग-अलग तरीकों का उपयोग किया है। आइए उनमें से कुछ पर विचार करें।

डेटा की सबसेट

पहला और सबसे सरल दृष्टिकोण, जिसने हमें समस्या को पूरी तरह से हल करने की अनुमति नहीं दी थी, सूचकांक में वैक्टर की संख्या को सीमित करना था। डेटा का दसवां हिस्सा लेते हुए, हमने एक इंडेक्स बनाया, जिसकी आवश्यकता है - आश्चर्य - 10% मेमोरी। हालाँकि, खोज की गुणवत्ता बिगड़ गई है, क्योंकि अब हमने कम प्रश्नों के साथ काम किया है।

परिमाणीकरण

यहां हमने सभी डेटा का उपयोग किया, लेकिन उन्हें परिमाणीकरण का उपयोग करके कम कर दिया (हमने विभिन्न मात्राकरण तकनीकों का उपयोग किया, उदाहरण के लिए, उत्पाद मात्रा का ठहराव, लेकिन डेटा की इतनी मात्रा के साथ काम की वांछित गुणवत्ता प्राप्त नहीं कर सका)। कुछ त्रुटियों को राउंड करके, हम मूल वैक्टर में सभी चार-बाइट संख्याओं को प्रतिस्थापित करने में सक्षम थे, जो कि एकल-बाइट संस्करणों के साथ थे। वैक्टर के लिए रैम की मात्रा में 75% की कमी आई है। हालांकि, हमें अभी भी 750 जीबी मेमोरी (इंडेक्स के आकार को खुद ही गिनना नहीं) की जरूरत थी, और यह अभी भी एक बहुत बड़ा सर्वर है।

ग्रैन के साथ स्मृति समस्याओं का समाधान

वर्णित दृष्टिकोणों के अपने फायदे थे, लेकिन उन्हें बहुत सारे संसाधनों की आवश्यकता थी और खराब गुणवत्ता की खोज की। हालाँकि , ऐसे पुस्तकालय हैं जो 1 एमएस से कम समय में जवाब देते हैं, हम कम हार्डवेयर आवश्यकताओं के बदले में गति का त्याग कर सकते हैं।

ग्रैन (ग्राफ-आधारित नज़दीकी निकटतम पड़ोसियों) एक एचएनएसडब्ल्यू पुस्तकालय है जिसे क्लिक्ज़ द्वारा इस तरह के प्रश्नों की खोज के लिए विकसित और उपयोग किया जाता है। इसमें ओपन सोर्स कोड है, लेकिन लाइब्रेरी अभी भी सक्रिय विकास के अधीन है। एक बेहतर संस्करण 2020 में crates.io पर प्रकाशित किया जाएगा। यह रस्ट में पायथन आवेषण के साथ लिखा गया है, जिसे प्रतिस्पर्धा का उपयोग करके अरबों वैक्टर को संभालने के लिए डिज़ाइन किया गया है। क्वेरी वैक्टर के दृष्टिकोण से, यह दिलचस्प है कि ग्रैन के पास एक विशेष मोड है जिसमें अन्य पुस्तकालयों की तुलना में बहुत कम मेमोरी की आवश्यकता होती है।

क्वेरी वैक्टर का कॉम्पैक्ट प्रतिनिधित्व

क्वेरी वैक्टर के आकार को कम करने से हमें कई लाभ मिलेंगे। ऐसा करने के लिए, चलो वापस जाते हैं और वैक्टर बनाने पर विचार करते हैं। चूंकि प्रश्न शब्दों से बने होते हैं, और क्वेरी वैक्टर शब्द वैक्टर के रूप में होते हैं, इसलिए हम क्वेरी वैक्टर को संग्रहीत करने से स्पष्ट रूप से मना कर सकते हैं और उन्हें आवश्यक रूप से गणना कर सकते हैं।

आप वर्ड सेट के रूप में प्रश्नों को स्टोर कर सकते हैं और संबंधित वैक्टर को खोजने के लिए लुकअप टेबल का उपयोग कर सकते हैं। हालाँकि, हम क्वेरी में शब्द वैक्टर के अनुरूप पूर्णांक आईडी की सूची के रूप में प्रत्येक क्वेरी को संग्रहीत करके पुनर्निर्देशन से बचते हैं। उदाहरण के लिए, क्वेरी को "म्यूनिख के सर्वश्रेष्ठ रेस्तरां" के रूप में सहेजें $$$[{i_ {सर्वोत्तम}}, {i_ {रेस्तरां}}, {i_ {का}}, {i_ {munich}}]$ जहाँ $$${i_ {सर्वोत्तम}}$ - यह "सर्वश्रेष्ठ" शब्द की वेक्टर आईडी है, मान लीजिए कि हमारे पास 16 मिलियन से कम शब्द वैक्टर हैं (इससे अधिक प्रति शब्द 1 बाइट खर्च होंगे), तो आप सभी शब्द आईडी का प्रतिनिधित्व करने के लिए 3 बाइट्स का उपयोग कर सकते हैं। अर्थात्, 800 बाइट्स (या मात्रा वाले वैक्टर के मामले में 200 बाइट्स) को संग्रहीत करने के बजाय, हम केवल 12 बाइट्स इस अनुरोध के लिए संग्रहीत करेंगे (यह पूरी तरह से सत्य नहीं है। चूँकि अनुरोधों में शब्दों की एक अलग संख्या शामिल है, हमें सूची इंडेक्स शब्द सूची में संग्रहीत करने की आवश्यकता है।) इसके लिए प्रति अनुरोध 5 बाइट की आवश्यकता होगी)।

वैक्टर शब्द के लिए, हम सभी को उनकी आवश्यकता है। हालाँकि, शब्दों की संख्या इन शब्दों के संयोजन द्वारा बनाई जा सकने वाली प्रश्नों की संख्या से बहुत कम है। और इसका मतलब है कि शब्दों का आकार इतना महत्वपूर्ण नहीं है। यदि आप एक साधारण सरणी में शब्द वैक्टर को चार-बाइट फ्लोटिंग पॉइंट संस्करणों के रूप में संग्रहीत करते हैं $$$वी$ , तो हमें हर मिलियन शब्दों के लिए 1 जीबी से कम की आवश्यकता है। यह वॉल्यूम आसानी से रैम में फिट हो सकता है। अब क्वेरी वेक्टर इस तरह दिखता है: $$${v _ {{i_ {सर्वोत्तम}}} + {v _ {{i_ {रेस्तरां}}} + {v _ {{i_ {का}}}} + {v _ {{i_ {munich}}}}$ ।

क्वेरी सबमिशन का अंतिम आकार क्वेरी में कुल शब्दों पर निर्भर करता है। 4 बिलियन प्रश्नों के लिए, यह लगभग 80 जीबी (शब्द वेक्टर सहित) है। दूसरे शब्दों में, मूल शब्द वैक्टर के साथ तुलना में, आकार में 97% की कमी आई, और परिमाणित वैक्टर के साथ तुलना में - 90% तक।

और एक बात। एक खोज के लिए, हमें ग्राफ़ के लगभग 200-300 नोड्स पर जाने की आवश्यकता है। प्रत्येक नोड में 20-30 पड़ोसी हैं। इसलिए, हमें इंडेक्स में इनपुट क्वेरी वेक्टर से 4000-9000 वैक्टर की दूरी की गणना करने की आवश्यकता है। और क्या अधिक है, हमें वैक्टर उत्पन्न करने की आवश्यकता है। मक्खी पर क्वेरी वैक्टर बनाने में कितना समय लगता है?

यह पता चला है कि एक नए प्रोसेसर के साथ यह समस्या कुछ मिलीसेकंड में हल हो सकती है। एक अनुरोध जो 1 एमएस में चलता था, अब लगभग 5 एमएस में चलता है। लेकिन फिर हमने वैक्टर के लिए मेमोरी की मात्रा 90% तक कम कर दी। हमने ऐसे समझौते को सहर्ष स्वीकार कर लिया।

वैक्टर और सूचकांक की स्मृति में प्रदर्शित करें

ऊपर, हमने वैक्टर के लिए मेमोरी की मात्रा कम करने की समस्या को हल किया। लेकिन हमने इस समस्या को हल करने के बाद, सूचकांक संरचना ही एक सीमित कारक बन गई। अब आपको इसके आकार को कम करने की आवश्यकता है।

ग्रैन में, ग्राफ संरचना को प्रत्येक नोड के लिए पड़ोसियों की एक चर संख्या के साथ एक आसन्न सूची के रूप में कॉम्पैक्ट रूप से संग्रहीत किया जाता है। अर्थात्, मेटाडेटा पर स्मृति को शायद ही बर्बाद किया जाता है। सूचकांक संरचना का आकार काफी हद तक डिजाइन मापदंडों और ग्राफ गुणों पर निर्भर करता है। फिर भी, सूचकांक के आकार का अंदाजा लगाने के लिए, यह कहना पर्याप्त है कि हम लगभग 240 जीबी के कुल आकार के साथ 4 बिलियन वैक्टर के लिए एक सूचकांक बना सकते हैं। यह एक बड़े सर्वर पर इन-मेमोरी उपयोग के लिए स्वीकार्य हो सकता है, लेकिन बेहतर किया जा सकता है।


^{चित्र 3: रैम और एसएसडी में दो अलग-अलग लेआउट।}

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

डेटा इलाके में सुधार

हमारे वर्तमान कॉन्फ़िगरेशन में, जब सूचकांक एक एसएसडी पर होता है, तो प्रत्येक अनुरोध पर डिस्क से 200-300 तक की आवश्यकता होती है। आप उन तत्वों की व्यवस्था करके डेटा की स्थानीयता को बढ़ाने का प्रयास कर सकते हैं जिनके वेक्टर इतने करीब हैं कि उनके HNSW नोड्स सूचकांक में स्थित हैं, एक दूसरे से बहुत दूर नहीं हैं। डेटा स्थानीयता प्रदर्शन में सुधार करती है, क्योंकि एक एकल रीड ऑपरेशन (आमतौर पर 4 केबी से निकाला जाता है) में ग्राफ को पार करने के लिए आवश्यक अन्य नोड्स शामिल होने की अधिक संभावना है। और यह, बदले में, प्रति खोज में डेटा पुनर्प्राप्ति की संख्या को कम करता है।


^{चित्र 4: डेटा स्थानीयता सूचना पुनर्प्राप्ति को कम करती है।}

यह ध्यान दिया जाना चाहिए कि reordering तत्वों खोज परिणामों को प्रभावित नहीं करता है, यह इसे गति देने का एक तरीका है। यही है, आदेश कोई भी हो सकता है, लेकिन हर विकल्प खोज को गति नहीं देगा। इष्टतम आदेश खोजना बहुत मुश्किल है। हालाँकि, जिस उत्तराधिकार का हमने सफलतापूर्वक उपयोग किया है, वह प्रत्येक प्रश्न में सबसे महत्वपूर्ण शब्द द्वारा प्रश्नों को क्रमबद्ध करना है।

निष्कर्ष

हम अपेक्षाकृत कम मेमोरी खपत वाले समान प्रश्नों की खोज करने के लिए क्वेरी वैक्टर के साथ मल्टीबिलियन-डॉलर इंडेक्स बनाने और बनाए रखने के लिए ग्रैन का उपयोग करते हैं। नीचे दी गई तालिका विभिन्न तरीकों के लिए आवश्यकताओं को दर्शाती है। खोज के दौरान देरी के पूर्ण मूल्यों के बारे में उलझन में रहें, क्योंकि वे दृढ़ता से इस बात पर निर्भर करते हैं कि क्या स्वीकार्य प्रतिक्रिया माना जाता है। हालांकि, यह जानकारी विधियों के सापेक्ष प्रदर्शन का वर्णन करती है।


* आवश्यक मात्रा से बड़ा मेमोरी इंडेक्स आवंटित करने से कुछ नोड्स (अक्सर विज़िट किए गए) का कैशिंग हो जाता है, जिससे खोज में देरी कम हो जाती है। इसके लिए कोई आंतरिक कैश का उपयोग नहीं किया गया था, केवल आंतरिक ओएस उपकरण (लिनक्स कर्नेल)।

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