דומה אבל פשוט יותר

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

פרופ' קראוטגמר מבהיר למה הכוונה באמצעות דוגמא מתחום הסייבר ואבטחת המידע: כדי לזהות התקפה מסוג "מניעת שירות מבוזרת" (distributed denial of service, DDOS), שבה מיוצר עומס-יתר של תקשורת על שרת כלשהו, על טכנאי הרשת לדעת כמה מחשבים שונים פנו לשרת במהלך יממה, ואיזה מחשב עשה זאת מספר הפעמים הרב ביותר. תשובה המבוססת על הזהויות הדיגיטליות (כתובות ה-IP) של המחשבים הפונים תהיה מאוד לא יעילה אם השרת יסרוק את כל רשומות ההיסטוריה שלו. אבל אלגוריתם שמשתמש בדוגמאות אקראיות בדרך מתוחכמת יכול להעריך את מספר המחשבים המדובר עם מרווח שגיאה של כ-1%. כמו כן, בעוד שקשה לזהות איזו כתובת IP מופיעה מספר הפעמים הרב ביותר, קיים אלגוריתם שיכול לזהות כתובות המופיעות בשכיחות גבוהה במיוחד (heavy hitters), אם יש כאלו.

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

אלגוריתם טוב הוא כזה שנפח הזיכרון שבו הוא משתמש קטן משמעותית מהגודל של מאגר הנתונים עצמו, כך שהחישוב יכול להיות מהיר ויעיל. במחקרים שנערכו באחרונה, פרופ' קראוטגמר ועמיתיו הציגו ניתוח מתמטי אשר ממיין את הבעיות לקלות וקשות. כדי לשפוך אור על המחקרים, פרופ' קראוטגמר חוזר להתקפת הסייבר: "אלגוריתם לאיתור כתובת ה- IPהשכיחה ביותר בזרם הנתונים – או אפילו הערכת שכיחות הופעתה בלבד – לא יכול להיות יעיל. אבל יש שאלה אחרת – שהמענה עליה קל, ובמקרה זה, חשוב אף יותר: האם ניתן להעריך כמה כתובות שונות מופיעות בשכיחות גדולה מ-0 – כלומר, מופיעות לפחות פעם אחת". חישובים כאלה כוללים סוג נפוץ של פונקציה הקרויה נורמת L^P, שבה המעריך p הוא מספר כלשהו. כאשר p=0, קל לאמוד את ערך הפונקציה; כאשר p הוא אינסוף, אומדן כזה קשה מאוד לביצוע. ומה לגבי p שנמצא בין שני הערכים? מתברר כי האומדן קשה לביצוע עבור כל ערך מעל 2, וכי כל ערך עד וכולל 2 קל לביצוע; כלומר קיים מעבר חד – בדומה למעבר פאזה בפיסיקה. מדוע זה כך? ההסבר המקובל היה שכל ערך מעל 2 דומה באופיו לאינסוף. אבל במהלך איפיון קבוצה כללית יותר של כל הפונקציות הסימטריות, פרופ' קראוטגמר ועמיתיו סיפקו שתי הוכחות מתמטיות להפרדה החדה, והראו כי קיים עיקרון מתמטי מובנה אשר יכול לתאר התנהגות זו.

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

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

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

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