موسسه تحقیقاتی کرهای Kiast، روشی به منظور توسعهی الگوریتمی برای گرافهایی با یک تریلیون یال یافته است که بر روی یک کامپیوتر واحد و بدون ذخیرهسازی گراف در حافظه اصلی و یا روی دیسک انجام میشود.
“Develop” یا “توسعه” واژهی مهمی در این کار محسوب میشود، چرا که این تحقیق بهجای دادههای بزرگ واقعی، الگوریتمهای اصلاح کردن (honing) را بر روی مجموعهای از دادههای مصنوعی، پوشش میدهد.
برطبق Kiast، “گرافها بهطور گسترده برای نمایش و تحلیل اشیای جهان واقعی در بسیاری از حوزهها مانند شبکههای اجتماعی، هوش تجاری، زیستشناسی و علوم اعصاب بهکار میروند.” “هنگام توسعه و تست الگوریتمها برای یک گراف با مقیاس بزرگ، معمولاً از یک گراف مصنوعی (ساختگی) بهجای یک گراف واقعی استفاده میشود. این کار به این دلیل صورت میگیرد که بهاشتراک گذاری و استفاده از گرافهای واقعی با مقیاس بزرگ، بسیار محدود است که بدلیل انحصاری بودن و غیر عملی بودن جمعآوری آنها است.”
طبق گفته Kiast، معمولاً توسعه و تست الگوریتمهای گراف از طریق رویکرد دو مرحلهای زیر انجام میشود:
در مرحله اول، یک گراف مصنوعی تولید و روی دیسکها ذخیره میشود. این گراف معمولاً از طریق تولید مبتنی بر پارامتر و یا افزایش مقیاس گراف بهوجود میآید- مورد اول، تعداد کمی از پارامترهایی را استخراج میکند که میتواند برخی از ویژگیهای یک گراف واقعی داده شده را بدست آورد و یک گراف مصنوعی با استفاده از این پارامترها تولید کند؛ مورد بعدی، به منظور حفظ ویژگیهای گراف واقعی اصلی تا حد ممکن، یک گراف واقعی داده شده را به یک گراف با مقیاس بزرگتر تبدیل میکند.
در مرحله دوم، گراف ذخیره شده در حافظه اصلی یک موتور پردازش گراف مانند Apache Graph X، بارگذاری شده و الگوریتم گراف داده شده روی موتور اجرا میشود. Kiast میگوید: “از آنجا که این گراف بسیار بزرگتر از آن است که در حافظه اصلی یک کامپیوتر واحد قرار گیرد، معمولاً موتور گراف بر روی کلاستری متشکل از دهها یا صدها کامپیوتر اجرا میشود”، “از این رو، رویکرد دو مرحلهای مرسوم، هزینه بالایی دارد.”
طبق تحقیقات این گروه کرهای، یک گراف مصنوعی با مقیاس بزرگ، تولید و ذخیره نمیشود.
درعوض، گراف واقعی کوچک اولیه در حافظه اصلی بارگذاری میشود. سپس، با استفاده از تکنیکی بهنام T-GPS (شبیهسازی پردازش گراف با مقیاس تریلیون)، الگوریتم گراف با گراف واقعی کوچک مواجه شده، بهگونهای که انگار گراف مصنوعی با مقیاس بزرگ که باید از گراف واقعی تولید شود، در حافظه اصلی وجود دارد. پس از انجام الگوریتم، تکنیک T-GPS نتیجهای مشابه با رویکرد دومرحلهای مرسوم برمیگرداند.
طبق آنچه که Kiast میگوید، “ایده اصلی تکنیک T-GPS، تولید تنها بخشی از گراف مصنوعی است که الگوریتم برای دسترسی به آن نیاز به پرش (fly) و اصلاح (modifying) موتور پردازش گراف داشته باشد تا بتواند بخش تولید شده در پرش را بهعنوان بخشی از گراف مصنوعی که واقعاً تولید شده است، تشخیص دهد.”
تکنیک T-GPS، یک گراف متشکل از یک تریلیون یال را تنها بر روی یک کامپیوتر پردازش میکند، درحالیکه رویکرد دو مرحلهای مرسوم، برای پردازش گرافی با یک میلیارد یال، به یک کلاستر متشکل از یازده کامپیوتر با مشخصات یکسان نیاز دارد. تکنیک T-GPS بدون نیاز به دسترسی به شبکه، 43 برابر سریعتر از رویکرد مرسوم است که سربار ارتباطی قابل توجهی هم دارد.
این کار تحقیقی در کنفرانس IEEE ICDE 2021 conference با عنوان “شبیهسازی پردازش گراف با مقیاس تریلیون مبتنی بر افزایش مقیاس گراف بهصورت بالا به پایین (Top-Down)” ارائه شده است.