دانلود رایگان ترجمه مقاله بهینه سازی پرس و جو تطابقی الگوی توزیع شده – IEEE 2014

مقاله انگلیسی رایگان

ترجمه فارسی رایگان 

فهرست مقاله:

چکیده
مقدمه
مقدمات
تطبیق الگوی زیر گراف
پارتیشن بندی داده ها و الحاق
بهینه سازی مبتنی بر برنامه نویسی دینامیک
برنامه های خطی
ج:طرح های نقطه ای
تبدیل
تولید طرح های نقطه ای
براورد هزینه
ارزیابی آزمایشی
ب:عملکرد تطبیق ساختاری
عملکرد تطبیق معنایی
عملکرد مثلث یابی

بخشی از ترجمه فارسی مقاله:

چکیده: الگوریتم های حریصانه برای عملیات تطبیق الگوی گراف اغلب زمانی که دده های گراف را بتوان در حافظه بر روی تک ماشین نگه داری کرد کافی می باشد. با این حال، چون مجموعه داده های گراف به طور فزاینده ای توسعه می یابند و نیاز مند فضای ذخیره ای اضافی و پارتیشن بندی در دسته ای از ماشین ها می باشند، فنون بهینه سازی پرس و جوی پیشرفته تر برای اجتناب از انفجار در تاخیر پرس و جو اهمیت حیاتی دارد.در این مقاله، ما اقدام به معرفی روش های بهینه سازی پرس و جو برای تطبیق الگوی گراف توزیع یافته می کنیم. این فنون شامل، ۱- الگوریتم بهینه سازی مبتنی بر برنامه نویسی دینامیک سبک سیستم R، که هر دو برنامه های خطی و نقطه ای را در نظر می گیرد، ۲- الگوریتم مبتنی بر تشخیص چرخه که اهرمی برای چرخه ها جهت کاهش اندازه مجموعه های نهایی می باشد و ۳- روش استفاده مجدد از محاسبه یا رایانش است که انتقال اطلاعات و اجرای پرس و جوی زائد را در شبکه حذف می کند. نتایج آزمایشی نشان می دهد که این الگوریتم ها می توانند موجب بهبود زیادی در عملکرد پرس و جو شوند.
۱-مقدمه
مدل داده های گراف، یک شیوه بسیار محبوب برای زمینه های مختلف محسوب می شود. از دلایل این محبوبیت می توان به موارد زیر اشاره کرد:۱- برای خلاصه سازی داده های پراکنده و یا نیمه ساختاری به مدل های داده های راس-لبه-راس نسبت به مدل های داده های سنتی ساده تر است ۲- برخی از مجموعه داده های محبوب( نظیر شبکه های تویتر، فیسبوک و لینکدین) در مورد استفاده از پارادایم گراف منطق و استدلال طبیعی دارند و ۳- عملیات گراف نظیر محاسبات با کوتاه ترین مسیر،، تطبیق الگوی زیر گراف و پیج رنک به آسانی نسبت به مدل داده های گراف بیان می شوند.
بسیاری از مجموعه داده های گراف آن قدر بزرگ هستند که مدیریت آن ها بر روی یک ماشین سخت بوده و از این روی دسته ای از ماشین ها برای پردازش، ذخیره، مدیریت و تحلیل داده های گراف به کار برده می شوند. برای مثال، از سال ۲۰۱۲، گراف کاربر فیسبوک دارای ۹۰۰ میلیون راس( درجه متوسط راس، ۱۳۰ است) می باشد(۱). در جامعه وب معنایی، جنبش داده های اپن لینکینگ، ۶ میلیون تریپل را ( یک تریپل، برابر باست با یک لبه در یک گراف) از ۳۰۰ مجموعه داده به هم پیوسته جمع اوری کرده است. از آن جا که بسیاری از الگوریتم های گراف در اصل با این فرض طراحی شده اند که گراف کامل را می توان در مموری بر روی یک ماشین ذخیره سازی کرد، معماری های توزیع یافته فوق نیاز به بازبینی این الکوریتم ها در زمینه توزیعی می باشند زیرا ملاحظاتی نظیر نهفتگی شبکه و بازدهی می تواند مانع از اجرای متعارف این الگوریتم ها شود.
تطبیق الگوی زیر گراف یک عملیات بسیار مهم می باشد که باید برای ذخایر گراف توزیعی باز بینی شود. عملیات تطبیق زیر گراف در عملیات داده کاوی شبکه اجتماعی( شمارش مثلث ها برای اندازه گیری اثر اجتماعی مراسم ها)، پرس و جو هایSPARQL در گراف داده های لینک شده و الگوریتم های یادگیری ماشین که موجب راه اندازی موتور ها برای سرگرمی و ابزار های تجارت الکترونیکی به شدت استفاده می شود.
مقاله حاضر به طور صریحی از روش های برنامه نویسی دینامیک سبک سیستم r استفاده می کند تا تطبیق الگوی زیر گراف توزیعی را بهینه سازی کند. با این حال، پی برده شد که این الگوریتم های متعارف باید به سه طریق اصلاح شوند تا عملکرد خوبی برای داده های گراف داشته باشند.
• اگرچه سایرین خاطر نشان کرده اند که حتی در زمینه های نسبی متعارف، مسئله سیستم R از درختان منجر به راهبرد بهینه سازی نیمه بهینه می شود، در نظر گرفتن برنامه های نقطه ای برای پرس و جو های تطبیق الگوی گراف توزیعی از اهمیت زیادی برای کاهش ترافیک شبکه و اندازه خروجی های میانی برخوردار است. بحی اکتشافی که برای آن ها طرح های نقطه ای در نظر گرفته می شوند باید اهرم خصوصیات گراف باشد.
• چرخه ها به طور مکرر در الگوهای پرس و جو در مدل گراف نسبت به داده های نشان داده شده در مدل های دیگر ظاهر می شوند. آن ها را می توان طوری اهرم بندی کرد که موجب بهبود عملکرد پرس و جو شده و به طور صریح طی تولید برنامه در نظر گرفته شوند.
• به طور کلی، تطبیق الگوی توزیعی زیر گراف با یافتن مولفه هایی از زیر گراف و اتصال این مولفه ها به هم انجام می شود. با این حال وقتی که الگوهای گراس خالص مورد جست و جو باشند، مجموعه های میانی حاصله، اندازه شان بزرگ تر می شود.
در این مقاله، ما دو قالب بهینه سازی پرس و جو را برای تطبیق الگوی زیر گراف ارایه می دهیم. با توجه به ذخیره داده ها در مدل داده های گراف، و پرس و جویی که همه نمونه های الگوی گراف را درون ذخیره گاه داده ها درخواست می کند،الگوریتم هایی را فراهم می کنیم که یک سری طرح های اجرای پرس و جو را تولید کرده، هر یک از طرح ها را براورد کرده و طرحی را با کم ترین هزینه برای اجرا انتخاب می کنند. هیچ گونه فرضی در مورد چگونگی تقسیم داده های گراف در خوشه وجود ندارد به جز این که همه لبه های بر گرفته از ورتکس در یک ماشین فیزیکی ذخیره شده و یک تابع قطعی ( تابع نقطه ای) را می توان به لبه ها برای تعیین مکان آن اعمال کرد. به علاوه، ما هیچ گونه فرضی را در مورد زیر گراف ارایه نداده و الگوریتم ما به دو زیر گراف غیر توزیعی و توزیعی نسبت داده می شود( که هر لبه و راس در مجموعه داده های گراف دارای خصوصیات مربوط به آن بوده و زیر گراف می تواند شامل گزاره هایی در خصوص این صفات برای کاهش حوزه پژوهش باشد. اهمیت مطالعه ما در زیر اشاره شده است.
• ما یک قالب بهینه سازی مبتنی بر برنامه نویسی دینامیک را پیشنهاد می کنیم که تنها طرح های نقطه ای را بدون مواجه با انفجار فضای برنامه پرس و چو در نظر می گیرد.
• ما یک چارچوب بهینه سازی مبتنی بر تشخیص چرخه را بر اساس این مشاهده ارایه می دهیم که چرخه ها به طور معنی داری، اندازه مجموعه های متوسط نهایی را کاهش می دهند.
• ما یک روش استفاده مجدد از محاسبات و رایانش را ارایه می دهیم که اجرای زیر پرس و جوی مشابه و انتقال شبکه زائد مجموعه متوسط را در پرس و جو حذف می کند.
نتایج آزمایشی نشان می دهد که روش های پیشنهادی ما، عملکرد تطبیق الگوی زیر گراف را در یک ذخیره گراف توزیعی به ترتیب بزرگی در الگوریتم های حریصانه بهبود بخشیده و منجر به افزایش عملکرد می شود.

بخشی از مقاله انگلیسی:

Abstract

Greedy algorithms for subgraph pattern matching operations are often sufficient when the graph data set can be held in memory on a single machine. However, as graph data sets increasingly expand and require external storage and partitioning across a cluster of machines, more sophisticated query optimization techniques become critical to avoid explosions in query latency. In this paper, we introduce several query optimization techniques for distributed graph pattern matching. These techniques include (1) a System-R style dynamic programming-based optimization algorithm that considers both linear and bushy plans, (2) a cycle detection-based algorithm that leverages cycles to reduce intermediate result set sizes, and (3) a computation reusing technique that eliminates redundant query execution and data transfer over the network. Experimental results show that these algorithms can lead to an order of magnitude improvement in query performance.

I. INTRODUCTION

The graph data model is becoming an increasingly popular way to represent data for various applications. Reasons for this include: (1) It can be less complex for a user to shoehorn semi-structured or sparse data into a vertex-edge-vertex data model than a relational data model, (2) some increasingly popular data sets (such as the Twitter, Facebook, and LinkedIn social networks) are most naturally reasoned about using a graph paradigm, and (3) graph operations, such as shortest path calculations, subgraph pattern matching, and PageRank are easily expressed over a graph data model. Many graph data sets are becoming too large to manage on a single machine, and therefore clusters of machines are being deployed to process, store, manage, and analyze graph data. For instance, as of 2012, Facebook’s user graph has 900 million vertices (and the average degree of a vertex is 130) [1]. In Semantic Web community, the Linking Open Data movement has collected 6 billion triples (a triple is equivalent to an edge in a graph) from 300 interconnected data sets [3]. Since many graph algorithms were originally designed with the assumption that the entire graph can be stored in memory on a single machine, these distributed architectures require revisiting these algorithms in a distributed context, as considerations such as network latency and throughput can bottleneck the traditional implementation of these algorithms. Subgraph pattern matching is a particularly important operation that must be revisited for distributed graph stores. Subgraph matching operations are heavily used in social network data mining operations (e.g. counting triangles for gauging social influence of celebrities [33]), SPARQL queries over the Linked Data graph, and machine learning algorithms that power recommendation engines for e-commerce retail applications and entertainment choices. This paper is the first (to the best of our knowledge) to explicitly use System-R style dynamic programming techniques [30] in order to optimize distributed subgraph pattern matching. However, we find that these traditional algorithms need to be modified in three ways in order to work well for graph data: • Although others have noted that even in the traditional relational context, System-R’s consideration of only left-deep join trees can lead to a suboptimal optimization strategy [21], the consideration of bushy plans for distributed graph pattern matching queries is particularly important in order to reduce network traffic and sizes of intermediate output. The heuristics for which bushy plans to consider should leverage graph characteristics. • Cycles appear more frequently in query patterns over a graph model than data represented in other models. They can be potentially leveraged to improve query performance and should be explicitly considered during plan generation. • In general, distributed subgraph pattern matching is performed by finding components of the subgraph separately, and joining these components together. However, when pure graph patterns are being searched for (without any selection predicates on vertex or edge attributes), the intermediate result sets tend to be extremely large. In this paper we introduce two query optimization frameworks for subgraph pattern matching. In particular, given a data store represented in the graph data model, and a query that requests all instances of a particular graph pattern within the data store, we provide algorithms that generate a series of query execution plans, estimate the cost of each of these plans, and select the plan with lowest cost for execution. We make no assumptions about how the graph data is partitioned across a cluster, except that all (directed) edges emanating from the same vertex are stored on the same physical machine, and that a deterministic function (e.g. a hash function) can be applied to any edge in order to determine its location. Furthermore, we make no assumptions about the subgraph being matched — our algorithms apply to both unattributed subgraphs (where just the structure of the graph pattern is being matched) and attributed subgraphs (where each vertex and edge in the graph data set may have attributes associated with it, and the subgraph may include predicates on these attributes in order to reduce the scope of the search). Our work makes the following contributions: • We propose a dynamic programming-based optimization framework that considers bushy plans without encountering query plan space explosion (Section III). We propose an cycle detection-based optimization framework based on the observation that cycles tend to significantly reduce the size of intermediate result sets (Section IV). • We introduce a computation reusing technique which eliminates repetitive identical subquery execution and redundant network transfer of intermediate result sets within a query (Section VI). Our experimental results show that our proposed techniques improve performance of subgraph pattern matching in a distributed graph store by an order of magnitude over commonly used greedy algorithms, and often result in even larger performance gains.