אלגוריתם Hilltop

מטרת מאמר זה להכנס לעומקו של אלגוריתם Hilltop, מהאלגוריתמים הבסיסיים המשמשים בגוגל, ולהבין אותו טוב יותר. האלגוריתם הופעל בגוגל ב-2003 בעדכון שזכה לכינוי "עדכון פלורידה", שהשפיע רבות על דירוגם של אתרים שונים במנוע החיפוש באותה תקופה. האלגוריתם עבר מאז שינויים שונים, אך אנו נביא כאן את האלגוריתם המקורי.

הקדמה

אלגוריתם Hilltop מציע מודל של מנוע חיפוש, שכמות התוצאות בו קטנה יותר מבמנוע רגיל. זאת משום שמרבית המשתמשים אינם מעוניינים בכל התוצאות אלא רק ב-10-20 הראשונות.
הרעיון המרכזי הוא יצירת תת-רשת של רשת האינטרנט, הקשורה בשאילתת החיפוש, והעזרות בה על מנת למצוא את התשובה לשאילתא. כתוצאה מכך, קיימת מגבלה על HillTop שמונעת מהאלגוריתם להיות ממומש על כל שאילתא שהיא – רק על נושאים בעלי כמות גדולה מספיק של מסמכים הקשורים אליהם, ניתן לחשב את השאילתא. בנוסף, דרושים משאבי זמן לחישוב מלא של השאילתא, מה שמגביל את היכולת לביצוע החישוב המלא בזמן אמת.

הנחות

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

דף מומחה – expert page

איך מאפיינים דף מומחה באופן אוטומטי? באלגוריתם Hilltop מתייחסים לכמות המקשרים הבלתי תלויים .

מקורות תלויים – host affiliation

2 מקורות תלויים אם הם עונים לאחד הקריטריונים הבאים:
1. שלושת המספרים הראשונים בכתובת ה-IP זהים.
2. הם בעלי אותו שם דומיין (גם אם בסיומות שונות, כגון domain.com, domain.co.uk).
3. באופן טרנזיטיבי, 2 מקורות A ו-C יהיו תלויים גם אם A תלוי ב-B, ו-B תלוי ב-C, עפ"י 2 הסעיפים הקודמים.
למרות שלעתים 2 מקורות שונים עשויים להחשב כתלויים, זהו קירוב סביר.
הדומיינים השונים מוגדרים במבנה נתונים הממפה כל דומיין ל-host, וכך ניתן לבצע חיפוש בתוך מרחב ה-hosts.

מיון מקדים של האינטרנט

בהעדר שאילתת החיפוש, אנו מעוניינים לערוך מיון ראשוני לדפי אינטרנט, נמצא דפים שונים העוסקים בנושאים ממוקדים.
יהי t ערך סף מסויים. דף ששייך לקטגוריה כללית כלשהי, כגון אמנות, מדע, וכד', ייחשב כדף מומחה לנושא אם הוא יוציא לפחות t קישורים ל-hosts שונים.
תכונה זו מרמזת על כך שהדף שייך לנושא ואיננו סתם אוסף אקראי של לינקים.

אינדוקס דפי מומחים

על מנת למיין את דפי המומחים לפי המונחים השונים, נשמרים עבור כל דף מונחי מפתח במבנה נתונים מתאים.
מדד הסמכה יגדיר עבור מונחי מפתח את החלק מהדף אליו הם רלוונטיים:
· כותרת הדף מסמיכה את הדף כולו.
· כותרת פנימית בדף (למשל תג H1) מסמיכה את כל הטקסט והלינקים שאחריה עד הכותרת הבאה בעלת חשיבות זהה או גדולה משלה.
· ביטוי קישור (anchor text) מסמיך את הטקסט והלינק שהוא מכיל.
מונחי המפתח אינם כוללים טקסט רגיל מתוך העמוד.

טיפול בשאילתא

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

