מה הדרך הקצרה ביותר להגיע מתל אביב לחיפה? ואם כביש 2 נחסם, מה הדרך הקצרה ביותר כעת?
בפרויקט זה אנו חוקרים בעיה שנקראת Distance Sensitivity Oracle) DSO).
מטרתנו היא למצוא את המרחק/מסלול הקצר ביותר בין כל שני צמתים בהינתן שבכל רגע נתון קשתות של הגרף עלולות להיחסם באופן זמני ושרירותי. לדוגמא, ניתן להקביל את הגרף שלנו למפת הכבישים בארץ, כך שנתון לנו כי מתבצעות עבודות בכביש ולכן דרכים יכולות להיחסם. דוגמא נוספת הינה רשת תקשורת, כאשר לינקים ברשת עלולים ליפול ועדיין יש למצוא מסלול קצר שבו הפקטות יעברו ברשת מהמקור ליעד.
על מנת שנוכל להגיע לתוצאה המתבקשת במהירות, עלינו לעבד את הגרף וליצור ממנו מבנה נתונים קטן ככל האפשר כך שכאשר תגיע שאילתא, נוכל לענות עליה באופן מיידי בעזרת אחד מתתי הגרפים.
מנחה הקבוצה (ד"ר שראל כהן) חקר שאלה זו בעבודת הדוקטורט שלו, וכעת אנו, כחלק מקבוצת מחקר בינלאומית, ממשים שני מאמרים מדעיים בתחום (מבנה הנתונים DSO של Weimann and Yuster שתואר ב- FOCS'13, וכן את מבנה הנתונים של Chechik, Cohen, Fiat and Kaplan שתואר ב- SODA'17) ומבצעים Benchmarkin על מבני הנתונים שמימשנו.
בהצגת הפרויקט נתמקד במבנה הנתונים של Weimann & Yuster, המבוסס על הרעיון הבא: תחילה בונים באופן אקראי מספר רב של "גרסאות" של הגרף על ידי מחיקה אקראית של קשתות, כך שעבור כל שאילתא ניתן למצוא גרף המכיל את המסלול הקצר ביותר וזורק את הקשתות שנפלו. בכל גרף זה נחשב מטריצה של המסלולים הקצרים ביותר - APSP.
קבוצת המחקר כוללת את ד"ר מרטין קראג'קה מצרפת (LIX-Polytechnique), וכן את ד"ר אוהד בן ברוך מאונ' בן גוריון.