คำว่า "พัฒนา" เป็นคำสำคัญในที่นี้เนื่องจากการวิจัยครอบคลุมถึงการสร้างเสริมอัลกอริทึมบนชุดข้อมูลสังเคราะห์มากกว่าข้อมูลขนาดใหญ่จริง
“ กราฟถูกใช้กันอย่างแพร่หลายเพื่อแสดงและวิเคราะห์วัตถุในโลกแห่งความเป็นจริงในหลาย ๆ โดเมนเช่นโซเชียลเน็ตเวิร์กระบบธุรกิจอัจฉริยะชีววิทยาและประสาทวิทยา” Kaist กล่าว “ เมื่อพัฒนาและทดสอบอัลกอริทึมสำหรับกราฟขนาดใหญ่มักใช้กราฟสังเคราะห์แทนกราฟจริง เนื่องจากการแบ่งปันและใช้กราฟจริงขนาดใหญ่มีข้อ จำกัด มากเนื่องจากเป็นกรรมสิทธิ์หรือรวบรวมไม่ได้ในทางปฏิบัติ”
ตามอัตภาพ Kaist การพัฒนาและทดสอบอัลกอริทึมกราฟทำได้โดยใช้วิธีการสองขั้นตอนต่อไปนี้:
ขั้นตอนที่หนึ่งสร้างกราฟสังเคราะห์และจัดเก็บไว้ในดิสก์ กราฟมักจะสร้างขึ้นโดยการสร้างตามพารามิเตอร์หรือการปรับขนาดกราฟซึ่งก่อนหน้านี้จะแยกพารามิเตอร์จำนวนเล็กน้อยที่สามารถจับคุณสมบัติบางอย่างของกราฟจริงที่กำหนดและสร้างกราฟสังเคราะห์ด้วยพารามิเตอร์หลังจากนั้นจะเพิ่มสเกล a ให้กราฟจริงเป็นกราฟที่ใหญ่กว่าเพื่อรักษาคุณสมบัติของกราฟจริงดั้งเดิมให้มากที่สุด
ขั้นตอนที่สองโหลดกราฟที่จัดเก็บไว้ในหน่วยความจำหลักของเครื่องมือประมวลผลกราฟเช่น Apache GraphX และเรียกใช้อัลกอริทึมกราฟที่กำหนดบนเอ็นจิ้น “ เนื่องจากกราฟมีขนาดใหญ่เกินกว่าที่จะใส่ลงในหน่วยความจำหลักของคอมพิวเตอร์เครื่องเดียวโดยทั่วไปเครื่องมือสร้างกราฟจะทำงานบนคลัสเตอร์ของคอมพิวเตอร์หลายสิบเครื่องหรือหลายร้อยเครื่อง” Kaist กล่าว“ ดังนั้นค่าใช้จ่ายของวิธีการสองขั้นตอนแบบเดิมจึงสูง .”
ทีมงานเกาหลีไม่ได้สร้างและจัดเก็บกราฟสังเคราะห์ขนาดใหญ่
แต่จะโหลดกราฟจริงขนาดเล็กเริ่มต้นลงในหน่วยความจำหลักแทน จากนั้นใช้เทคนิคที่เรียกว่า T-GPS (การจำลองการประมวลผลกราฟล้านล้านมาตราส่วน) อัลกอริทึมกราฟจะเผชิญหน้ากับกราฟจริงขนาดเล็กราวกับว่ากราฟสังเคราะห์ขนาดใหญ่ที่ควรสร้างขึ้นจากกราฟจริงมีอยู่ในหน่วยความจำหลัก Kaist กล่าว เพิ่มเติมว่าหลังจากทำอัลกอริทึม T-GPS จะส่งคืนผลลัพธ์เช่นเดียวกับวิธีการสองขั้นตอนทั่วไป
“ แนวคิดหลักของ T-GPS คือการสร้างเฉพาะส่วนของกราฟสังเคราะห์ที่อัลกอริทึมจำเป็นต้องเข้าถึงได้ทันทีและปรับเปลี่ยนระบบประมวลผลกราฟเพื่อรับรู้ส่วนที่สร้างขึ้นทันทีซึ่งเป็นส่วนหนึ่งของกราฟสังเคราะห์ที่สร้างขึ้นจริง ” Kaist กล่าว
T-GPS ประมวลผลกราฟหนึ่งล้านล้านขอบบนคอมพิวเตอร์เครื่องเดียวในขณะที่วิธีการสองขั้นตอนแบบเดิมจำเป็นต้องมีคอมพิวเตอร์สิบเอ็ดเครื่องที่มีคุณสมบัติเดียวกันเพื่อประมวลผลกราฟที่มีขอบหนึ่งพันล้าน ไม่จำเป็นต้องเข้าถึงเครือข่าย T-GPS เร็วกว่าวิธีการทั่วไปถึง 43 เท่าซึ่งมีค่าใช้จ่ายในการสื่อสารที่สำคัญ
งานนี้ถูกนำเสนอในการประชุม IEEE ICDE 2021 ในชื่อ 'การจำลองการประมวลผลกราฟล้านล้านสเกลตามการเพิ่มขนาดกราฟจากบนลงล่าง'