approximate nearest neighbor search कैसे काम करता है, और रफ्तार के बदले आप क्या छोड़ते हैं?

exact search query की तुलना हर vector से करता है, जो corpus size में linear है। HNSW या IVF जैसे ANN indexes एक संरचना बनाते हैं (एक navigable graph, या clusters का समूह) जो सिर्फ एक छोटे candidate हिस्से तक जाती है, और query time sublinear हो जाता है। आप exact recall छोड़ते हैं: कुछ असली nearest neighbors छूट जाते हैं। efSearch या nprobe जैसे parameters आपको recall बनाम latency वाले curve पर आगे पीछे ले जाते हैं।

exact search का मतलब है query की तुलना हर vector से करना, जो एक लाख पर ठीक है और दस करोड़ पर नामुमकिन। ANN indexes candidate सेट काटते हैं। HNSW एक परतदार proximity graph बनाता है और उस पर विरल ऊपरी परत से घनी निचली परत तक लालची तरीके से चलता है, इसलिए आप पूरे corpus की जगह कुछ हजार nodes छूते हैं। IVF पहले space को clusters में बांटता है और सिर्फ सबसे नजदीकी कुछ clusters में खोजता है। दोनों हाल में आप recall छोड़ते हैं: कभी कभी असली nearest neighbor उस इलाके से ठीक बाहर बैठा होता है जिसे आपने खंगाला। अहम बात यह है कि यह एक डायल है। HNSW में efSearch तय करता है कि beam कितनी चौड़ी है; IVF में nprobe तय करता है कि आप कितने clusters खोलते हैं। मैं हमेशा एक छोटा ground truth सेट बनाता हूं, कुछ हजार queries जिन्हें brute force से score किया गया हो, फिर उस parameter को sweep करके recall at ten को p99 latency के मुकाबले plot करता हूं। पिछले जिस सिस्टम को मैंने tune किया, वहां 95 से 99 प्रतिशत recall पर जाने से latency तिगुनी हो गई और नीचे click rate लगभग हिली ही नहीं, तो हम 95 पर बैठ गए। मैं recall की निगरानी भी करता हूं, क्योंकि बड़े index rebuilds के बाद वह चुपचाप गिरता है।