אינדקסים מבוססי גרפים — HNSW
מהו HNSW?
HNSW — ראשי תיבות של Hierarchical Navigable Small World — הוא אחד מאלגוריתמי ה-ANN הנפוצים והמוצלחים ביותר בפרקטיקה, והאינדקס המובנה כברירת מחדל ברוב מסדי הנתונים הווקטוריים המובילים. הרעיון המרכזי: לארגן את כל הוקטורים כגרף רב-שכבתי (multi-layer graph), שבו כל וקטור הוא צומת (node), וצמתים קרובים זה לזה במרחב מחוברים בקשתות (edges).
המבנה הרב-שכבתי הוא הלב של האלגוריתם: השכבה העליונה דלילה — מעט מאוד צמתים, עם קשתות "קפיצה גדולה" למרחקים ארוכים במרחב. כל שכבה מתחתיה צפופה יותר, עד לשכבה התחתונה שמכילה את כל הווקטורים ואת רוב הקשתות "המקומיות" קצרות הטווח. אפשר לדמיין זאת כמפת דרכים: כביש בין-עירוני מהיר בשכבה העליונה, וכבישים מקומיים הולכים ומתפצלים ככל שיורדים שכבה.
איך מתבצע חיפוש בגרף
החיפוש מתחיל בנקודת כניסה קבועה בשכבה העליונה (הדלילה ביותר). מהנקודה הזו, האלגוריתם עובר בצורה חמדנית (greedy) לשכן הקרוב ביותר לשאילתה מבין שכני הצומת הנוכחי, וממשיך כך שוב ושוב כל עוד נמצא שכן קרוב יותר לשאילתה מהצומת הנוכחי באותה שכבה.
כשאין יותר שכן קרוב יותר בשכבה הנוכחית, האלגוריתם "יורד" שכבה אחת למטה, ומתחיל שוב את אותו תהליך חיפוש חמדני משם — הפעם בגרף צפוף יותר, עם קשתות קצרות וממוקדות יותר. התהליך חוזר על עצמו עד השכבה התחתונה, שבה מתקבלים המועמדים הסופיים לתשובה.
ההשוואה המדויקת ביותר היא לרשימת דילוג (skip list): קודם קופצים קפיצות גדולות שמצמצמות מהר את המרחב הרלוונטי לחיפוש, ורק לקראת הסוף עוברים לחיפוש עדין ומדויק באזור הקטן שכבר אותר.
למה זה מהיר — אינטואיציה לסיבוכיות
בניגוד לסריקת brute-force שבודקת כל וקטור בבסיס הנתונים (סיבוכיות ליניארית, O(n)), החיפוש בגרף HNSW "מדלג" על רוב הצמתים לגמרי — כל שכבה מצמצמת את מרחב החיפוש הרלוונטי משמעותית לפני שממשיכים לשכבה הבאה, מה שנותן לחיפוש סיבוכיות שקרובה ללוגריתמית ביחס לגודל בסיס הנתונים (בערך O(log n)) במקום ליניארית.
בפועל המשמעות היא ששאילתה על בסיס נתונים בגודל מיליון וקטורים לא דורשת מיליון חישובי מרחק, אלא רק שבר קטן מהם — שיפור דרמטי שמאפשר לחיפוש וקטורי לפעול ב-latency של מילישניות בודדות גם בקנה מידה עצום.
המחיר: זיכרון וזמן בנייה
היתרון של HNSW אינו חינם. הגרף עצמו — לא רק הווקטורים הגולמיים — חייב להישמר בזיכרון: כל צומת שומר רשימת קשתות (שכנים) בכל שכבה שהוא משתתף בה, כך שהאינדקס תופס משמעותית יותר זיכרון ממה שהוקטורים הגולמיים היו תופסים לבדם.
גם בניית האינדקס אינה זניחה: הוספת כל וקטור חדש דורשת "לחווט" אותו לתוך הגרף — למצוא את השכנים המתאימים לו בכל שכבה שהוא ישתתף בה ולעדכן את הקשתות סביבו — כך שזמן בנייה גדל עם גודל בסיס הנתונים, ואינדקסים עצומים עשויים לקחת זמן משמעותי לבנייה מלאה.
הטרייד-אוף הזה — ביצועי חיפוש מצוינים במחיר זיכרון — הוא בדיוק מה שמניע גישה חלופית: אינדקסים מבוססי קוונטיזציה, שדוחסים את הוקטורים עצמם כדי לחסוך בזיכרון במחיר מסוים בדיוק. זה הנושא של הפרק הבא.