| عنوان فارسی مقاله: | برچسب گذاری موازی داده های انبوه XML با مپ ردیوس |
| عنوان انگلیسی مقاله: | Parallel labeling of massive XML data with MapReduce |
| دانلود مقاله انگلیسی: | برای دانلود رایگان مقاله انگلیسی با فرمت pdf اینجا کلیک نمائید |
| سال انتشار | 2014 |
| تعداد صفحات مقاله انگلیسی | 30 صفحه |
| تعداد صفحات ترجمه مقاله | 49 صفحه |
| مجله | مجله ابر محاسبات |
| دانشگاه | کره |
| کلمات کلیدی | محاسبه موازی، XML ، الگوریتم برچسب گذاری درختی، مپ ردیوس |
| نشریه | Springer |
فهرست مطالب:
چکیده
۱ مقدمه
۲ کلیات
۱ ۲ طرحهای برچسب گذاری درختی و XML
۱ ۱ ۲ طرح برچسب گذاری بر مبنای بازه
۲ ۱ ۲ طرح برچسب گذاری بر مبنای پیشوند
۲ ۲ مپ ردیوس
۳ برچسب گذاری موازی XML با مپ ردیوس
۱ ۳ تقسیم داده های XML با XMLInput format
۲ ۳ الگوریتم برچسب گذاری موازی بر مبنای بازه
۳ ۳ الگوریتم برچسب گذاری موازی بر مبنای پیشوند
۴ بهینه سازیها
۱ ۴ توازن حجم کاردر زمان اجرا
۲ ۴ پارتیشن بندی یا بخش بندی مجدد داده ها
۵ مطالعه عملکرد
۱ ۵ راه اندازی آزمایش
۲ ۵ تحلیل عملکرد
۳ ۵ بهینه سازی
۶ کارهای وابسته
۷ نتیجه گیری
بخشی از ترجمه:
۱ مقدمه
در حال حاضر XML یکی از مشهورترین فرمت های داده برای نمایش و انتقال داده ها برروی اینترنت می باشد. به خاطر طبقه بندی حجم زیادی از داده ها در XML ، حجم یک سند XML نیز افزایش یافته و به سرعت نیز رشد می کند. به طور مثال، ویکی پدیا از صفحه به عنوان یک سند XML رونوشت برمی دارد که اندازه آن بیش از ۴۰GB می باشد. بیشتر اوقات شاهد اسناد بزرگ XML در بخشهای علمی هستیم. به طور مثال، یونیت پرت KB که مجموعه ای از روابط تابعی بین پروتئین ها را عرضه می کند، حال هدف آن بیش از ۱۰۸ GB می باشد. به علاوه، اندازه سند XML دائماً رو به رشد می باشد زیرا زیست شناسایی حقایق جدیدی پیرامون پروتئین ها در آزمایشاتشان بدست می آورند. در نتیجه تقاضای زیادی برای حمایت از پردازش پرس و جو در اسناد بزرگ XML وجود دارد.
ضمناًف برچسب گذاری یک سند XML اولین و کلیدی ترین مرحله در پردازش پرس و جوی XML محسوب می شود. الگوریتم های برچسب گذاری درختی از طریق تخصیص برچسبی منحصر به فرد به هر گره در درختی که یک سند XML نشان دهنده آن است، روند پردازش پرس و جوی XML را تسهیل می نمایند. رابطه ساختاری بین دو گره درختی از طریق مقایسه دو برچسبی شناسایی می شود که نظیر گره ها می باشند. بدون الگوریتم های برچسب گذاری درختی، پردازش پرس و جوی XML می تواند سخت تر شود چرا که هیچ حق انتخابی وجود ندارد، اما برای پیمایش کلیه گره ها در یک درخت XML برای یافتن کلیه رخدادهای الگوی زیردرختی که یک پرس و جوی خاص نشان دهنده آن است، به آن نیاز می باشد.
اما الگوریتم های برچسب گذاری درختی معمولی همگی ترتیبی هستند. این امرشامل تاخیرها یا توقف های جدی در پردازش پرس و جو می باشد چرا که سیستم برای ادامه فرایند برچسب گذاری اش بدون پردازش پرس و جوی حقیقی، به زمان غیر قابل تحملی نیاز دارد. در نتیجه، الگوریتم های معمولی به موقع نمی توانند سند حجیم XML را برچسب گذاری کنند. به منظور ارائه منطق فراتر از این ادعا، دو طرح برچسب گذاری درختی مشهور را تست کردیم، به عبارتی طرح های برچسب گذاری بر مبنای پیشوند و بازه.
7. نتیجه گیری
برچسب گذاری XML یک عملیات ضروری برای پردازش پرس و جوی کارآمد XML محسوب می شود. در این مقاله، الگوریتم های برچسب گذاری موازی XML برای دو طرح برچسب گذاری درختی غالب با مپ ردیوس پیشنهاد کردیم. الگوریتم ها حجم وسیعی از داده های XML را به صورت موازی برچسب گذاری می کنند. اما، اسناد XML ممکن است توزیعی نامتعادل از فراوانی های عنصر و تعداد کمی از نامهای برچسب متمایز داشته باشند. این امر باعث می گردد پردازش برخی از گره ها با تعداد زیادی عنصر XML به تاخیر بیفتد. با تکنیک های بهینه سازی، الگوریتم های برچسب گذاری موازی، حجم وسیعی از داده های XML را به شیوه ای متوازن و مقیاس پذیر، برچسب گذاری می کنند.
بخشی از مقاله انگلیسی:
1 Introduction
XML is currently one of the most popular data formats for data representation andtransmission on the Internet [9]. As many data have been typed in XML, the volumeof a single XML document has also become enormous and also grows very quickly.For example, Wikipedia provides page dumps as a single XML document that sizesover 40 GBytes [4]. It is more often to witness large XML documents in scientific areas.For instance, UnitprotKB, which provides a collection of functional relationshipsbetween proteins, now hits more than 108 GBytes a file [5]. Moreover, the size of theXML document is continuously growing as biologists find new facts on the proteinsin their experiments. Consequently, there is a growing demand for the support ofquery processing over a large XML document.Meanwhile, labeling an XML document is the first and crucial step in XML queryprocessing. Tree labeling algorithms facilitate XML query processing by assigning aunique label to each node in a tree that an XML document represents [19, 29, 30].A structural relationship between two tree nodes is simply identified by comparingtwo labels that correspond to the nodes.Without tree labeling algorithms, XML queryprocessing could be harder since there is no choice, but to traverse all nodes in anXML tree to find all occurrences of the subtree pattern that a given query represents.However, conventional tree labeling algorithms are all sequential. This involves serious delays or halt in query processing as a system requires unbearable time to proceedits labeling process before actual query processing. Consequently, conventionalalgorithms can no longer label a massive XML document in a timely manner. To providea rationale behind this assertion, we tested two popular tree labeling schemes,i.e., interval-based and prefix-based labeling schemes. We delicately implementedtwo labeling algorithms in Java. Figure 1 presents the result of this mini-test, whichwas performed on a Linux machine equipped with an AMD FX-4100 3.6 GHz processor,8 GB memory, and a 7200 RPM HDD. In the test, all the labeling algorithmsfailed to label given XML files in a proper time. Specifically, the interval-based labelingalgorithm spent approximately 5.56 hours (20,000 seconds) for labeling an XMLdocument that consists of 4,894 million nodes. Note that we labeled both elementsand attributes in the test. single large XML file in parallel. First, we provide MapReduce-based algorithms fortwo prominent tree labeling schemes. Then we present two optimization techniquesfor solving performance issues caused by data skewness and MapReduce’s inheritedlimitations. Note that dynamic labeling techniques for XML document updates areout of scope in this article.The key contributions of our approach are summarized as follows:1. We provide an efficient method to parallelize conventional tree labeling algorithmswith MapReduce. In other words, we provide an efficient way to tailor conventionaltree labeling algorithms to fit the MapReduce programming model.2. In our approach, elements are naturally grouped by tag name. In addition, elementswith the same tag name are sorted in an ascending order of labels after thelabeling process. This is just the same as the input type used in most of holistictwig join algorithms such as TwigStack [10]. Therefore, the results of our labelingalgorithms are directly used for twig pattern joins with no more efforts.3. In the MapReduce programming model, an input is partitioned into many equalsizedblocks with no semantic knowledge about its input data. This makes it difficultto label XML elements in parallel.We provide a method for keeping structuralinformation of an XML document during the labeling process.4. We also present optimization techniques to address performance issues in MapReduce.The skewed distribution of key-value pairs in input data may harm the overallperformance of a MapReduce-based algorithm as the data skewness makesMapReduce tasks have imbalanced workloads.We address this performance issueby providing both a sophisticated runtime workload balancing and data repartitiontechniques.5. We report results from a comprehensive set of experiments carried out to evaluateour MapReduce-based labeling algorithms in comparison with conventional treelabeling algorithms.The rest of this article is organized as follows. Section 2 explains preliminaryknowledge useful for better understanding of our work. Section 3 presents our parallellabeling techniques based on the MapReduce framework. Section 4 describesoptimization techniques to alleviate a data skewness problem in labeling massiveXML data. In Sect. 5, we extensively evaluate the performance of our parallel labelingalgorithms with various datasets. Section 6 introduces previous work related toour approach. Finally, we conclude this article in Sect. 7.
| عنوان فارسی مقاله: | برچسب گذاری موازی داده های انبوه XML با مپ ردیوس |
| عنوان انگلیسی مقاله: | Parallel labeling of massive XML data with MapReduce |
خرید ترجمه فارسی مقاله با فرمت ورد