חיפוש מדויק מול חיפוש מקורב (kNN vs ANN)
חיפוש מדויק: Brute-Force k-Nearest Neighbors
הדרך הפשוטה והמדויקת ביותר למצוא את k הפריטים הקרובים ביותר לשאילתה היא לחשב את מרחק (או דמיון) השאילתה מול כל וקטור בבסיס הנתונים, בלי יוצא מן הכלל, ולמיין את התוצאות. השיטה הזו נקראת brute-force exact k-Nearest Neighbors, והיא מדויקת לחלוטין מבחינה מתמטית — היא תמיד מוצאת את השכנים הקרובים ביותר האמיתיים, ללא פשרות.
המחיר הוא בסיבוכיות: עבור n וקטורים בממד d, כל שאילתה בודדת דורשת O(n·d) פעולות — חישוב מרחק אחד לכל וקטור, וכל חישוב כזה תלוי בממד. הסיבוכיות הזו ליניארית בגודל בסיס הנתונים: הכפלת מספר הווקטורים מכפילה את זמן השאילתה. עבור אלפי או עשרות אלפי וקטורים זה עדיין ישים; עבור מיליוני או מיליארדי וקטורים, בעומס של שאילתות רבות בשנייה ובדרישת latency נמוך, זה כבר לא מעשי.
חיפוש מקורב: Approximate Nearest Neighbor (ANN)
הרעיון המרכזי של ANN: לוותר על הבטחת דיוק מוחלט (מציאת השכן הקרוב ביותר האמיתי, בוודאות) בתמורה למהירות גבוהה משמעותית — לרוב שיפור של סדרי גודל בזמן שאילתה, במחיר סיכוי קטן (לרוב ניתן לכיוון) לפספס חלק מהשכנים האמיתיים.
מבחינה מבנית, שיטות ANN כמעט תמיד בונות אינדקס מראש — מבנה נתונים מיוחד שנבנה פעם אחת (offline) ומאפשר לענות על שאילתות רבות מהר בהרבה מסריקה מלאה בכל פעם, במקום לחשב מרחק לכל וקטור מחדש בכל שאילתה. זה בדיוק ה"אינדקס" שהוזכר בפרק המבוא לנושא — הפרקים הבאים עוסקים במבני האינדקס הנפוצים בפועל.
איך מודדים איכות של חיפוש מקורב: Recall@k
recall@k הוא המדד הסטנדרטי להערכת איכות שיטת ANN: מתוך k השכנים הקרובים ביותר האמיתיים (שמתקבלים מ-exact search על אותה שאילתה), איזה אחוז מהם שיטת ה-ANN אכן החזירה בתוצאותיה. לדוגמה, recall@10 של 0.95 אומר שבממוצע, 9.5 מתוך 10 השכנים האמיתיים הקרובים ביותר אכן הופיעו בתוצאות ה-ANN.
בפועל בודקים recall@k על מדגם שאילתות, משווים את תוצאות ה-ANN מול תוצאות ה-exact search כ"אמת מידה" (ground truth), וממוצעים. המדד הזה יחזור בפרק העוסק בהערכת ביצועים בהמשך הנושא — הוא הכלי המרכזי להשוואה בין אינדקסים ובין הגדרות פרמטרים שונות של אותו אינדקס.
מתי בכלל צריך ANN?
חיפוש מדויק (exact) עדיין הבחירה הנכונה כאשר בסיס הנתונים קטן יחסית (עד כמה עשרות אלפי וקטורים, כאשר גם סריקה מלאה מהירה מספיק בפועל), או כאשר יש דרישה עסקית מוחלטת ל-100% recall — למשל התאמות משפטיות או רפואיות שבהן פספוס תוצאה אסור.
ברוב המקרים בפרודקשן בקנה מידה — מנועי חיפוש, מערכות RAG, מערכות המלצה — הכמות היא מיליוני עד מיליארדי וקטורים, וANN הוא לא רק אופציה אלא הכרח מעשי כדי לשמור על latency סביר. הפרקים הבאים עוסקים בשיטות ה-ANN הנפוצות ביותר בתעשייה.