דירוג דפי המומחה

לכל דף מומחה מחושבת עבור השאילתא שלישיה (S0, S1, S2).
יהי k מספר המונחים בשאילתא q.
Si יחושב עבור כל הביטויים המכילים בדיוק k-i מונחים מתוך השאילתה q. כלומר, S0 יחושב עבור הביטויים המכילים את השאילתא כולה.
הנוסחא לחישוב Si:

LevelScore(p) – מחושב לפי סוג המשפט p. לדוגמא, ניתן ערך 16 לכותרת העמוד, 6 לכותרות פנימיות, 1 לביטוי קישור וכו'.
FullnessFactor(p,q) – יהי m מספר המונחים ב-p שאינם ב-q, ויהי plen אורך הביטוי p.
אזי

לאחר שמחושבים S0,S1,S2 מדורגים דפי המומחה השונים על פי שקלול של 3 אבני הבניין, S0,S1,S2. ל-S0 (המבטא את השאילתא המקורית) ניתן המשקל הגדול ביותר.

דירוג דפי המטרה

דפי המטרה מדורגים בעזרת דפי המומחה אותם מצאנו קודם. לכל דף מטרה צריכים להצביע 2 דפי מומחים לפחות על מנת שנשקול אותו.
לאחר מיון בסיסי זה, מתבצע הסינון באופן הבא בעזרת תורת הגרפים:
1. נצייר את הגרף של דפי המומחה ודפי המטרה, כאשר כל קישור מדף מומחה E לדף מטרה T ייוצג ע"י קשת מכוונת בגרף.
2. לכל קשת בגרף ניתן משקל עפ"י היחס בין הקישורים היוצאים מדף המומחה לדף המטרה ומונחי המפתח שהוגדרו לדף המומחה.
לכל מילה w בשאילתת החיפוש, תהי occ(w,T) מספר ההופעות המובחנות של ביטויי החיפוש ב-E שמכילים את w ומסמיכים את T (עפ"י יחס הסמכה שתואר למעלה).
המשקל של הקשת (E,T) יוגדר באופן הבא:

אם אין קשתות כאלה, או אין קשתות בעלות משקל חיובי, Edge_Score(E,T) = 0
באופן זה המשקל עולה ככל שעולה הדירוג של האתר המקשר והרלוונטיות לנושא.
3. בשלב זה בודקים האם קיימים מקורות תלויים מהם יוצאים 2 קישורים (או יותר) לאותו עמוד. אם כן, משאירים רק את הקישור בעל המשקל הגדול ביותר ואת האחרים מסירים.
4. על מנת לחשב את ה-Target_Score עבור עמודי המטרה, סוכמים עבור כל הקשתות הנכנסות:

5. בשלב זה ניתן לדרג את דפי המטרה על פי ה-Target_Score שלהם. באופן אופציונלי, ניתן לחשב מדד תאימות נוסף שיבדוק את התאמת דף המטרה לשאילתא, ואז לשקלל בין שני המדדים השונים.

סיכום

אלגוריתם Hilltop הוא אחד האלגוריתמים החשובים בגוגל, המסתמך לא על מבנה רשת האינטרנט כולה (כמו PageRank) אלא רק על מבנה תת-הרשת הרלוונטית לנושא. בעזרת השימוש בדפי מומחים המקשרים לאתרים רלוונטיים רבים, מאתר האלגוריתם את הדף המתאים ביותר מבין הדפים המקושרים ביותר.
עם זאת, בגלל מגבלות כמו זמן חישוב ארוך, הצורך בנושא גדול דיו וכו', הוא משמש בגוגל רק בחלק מהזמן.
לעיון נוסף: המאמר המקורי של קרישנה בהארט וג'ורג' א. מיהילה "When Experts agree: Using non-affiliated Experts to Rank Popular Topics".

המאמר נכתב ע"י אליס תמנת מחברת K Logic קידום אתרים