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