פיצחו את סוד הביג דאטה וזכו בפרס

פרופ' נוגה אלון ופרופ' יוסי מטיאס זכו בפרס היוקרתי ע"ש קנלקיס של ה-ACM

01 יוני 2020

האגודה למכונות מחשוב (ACM) תעניק את הפרס הבינלאומי ע"ש פריס קנלקיס לשנת 2019, לפרופ' נוגה אלון מהפקולטה למדעים מדויקים ע"ש ריימונד ובברלי סאקלר ומאוניברסיטת פרינסטון, ולפרופ' יוסי מטיאס מבית הספר למדעי המחשב ע"ש בלווטניק ומ-Google, שהניחו בשנות ה-90' של המאה הקודמת את היסודות לאלגוריתמים של סטרימינג. המסגרת התיאורטית שהציעו החוקרים קובעת מה אפשר ומה אי אפשר לחשב בנתוני עתק (ביג דאטה).

 

מחלוצי מהפכת הביג דאטה

פרס ACM היוקרתי מוענק להישגים תיאורטיים, שהולידו יישומים משמעותיים ומוכחים בתחום המחשוב. פרופ' אלון ופרופ' מטיאס זכו בפרס יחד עם שותפיהם, פרופ' פיליפ גיבונס מאוניברסיטת קרנגי מלון ופרופ' מריו סגדי מאוניברסיטת רטגרס, על עבודתם פורצת הדרך בהנחת היסודות לאלגוריתמים של סטרימינג (מידע זורם), ובפיתוח יישומים לניתוח ביג דאטה (נתוני עתק). העבודה כוללת סדרת מחקרים, שבהם מאמר מכונן שפרסמו בשנת 1996 בכתב העת JCSS, בשם “The space complexity of approximating the frequency moments", שבו הציעו שיטה לטיפול בכמויות גדולות מאוד של מידע זורם. על מאמר זה גם קיבלו ב-2005 את פרס גדל היוקרתי.

 

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

 

הפער בין כמות המידע והזיכרון

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

 

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

 

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

 

"מהנדסים משתמשים במסגרת שלנו כדי לתכנת אלגוריתמים למידע זורם"

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

 

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

 

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

 

אוניברסיטת תל-אביב, רחוב חיים לבנון 30, 6997801.
UI/UX Basch_Interactive