یک رویکرد ترکیبی جهت کاهش پیچیدگی زمانی الگوریتم پرس و جوهای K- بالاترین بر جریان های داده ایی

پردازش مؤثر پرس و جوهای k- بالاترین، یک نیاز حیاتی برای بسیاری از محیط های تعاملی با توده های عظیم داده ایی مثل سیسیتم های اطلاعاتی جغرافیایی، شبکه های حسگر بی سیم و غیره است. در این سیستم ها، کاربران معمولا علاقه مند به مهم ترین نتایج یک پرس و جو در بین پاسخ های بالقوه وسیع هستند. سیستم های مختلف از روش های متفاوتی برای رتبه بندی نتایج پرس و جو استفاده کرد و مهم ترین نتایج را اعلام می کنند. در پرس و جو های سنتی k- بالاترین، رتبه بندی نتایج بر اساس امتیاز اشیاء داده ایی صورت می گیرد و k شی با بالاترین رتبه گزارش می شود. در بعضی از کاربردها، رتبه بندی نتایج بر اساس امتیاز زوج اشیاء داده ایی انجام می شود و k زوج شیء با بالاترین رتبه گزارش می شود. در سال های اخیر، در کنار پایگاه های داده، شاهد پدیده جریان های داده ایی بسیار بزرگ با سرعت بالا هستیم. یک جریان داده ایی، دنباله ایی متوالی و بلادرنگ از توده های عظیم داده است. چالش اصلی این سیستم ها ورود پیوسته اجزاء داده ایی است و به دلیل حجم بالای داده ها، نمی توان همه آنها را برای پردازش های برخط در حافظه اصلی و یا حتی در دیسک محلی ذخیره کرد. به دلیل ماهیت نامحدود جریان های داده ایی، برای کاهش اندازه و ایجاد محدودیت بر جریان های داده ایی تاکنون چند مدل ارائه شده است که یکی از آن ها، مدل پنجره لغزان است. در این مدل فقط اشیاء داده ایی اخیر یک جریان داده ایی جهت پردازش پرس و جوها نگهداری می شود. در این مقاله، یک راه کار ترکیبی جهت کاهش زمان پردازش پرس وجوهای k- بالاترین زوج اشیاء بر جریان های داده ایی مبتنی بر پنجره لغزان ارائه می شود.

Keywords:

پرس و جو , جریان داده ایی , k- بالاترین زوج اشیاء , پنجره لغزان و K-skyband