हायरार्किकल नेविगेबल स्मॉल वर्ल्ड (HNSW) अनुमानित निकटतम पड़ोसी खोज के लिए एक एल्गोरिदम है। इसका उपयोग किसी बड़े संग्रह में क्वेरी आइटम के समान आइटम खोजने के लिए किया जाता है, बिना क्वेरी की तुलना हर आइटम से एक-एक करके किए। यह एल्गोरिदम आमतौर पर वेक्टर डेटा खोजने के लिए उपयोग किया जाता है, जहां दस्तावेज़, चित्र, गाने, या उपयोगकर्ता प्रोफ़ाइल जैसे आइटम को वेक्टर नामक संख्याओं की सूची के रूप में दर्शाया जाता है। समान वेक्टर वाले आइटम को उस मॉडल के अनुसार समान माना जाता है जिसने वेक्टर उत्पन्न किए हैं, और HNSW इन वेक्टरों को जल्दी से खोजने का एक तरीका प्रदान करता है, विशेष रूप से बड़े डेटासेट में।
HNSW वेक्टरों को एक ग्राफ में संग्रहीत करता है। प्रत्येक वेक्टर एक नोड है, और लिंक इसे कुछ निकटवर्ती वेक्टरों से जोड़ते हैं। ग्राफ में कई परतें होती हैं: ऊपरी परतों में कम नोड होते हैं और वे एक मोटे नक्शे की तरह कार्य करती हैं, जबकि निचली परत में सभी नोड होते हैं और अधिक विस्तृत दृश्य देती है। एक खोज ऊपरी परत में शुरू होती है, क्वेरी के करीब नोड्स की ओर लिंक का अनुसरण करती है, और फिर निचली परतों में प्रक्रिया को दोहराती है जब तक कि यह संभावित निकटतम पड़ोसियों का एक सेट नहीं ढूंढ लेती।
पृष्ठभूमि
निकटतम पड़ोसी खोज समस्या पूछती है कि किसी डेटासेट में कौन से आइटम क्वेरी आइटम के सबसे करीब हैं। एक सीधी खोज क्वेरी की तुलना डेटासेट के हर आइटम से कर सकती है, लेकिन यह तब धीमी हो जाती है जब डेटासेट बड़ा होता है। स्थानिक पेड़ों पर आधारित सटीक खोज विधियाँ, जैसे कि k-d पेड़ और R-पेड़, उच्च-आयामी डेटा के लिए भी कम प्रभावी हो सकती हैं, यह समस्या अक्सर आयामीता के अभिशाप से जुड़ी होती है।
अनुमानित निकटतम पड़ोसी विधियाँ गति या कम संसाधन उपयोग के लिए कुछ सटीकता का त्याग करती हैं। हमेशा सटीक निकटतम आइटम की गारंटी देने के बजाय, वे जल्दी से करीबी आइटम लौटाने की कोशिश करती हैं। अन्य अनुमानित विधियों में स्थानीयता-संवेदनशील हैशिंग और उत्पाद क्वांटीकरण शामिल हैं।
HNSW छोटे-विश्व नेटवर्क और नेविगेबल ग्राफ़ पर शोध पर आधारित है। एक छोटे-विश्व ग्राफ में, अधिकांश नोड्स को अन्य नोड्स से लिंक की एक छोटी श्रृंखला के माध्यम से पहुँचा जा सकता है। एक नेविगेबल ग्राफ में, एक खोज प्रक्रिया लक्ष्य की ओर बढ़ने के लिए स्थानीय जानकारी का उपयोग कर सकती है। जॉन क्लेनबर्ग का छोटे-विश्व नेटवर्क में नेविगेशन पर काम इस शोध क्षेत्र का एक महत्वपूर्ण उदाहरण है। बाद के काम ने ऐसे लिंक जोड़ने के तरीकों का अध्ययन किया जो ग्राफ़ को लालची ढंग से नेविगेट करना आसान बनाते हैं।
HNSW एल्गोरिदम समानता खोज के लिए पहले के नेविगेबल छोटे विश्व तरीकों को ग्राफ़ परतों का एक पदानुक्रम जोड़कर विस्तारित करता है। यह पदानुक्रम एल्गोरिदम को निचली परत में अधिक विस्तृत खोज करने से पहले ग्राफ़ का एक अच्छा क्षेत्र खोजने में मदद करता है।
एल्गोरिदम
HNSW एक निकटता ग्राफ पर आधारित है। इस ग्राफ में, निकटवर्ती वेक्टर किनारों से जुड़े होते हैं। एल्गोरिदम हर वेक्टर को स्कैन करने के बजाय डेटासेट के माध्यम से आगे बढ़ने के लिए इन किनारों का उपयोग करता है।
ग्राफ पदानुक्रमित है। हर वेक्टर निचली परत में दिखाई देता है। कुछ वेक्टर उच्च परतों में भी रखे जाते हैं, परतों के ऊपर जाने पर कम वेक्टर दिखाई देते हैं। ऊपरी परतें डेटासेट में लंबी दूरी की गति की अनुमति देती हैं, जबकि निचली परतें आशाजनक उम्मीदवारों के पास अधिक विस्तृत खोज की अनुमति देती हैं।
एक विशिष्ट खोज निम्नानुसार आगे बढ़ती है:
- खोज उच्चतम परत में एक प्रवेश बिंदु से शुरू होती है।
- प्रत्येक चरण में, एल्गोरिदम पड़ोसी नोड्स को देखता है और एक पड़ोसी की ओर बढ़ता है जो क्वेरी के करीब है।
- जब यह उस परत में एक करीबी पड़ोसी नहीं ढूंढ पाता है, तो यह अगली परत में नीचे चला जाता है।
- निचली परत में, यह उम्मीदवार नोड्स के एक व्यापक सेट की खोज करता है और मिले निकटतम उम्मीदवारों को लौटाता है।
इस खोज रणनीति को अक्सर लालची नेविगेशन के रूप में वर्णित किया जाता है। एल्गोरिदम बार-बार स्थानीय रूप से बेहतर नोड्स चुनता है, क्वेरी बिंदु तक पहुंचने के लिए ग्राफ संरचना का उपयोग करता है।
निर्माण और पैरामीटर
HNSW ग्राफ वृद्धिशील रूप से बनाया गया है। जब एक नया वेक्टर डाला जाता है, तो एल्गोरिदम इसे एक अधिकतम परत निर्दिष्ट करता है, निकटवर्ती मौजूदा नोड्स की खोज करता है, और नए नोड को प्रत्येक परत में चयनित पड़ोसियों से जोड़ता है जहां यह दिखाई देता है।
कार्यान्वयन आमतौर पर पैरामीटर उजागर करते हैं जो गति, सटीकता, मेमोरी उपयोग और निर्माण समय के बीच व्यापार-बंद को नियंत्रित करते हैं। ग्राफ कनेक्शन की उच्च संख्या रिकॉल में सुधार कर सकती है लेकिन अधिक मेमोरी की आवश्यकता होती है। एक बड़ी खोज उम्मीदवार सूची सटीकता में सुधार कर सकती है लेकिन क्वेरी को धीमा बनाती है। एक बड़ी निर्माण उम्मीदवार सूची ग्राफ की गुणवत्ता में सुधार कर सकती है लेकिन इंडेक्स निर्माण को धीमा बनाती है।
क्योंकि HNSW अनुमानित है, इसके परिणाम हमेशा पूर्ण सटीक खोज के समान नहीं होते हैं। इसका व्यावहारिक प्रदर्शन डेटासेट, दूरी माप, कार्यान्वयन और पैरामीटर सेटिंग्स पर निर्भर करता है। बेंचमार्किंग अध्ययनों ने पाया है कि HNSW-आधारित लाइब्रेरी अनुमानित निकटतम पड़ोसी विधियों के बीच मजबूत प्रदर्शन करती हैं, हालांकि सबसे खराब स्थिति का प्रदर्शन सामान्य बेंचमार्क डेटासेट पर प्रदर्शन से भिन्न हो सकता है।
वेक्टर खोज प्रणालियों में उपयोग
HNSW का उपयोग उन प्रणालियों में एक इंडेक्स के रूप में किया जाता है जो उच्च-आयामी वेक्टर संग्रहीत और खोजते हैं। इन प्रणालियों में वेक्टर डेटाबेस, खोज इंजन और डेटाबेस एक्सटेंशन शामिल हैं। विशिष्ट उपयोगों में सिमेंटिक खोज, अनुशंसा प्रणाली, छवि समानता खोज, और पुनर्प्राप्ति-संवर्धित जनरेशन शामिल हैं, जो अक्सर जनरेटिव एआई और बड़े भाषा मॉडल पाइपलाइनों में लागू होते हैं।
कई सॉफ्टवेयर प्रोजेक्ट HNSW को लागू या समर्थन करते हैं। लाइब्रेरी में hnswlib शामिल है, जो मूल HNSW लेखकों से जुड़ा है, और FAISS। डेटाबेस और खोज प्रणालियाँ जो HNSW समर्थन का दस्तावेजीकरण करती हैं, उनमें Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant, और Redis शामिल हैं। ये उपकरण आमतौर पर अमेज़न वेब सर्विसेज, माइक्रोसॉफ्ट एज़्योर, और गूगल क्लाउड जैसे क्लाउड प्लेटफार्मों पर उत्पादन मशीन लर्निंग कार्यभार के लिए तैनात किए जाते हैं।
यह भी देखें
- अनुमानित निकटतम पड़ोसी खोज
- वेक्टर डेटाबेस
- स्थानीयता-संवेदनशील हैशिंग
- उत्पाद क्वांटीकरण