The amount of applications calling for efficient large graph management is dramatically increasing. Social network analysis, Internet or biocomputation are just three examples of such applications. In these cases, the interest focuses on the structural analysis of the relationships between different entities organized in huge networks or graph-like structures. Being able to efficiently handle such graphs becomes essential, placing graph database management systems in the eye of the storm. Among the different challenges posed by graph databases, finding an efficient way to represent and manipulate huge graphs that do not entirely fit in memory is still an unresolved problem. In this work, we present DEX, a high performance graph database management system based on bitmaps and other secondary structures. We show that by using bitmap structures for graph representation it is possible to improve the performance of a graph database system, allowing for the efficient manipulation of very large graphs containing thousands of millions of nodes and edges

چکیده

میزان برنامه‌های کاربردی که برای مدیریت گراف بزرگ کارا فراخوانی می‌شوند، به طور چشمگیری در حال افزایش است. تحلیل شبکه‌ی اجتماعی، اینترنت یا محاسبات زیستی فقط سه مثال از چنین برنامه‌هایی هستند. در این موارد، علاقه به تمرکز روی تحلیل ساختاری رابطه‌ی بین موجودیت های مختلف سازمان‌دهی شده در شبکه‌های بزرگ یا ساختارهای شبه گراف است. ضرورت قادر بودن به کنترل چنین گراف‌هایی، سیستم‌های مدیریت پایگاه‌داده‌ را مورد توجه قرار می‌دهد. در بین چالش‌های مختلف ایجاد شده توسط پایگاه‌داده‌های گراف، یافتن یک روش کارا برای نمایش و دستکاری گراف‌های یزرگ که کاملاً متناسب با حافظه نیستند، هنوز یک مسئله‌ی حل نشده است. در این کار، ما DEX را ارائه نموده‌ایم که یک سیستم مدیریت پایگاه‌داده‌ی گراف بر مبنای بیت‌مپ ها و دیگر ساختارهای ثانویه می‌باشد. ما نشان می دهیم که با استفاده از ساختار بیت‌مپ برای نمایش گراف، می‌توان کارایی یک سیستم پایگاه‌داده‌ی گراف را بهبود بخشید و اجازه داد که دستکاری گراف‌های بسیار بزرگ شامل میلیون‌ها گره و یال به صورت کارا انجام پذیرد.  

1-مقدمه 

مقدار افزایش شبکه‌های بزرگ مانند اینترنت، سیستم‌های جغرافیایی و پایگاه‌داده‌های شبکه های اجتماعی، یا آن‌هایی که برای نمایش تعامل بین پروتئین‌ها در سیستم‌های بیولوژیکی ساخته شده اند، نیاز به مدیریت اطلاعات با ماهیت شبه گراف ذاتی را مشخص می نماید. به خصوص، مطالعه‌ی شبکه‌های مقیاس آزاد که با توزیع‌های قدرت پایین مشخص می‌شود، یکی از نواحی بسیار فعال تحقیقاتی در این زمینه است.  بنابراین علاقه به تحلیل رابطه‌‌ی بین موجودیت‌ها در این شبکه‌ها، به سرعت در حال افزایش است و روی ایجاد سیستم‌های مدیریت اطلاعاتی که قادر به انجام عملیات گراف-گرا به صورت کارا می‌باشد، تمرکز می‌کند...