'פיתוח' היא המילה החשובה כאן, מכיוון שהמחקר מכסה אלגוריתמי השחזה על מערכי נתונים סינתטיים ולא על נתונים גדולים גדולים.
"נעשה שימוש נרחב בתרשימים לייצוג וניתוח של אובייקטים בעולם האמיתי בתחומים רבים כמו רשתות חברתיות, בינה עסקית, ביולוגיה ומדעי המוח", אמר קייסט. "כאשר מפתחים ובודקים אלגוריתמים עבור גרף בקנה מידה גדול, משתמשים בדרך כלל בגרף סינתטי במקום בגרף אמיתי. הסיבה לכך היא ששיתוף ושימוש בגרפים אמיתיים רחבי היקף מוגבל מאוד בגלל היותם קנייניים או בלתי אפשרי כמעט לאיסוף. "
באופן מקובל, על פי Kaist, פיתוח ובדיקת אלגוריתמים של גרפים נעשים באמצעות הגישה הדו-שלבית הבאה:
שלב ראשון מייצר גרף סינתטי ומאחסן אותו על דיסקים. הגרף נוצר בדרך כלל על ידי ייצור מבוסס פרמטר או שינוי קנה המידה של הגרף - הראשון מחלץ מספר קטן של פרמטרים שיכולים לתפוס כמה מאפיינים של גרף אמיתי נתון ויוצר את הגרף הסינתטי עם הפרמטרים, האחרון מעלה קנה מידה א נתון גרף אמיתי לגרף גדול יותר כדי לשמר את המאפיינים של הגרף האמיתי המקורי ככל האפשר.
שלב שני טוען את הגרף המאוחסן בזיכרון הראשי של מנוע עיבוד גרפים, כגון Apache GraphX, ומבצע אלגוריתם גרפי נתון במנוע. "מכיוון שהגרף גדול מכדי להכנס לזיכרון הראשי של מחשב יחיד, מנוע הגרף פועל בדרך כלל על אשכול של כמה עשרות או מאות מחשבים", אמר קייסט, "לכן עלות הגישה הדו-שלבית המקובלת היא גבוהה. . ”
הצוות הקוריאני אינו מייצר ואוחסן גרף סינטטי רחב היקף.
במקום זאת, הוא טוען את הגרף האמיתי הקטן הראשוני בזיכרון הראשי. ואז, תוך שימוש בטכניקה המכונה T-GPS (סימולציה של עיבוד גרפים בקנה מידה טריליוני), אלגוריתם הגרפים התמודד עם הגרף האמיתי הקטן כאילו הגרף הסינתטי בקנה מידה גדול שיש לייצר מהגרף האמיתי קיים בזיכרון הראשי, אמר קייסט. והוסיף כי לאחר סיום האלגוריתם T-GPS מחזיר את אותה תוצאה כמו הגישה הדו-שלבית המקובלת.
"הרעיון המרכזי של T-GPS הוא יצירת רק את החלק של הגרף הסינתטי אליו האלגוריתם צריך לגשת באופן מיידי ושינוי מנוע עיבוד הגרפים בכדי לזהות את החלק שנוצר תוך כדי טיסה כחלק מהגרף הסינתטי שנוצר בפועל, ”אמר קייסט.
T-GPS עיבד גרף של טריליון שוליים במחשב אחד, ואילו הגישה הדו-שלבית המקובלת זקוקה לאשכול של אחד-עשר מחשבים באותו מפרט לעיבוד גרף של מיליארד קצוות. לא היה צורך בגישה לרשת, ה- T-GPS היה מהיר פי 43 מהגישה המקובלת שיש לה תקורה משמעותית בתקשורת.
העבודה הוצגה בכנס IEEE ICDE 2021 כ'סימולציית עיבוד גרפים בקנה מידה טריליון על בסיס שדרוג גרפים מלמעלה למטה '.