ترجمه مقاله جستجوهای تجمعی (انبوه) توزیع شده top-k در سطح کلان (بزرگ) – نشریه اشپرینگر

عنوان فارسی: | جستجوهای تجمعی (انبوه) توزیع شده top-k در سطح کلان (بزرگ) |
عنوان انگلیسی: | Distributed top-k aggregation queries at large |
تعداد صفحات مقاله انگلیسی : 23 | تعداد صفحات ترجمه فارسی : 42 |
سال انتشار : 2009 | نشریه : اشپرینگر - Springer |
فرمت مقاله انگلیسی : PDF | فرمت ترجمه مقاله : ورد تایپ شده |
کد محصول : 5333 | رفرنس : دارد |
محتوای فایل : zip | حجم فایل : 2.04Mb |
رشته های مرتبط با این مقاله: مهندسی کامپیوتر، مهندسی صنایع |
گرایش های مرتبط با این مقاله: مهندسی الگوریتم و محسابات، تحلیل و بهینه سازی سیستم ها، شبکه های کامپیوتری |
مجله: توزیع و پایگاه داده موازی |
دانشگاه: موسسه ماکس پلانک برای علوم کامپیوتر، زاربروکن آلمان |
کلمات کلیدی: top-k، جستجوهای توزیعشده، بهینهسازی جستجو، مدلهای هزینه |
وضعیت ترجمه عناوین تصاویر و جداول: ترجمه شده است |
وضعیت ترجمه متون داخل تصاویر و جداول: ترجمه نشده است |
وضعیت فرمولها و محاسبات در فایل ترجمه: به صورت عکس، درج شده است |
چکیده
1. مقدمه
1.1. انگیزه و بیان مسئله
1.2. مدل محاسباتی، فرضیات
1.3 نقش و طرح کلی مقاله
2 کارهای مرتبط
3 چهارچوب پردازش جستجو
4 پیشبینی هزینه
4.1 تخمین تعداد آیتمهای انتقالیافته
4.2 تخمین هزینههای شبکه
5 گروهبندی سلسله مراتبی و بهینهسازی آن
5.1 روش برنامهنویسی پویا
5.2 هیوریستیک سریع
6 آستانههای تطبیقی
7 نمونهبرداری مکانی
7.1 تخمین min-k(m,n)
7.2 تخمین min-k(m´,n´)
8 خرابی گرهها و پویایی شبکه
9 آزمایشها
9.1 آماده¬سازی
الگوریتمهای مورد مقایسه
حالت تقریبی در مقابل حالت دقیق
مجموعه دادهها
معیارهای عملکرد
9.2 نتایج
9.3 دقت پیشبینی
9.4 بحث
10 نتیجهگیری و کارهای آتی
Abstract
Top-k query processing is a fundamental building block for efficient ranking in a large number of applications. Efficiency is a central issue, especially for distributed settings, when the data is spread across different nodes in a network. This paper introduces novel optimization methods for top-k aggregation queries in such distributed environments. The optimizations can be applied to all algorithms that fall into the frameworks of the prior TPUT and KLEE methods. The optimizations address three degrees of freedom: 1) hierarchically grouping input lists into top-k operator trees and optimizing the tree structure, 2) computing data-adaptive scan depths for different input sources, and 3) data-adaptive sampling of a small subset of input sources in scenarios with hundreds or thousands of query-relevant network nodes. All optimizations are based on a statistical cost model that utilizes local synopses, e.g., in the form of histograms, efficiently computed convolutions, and estimators based on order statistics. The paper presents comprehensive experiments, with three different real-life datasets and using the ns-2 network simulator for a packet-level simulation of a large Internet-style network.
چکیده
در بسیاری از کاربردها، پردازش جستجو top-k یک بلوک سازنده اساسی برای رتبهبندی بهینه و کارا است. کارایی یک مسئله مهم است، بهویژه برای محیطهای توزیعشده، هنگامیکه داده در میان گرههای مختلف در یک شبکه گسترش یافته است. این مقاله روشهای بهینهسازی جدیدی را برای جستجوهای تجمعی top-k در چنین محیطهای توزیعشدهای معرفی میکند. بهینهسازیها را میتوان به تمام الگوریتمهایی که در چهارچوب روشهای قبلی TPUT و KLEE قرار دارند، اعمال کرد. بهینهسازیها سه درجه آزادی را ارائه میدهند: 1) دستهبندی سلسله مراتبی لیست ورودیها به درختهای عملگر k-top و بهینهسازی ساختار درخت، 2) محاسبه عمق اسکن تطبیقی داده برای منابع ورودی مختلف و 3) نمونهبرداری تطبیقی داده زیرمجموعه کوچکی از منابع ورودی در طرحهایی با صدها یا هزاران گره شبکه مرتبط با جستجو. تمام بهینهسازیها بر اساس یک مدل هزینه آماری هستند که از سیناپسهای محلی، برای مثال، بهصورت نمودارهای هیستوگرام، کانولوشنهای محاسبهشده بهصورت بهینه و تخمین گرهایی مبتنی بر آمار ترتیبی استفاده میکند. این مقاله آزمایشهای جامعی را با سه مجموعه داده زندگی واقعی متفاوت و استفاده از شبیهساز شبکه ns-2 برای شبیهسازی در سطح کوچک یک شبکه اینترنتی بزرگ ارائه میدهد.