קוונטיזציה ואינדקסים מבוססי IVF/PQ

IVF — Inverted File Index

הרעיון של IVF: לפני שמגיעה אפילו שאילתה אחת, מחלקים את כל הוקטורים בבסיס הנתונים למספר קבוע של "תאים" (clusters), בדרך כלל באמצעות אלגוריתם k-means — כל תא מיוצג ע"י צנטרואיד (centroid), הממוצע של כל הוקטורים שהוקצו אליו.

בזמן שאילתה, במקום להשוות את השאילתה מול כל וקטור בבסיס הנתונים, משווים אותה קודם רק מול הצנטרואידים — מוצאים את כמה התאים שהצנטרואיד שלהם הכי קרוב לשאילתה — וסורקים לעומק רק את הוקטורים שבתוך התאים הנבחרים האלה. כך נחסכת רוב העבודה: אין צורך להשוות מול וקטורים שבתאים רחוקים לגמרי מהשאילתה.

הפרמטר המרכזי שקובע את הטרייד-אוף כאן נקרא nprobe — מספר התאים שנסרקים בפועל בכל שאילתה. nprobe גבוה יותר בודק יותר תאים, מה שמשפר את הסיכוי למצוא את השכנים האמיתיים (recall גבוה יותר) אך מאט את השאילתה; nprobe נמוך מהיר יותר אך מסתכן בפספוס שכנים אמיתיים שנפלו בתא שלא נבדק.

תרשים פיזור דו-ממדי המציג ארבעה תאים (clusters) של נקודות כחולות, כל אחד עם צנטרואיד מסומן בעיגול עם קווי כוונת, מופרדים בגבולות דמויי Voronoi. תא אחד, בפינה הימנית-העליונה, מסומן בכתום עם רקע מודגש קלות — מייצג את התאים שנבחרו לפי nprobe. נקודת שאילתה לדוגמה מסומנת ב-X ליד גבול אותו תא, עם חץ מקווקו כתום המצביע מהשאילתה אל הצנטרואיד הקרוב ביותר.
IVF: חלוקת המרחב לתאים סביב צנטרואידים — שאילתה נבדקת קודם מול הצנטרואידים, ואז נסרקת רק בתוך התאים הקרובים (nprobe)

Product Quantization (PQ) — דחיסת הוקטורים עצמם

PQ פותר בעיה שונה מ-IVF: לא אילו וקטורים להשוות, אלא איך לאחסן ולהשוות אותם בזול יותר. הרעיון: מפצלים כל וקטור למספר תת-וקטורים קצרים (למשל וקטור באורך 1,536 מתחלק ל-96 תת-וקטורים באורך 16 כל אחד), ועבור כל "עמדה" של תת-וקטור לומדים בנפרד, מראש וע"י clustering, ספר קודים (codebook) קטן — קבוצה קבועה של צנטרואידים מייצגים (למשל 256 כאלה).

אחרי הלמידה, כל תת-וקטור מוחלף באינדקס הצנטרואיד הקרוב אליו בספר הקודים שלו — מספר שלם קטן אחד (בין 0 ל-255, למשל, שניתן לאחסון בבית בודד) במקום רשימת מספרים עשרוניים. זו בדיוק הדחיסה: וקטור באורך 1,536 מספרי float32 (כ-6 קילובייט) יכול להצטמצם, להמחשה, לכמה עשרות בתים בלבד — שיפור דרמטי בזיכרון, במחיר איבוד מדויק (lossy compression): הוקטור המדוחס הוא קירוב, לא שחזור מדויק, של הוקטור המקורי.

תרשים המציג וקטור ארוך (פס תאים כחולים רבים) בחלק העליון, מחולק בסוגריים לארבע קבוצות של תת-וקטורים, עם חצים יורדים מכל קבוצה לתיבה כתומה קטנה המכילה מספר בודד (73, 12, 205, 88) — ממחיש שכל תת-וקטור מוחלף במספר שלם קטן אחד. בתחתית, אשכול נקודות כחולות מייצג את ספר הקודים (codebook) שממנו נבחר כל מספר, עם עיגול כתום מסביב לנקודה שנבחרה.
Product Quantization: כל תת-וקטור מוחלף באינדקס הצנטרואיד הקרוב אליו בספר הקודים — דחיסה חדה במחיר קירוב

IVF-PQ: השילוב הנפוץ בפרקטיקה

בפועל, IVF ו-PQ כמעט תמיד משולבים יחד, בשיטה שנקראת IVF-PQ: IVF מצמצם קודם את מרחב החיפוש לכמה תאים רלוונטיים בלבד, ו-PQ דוחס את הוקטורים בתוך התאים האלה כך שגם ההשוואה בתוכם זולה בזיכרון ובחישוב. השילוב הזה נועד בדיוק כדי לפתור את חולשת הזיכרון של HNSW שראינו בפרק הקודם, במחיר של ירידה מסוימת ב-recall שנובעת מהדחיסה החדה.

שלושת משפחות האינדקסים שנסקרו עד כה תופסות שלוש נקודות שונות במרחב הטרייד-אוף בין מהירות/דיוק לזיכרון: HNSW נותן את ה-recall והמהירות הטובים ביותר אך במחיר זיכרון הגבוה מכולם; IVF לבדו פשוט לבנייה ולהבנה, מהיר, וצורך זיכרון בינוני; IVF-PQ הוא החסכוני ביותר בזיכרון מבין השלושה, במחיר איבוד דיוק נוסף מהדחיסה. אין אינדקס אחד ש"מנצח" תמיד — הבחירה תלויה בגודל בסיס הנתונים, בתקציב הזיכרון ובדרישת ה-recall של המערכת הספציפית.