החוקרים מאוניברסיטת תל אביב זכו בפרס על הנחת היסודות לאלגוריתמים של סטרימינג בשנות ה-90′ * המסגרת התיאורטית שהציעו החוקרים מאוניברסיטת תל אביב קובעת מה אפשר ומה אי אפשר לחשב בנתוני עתק
האגודה למכונות מחשוב (ACM) תעניק את הפרס הבינלאומי ע”ש פריס קנלקיס לשנת 2019 לפרופ’ נוגה אלון מאוניברסיטת תל אביב ומאוניברסיטת פרינסטון ולפרופ’ יוסי מטיאס מאוניברסיטת תל אביב ומ-Google.
פרס ACM היוקרתי ע”ש קנלקיס מוענק להישגים תיאורטיים שהולידו יישומים משמעותיים ומוכחים בתחום המחשוב. פרופ’ אלון ופרופ’ מטיאס זכו בפרס יחד עם שותפיהם, פרופ’ פיליפ גיבונס מאוניברסיטת קרנגי מלון ופרופ’ מריו סגדי מאוניברסיטת רטגרס, על עבודתם פורצת הדרך בהנחת היסודות לאלגוריתמים של סטרימינג (מידע זורם) ובפיתוח יישומים לניתוח ביג דאטה (נתוני עתק).
החוקרים מאוניברסיטת תל אביב זכו בפרס ACM ע”ש קנלקיס, יחד עם גיבונס וסגדי, על סדרה של מחקרים, כולל מאמר מכונן שפרסמו בשנת 1996 בכתב העת JCSS, בשם “The space complexity of approximating the frequency moments” – ובו הציעו שיטה לטיפול בכמויות גדולות מאוד של מידע זורם. על מאמר זה גם קיבלו ב-2005 את פרס גדל היוקרתי.
ועדת הפרס הסבירה בנימוקיה: “הם [אלון, גיבונס, מטיאס וסגדי] היו חלוצי המסגרת לטיפול האלגוריתמי בהזרמה מסיבית של נתוני עתק, והיום שיטות הסקיצה והאלגוריתמים שלהם עדיין מהווים את הגישה העיקרית באלגוריתמים של סטרימינג ואת הבסיס לתת-תחום שלם בשדה האלגוריתמיקה… בנוסף, המושגים של סקיצות ותקצירי מידע שהציעו נמצאים בשימוש באופן שגרתי במשימות שונות של ניתוח מידע בתחומים שונים כמסדי נתונים, ניטור רשתות, ניתוחי שימוש של מוצרי אינטרנט, עיבודי שפה טבעית ולמידת מכונה”.
פרופ’ אלון מסביר: “היום בעידן של הביג דאטה יש לנו כמויות עצומות של מידע בהרבה תחומים – מלמידה חישובית, דרך אנליזה של דיבור וכלה בתקשורת ברשתות. אנחנו יכולים לקרוא את הנתונים כשהם מגיעים, אבל אין לנו אפשרות לשמור את הכול בזיכרון. כעת השאלה היא אילו אלגוריתמים ניתן לתכנת כדי לבצע חישובים בקלט גם מבלי לשמור אותו – באמצעות דאטה סינופסיס, או תקצירי מידע”.
פרופ’ מטיאס מוסיף: “האתגר של חישובים על ביג דאטה אולי נשמע מובן מאליו היום, אבל בשנות ה-90′ נאלצנו להסביר מה בכלל הבעיה. הרי חישוב של פונקציות סטטיסטיות יכול להיות תרגיל בקורס תכנות, והבעיה החישובית המשמעותית נוצרת רק כשיש פער בין כמות המידע והזיכרון שניתן לחשב בו. לשם כך הצענו מודל חישובי שמשתמש בתקצירי מידע, או ‘סקיצות’, ופיתחנו אלגוריתמים תיאורטיים ומעשיים שחלקם נכנסו כבר אז ליישום במערכות בינה עסקית מהגדולות בעולם. שנים ספורות אחרי פרסום המאמר, האינטרנט החל להתפוצץ ממידע – ונוצר פער הולך וגדל בין כמות המידע למה שניתן לשמור בזיכרון. מתוך הפער הזה צמח תחום חדש של אלגוריתמים למידע זורם, עם שימוש חכם בתקצירי מידע”.
במאמר המכונן, ובמחקרי ההמשך הרבים שפרסמו לאורך השנים, פרופ’ אלון ופרופ’ מטיאס הדגימו כיצד ניתן להשתמש בתכונות סטטיסטיות מסוימות של המידע כדי להריץ חישובים על ביג דאטה מבלי לשמור את הנתונים במערכת.
פרופ’ אלון: “נניח שהמידע שזורם אלינו הוא אוסף של מספרים ואני רוצה לבדוק אם יש מספר שהגיע פעמיים. אלגוריתם רגיל צריך לקחת כל מספר חדש שמגיע ולהשוות אותו לכל מספר שהגיע קודם. אבל בשביל זה צריך לשמור את כל המספרים שהגיעו, משימה בלתי אפשרית במסגרת מגבלות הזיכרון. לעומת זאת, אפשר ליצור סטטיסטיקה יעילה, שמצריכה זיכרון קטן, שתעריך בקירוב כמה מספרים שונים הגיעו בקלט או כמה זוגות מהמספרים שהגיעו שווים זה לזה. במקביל גם הראינו תכונות סטטיסטיות של ביג דאטה שלא ניתן לזהות עם זיכרון מוגבל”.
פרופ’ מטיאס: “האתגר הוא לשמור את תקצירי הנתונים כך שעדיין יתאפשר לנו להריץ חישובים לבעיות שונות ולהוכיח שהחישובים נכונים. הצענו את המסגרת התיאורטית-מתמטית לתמצות חכם של מידע, והראנו מה אפשר ומה אי אפשר לחשב בצורה הזאת. נוצר תחום עשיר מאוד, שבמסגרתו חוקרים רבים עשו עבודות יפיפיות וחשובות, הן מהבחינה התיאורטית והן מהבחינה המעשית. מהנדסים משתמשים במסגרת שלנו כדי לתכנת אלגוריתמים למידע זורם”.
נשיא אוניברסיטת תל אביב, פרופ’ אריאל פורת: “אני מברך את פרופ’ אלון ופרופ’ מטיאס על הזכייה בפרס היוקרתי. עיסוק בנתוני עתק בתחומים שונים ומגוונים נפוץ היום יותר מתמיד, ויש לו חשיבות תיאורטית ופרקטית גם יחד. אנחנו גאים בתרומתם של פרופ’ אלון ופרופ’ מטיאס לפיתוח האלגוריתמים לניתוח ניתוח נתוני עתק, ופרס ה- ACM הוא ההוקרה הטובה ביותר להישגיהם פורצי הדרך”.
