ارسل ملاحظاتك

ارسل ملاحظاتك لنا







الرئيسية > MSP: Multiple Sub Graph Query...>الوصف
يجب تسجيل الدخول أولا

MSP: Multiple Sub Graph Query Processing Using Structure Based Graph Partitioning Strategy And Map Reduce

المصدر: مجلة جامعة الملك سعود - علوم الحاسب والمعلومات
الناشر: جامعة الملك سعود
المؤلف الرئيسي: Fathimabi, Shaik (Author)
مؤلفين آخرين: Subramanyam, R. B. V. (Co-Author) , Somayajulu, D. V. L. N. (Co-Author)
المجلد/العدد: مج31, ع1
محكمة: نعم
الدولة: السعودية
التاريخ الميلادي: 2019
الصفحات: 22 - 34
DOI: 10.33948/0584-031-001-003
ISSN: 1319-1578
رقم MD: 974532
نوع المحتوى: بحوث ومقالات
اللغة: الإنجليزية
قواعد المعلومات: science
مواضيع:
قواعد البيانات | الرسوم البيانية | الخوارزميات
كلمات المؤلف المفتاحية:
Graph Database | Big Data | Structure Based Graph Partitioning | Parallel Processing | Map-Reduce | Integrated Graph Inde
رابط المحتوى:
PDF (صورة)     
صورة الغلاف QR قانون
حفظ في:
المستخلص: In a distributed environment, the volume of graph database increases quickly because graphs emerge from several autonomous sources. Sub graph query processing is a challenging problem in distributed environment. Centralized approaches proposed many algorithms, they mine frequent subgraphs from the graph database and construct an index which is very expensive. These algorithms require more number of database scans to mine frequent subgraphs and they use filter and verify approach, which requires many subgraph isomorphism tests. In this paper, we design a novel Map-Reduce based multiple subgraph query processing framework, namely MSP. MSP processes multiple graph queries using distributed index. The framework completely relies on the graph partition and indexing. Moreover, in order to improve its performance, we propose several solutions to balance the workload and reduce the size of Integrated Graph Index. We propose a structure-based partitioning technique and distributed way of building Integrated Graph Index. This work uses two Map-Reduce rounds, the first Map-Reduce round partitions the graphs and creating index for each partition, second Map-Reduce round processes sub-graph queries and index maintenance. A good partitioning will reduce the index size by distributing the load equally to the machines in the cluster and improves the performance of query evaluation. This graph partition and Integrated Graph Index reduces the search space of query graphs. Our approach allows to add data graphs incrementally to Integrated Graph Index while doing query processing. We experimentally show that our approach decreases remarkably the execution time and scales the subgraph query processing to large graph databases. © 2016 The Authors. Production and hosting by Elsevier B.V. on behalf of King Saud University. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
ISSN: 1319-1578

عناصر مشابهة


© 2024 المنظومة. جميع الحقوق محفوظة.