پردازش کارآمد معکوس پیوسته k نزدیکترین همسایه بر روی اجسام متحرک در شبکه های جاده ای

خلاصه

یک جستار معکوس k نزدیکترین همسایه (Rk NN ) تمام نقاط داده ای را که q به عنوان یکی از k نزدیکترین نقاط آنهاست بازیابی می کند. در سال‌های اخیر، تحقیقات قابل‌توجهی برای نظارت بر پرس‌وجوهای معکوس k نزدیکترین همسایه انجام شده است . در این مقاله، ما مسئله پرس‌وجوهای نزدیک‌ترین همسایه معکوس پیوسته را که در آن هر دو شی پرس و جو q هستند، مطالعه می‌کنیمو اشیاء داده در حال حرکت هستند. تکنیک های پیشرفته موجود نسبت به جابجایی اشیاء داده حساس هستند، به عنوان مثال، یک شی کاندید باید هر زمان که مکان خود را تغییر می دهد تأیید شود. علاوه بر این، توجه کافی به نظارت بر جستارهای RNN در شبکه‌های جاده‌ای پویا که در آن وزن شبکه بسته به شرایط ترافیکی تغییر می‌کند، شده است. در این مقاله، ما این مشکلات را با پیشنهاد یک الگوریتم مبتنی بر خروج ایمن جدید به نام CORE-X برای محاسبه موثر نقاط خروج ایمن هر دو پرس و جو و اشیاء داده بررسی می کنیم. نقطه خروج ایمن یک شی نقطه ای را نشان می دهد که در آن منطقه امن و منطقه غیرایمن آن به هم می رسند، بنابراین مجموعه ای از نقاط خروج ایمن مرز منطقه امن را نشان می دهد. در منطقه امن، نتیجه پرس و جو بدون تغییر باقی می ماند به شرطی که پرس و جو و اشیاء داده در مناطق امن مربوطه خود باقی بمانند. نتایج آزمایش های گسترده انجام شده با استفاده از نقشه های راه واقعی نشان می دهد که الگوریتم پیشنهادی به طور قابل توجهی هزینه های ارتباطی و محاسباتی را در مقایسه با الگوریتم پیشرفته کاهش می دهد.

کلید واژه ها:

نظارت مستمر ؛ برنامه های کاربردی مبتنی بر مکان ؛ پرس و جوی معکوس نزدیکترین همسایه الگوریتم خروج ایمن ; محاسبات تلفن همراه ; شبکه جاده ای

1. معرفی

پیشرفت سریع فناوری در شبکه‌های بی‌سیم و توسعه دستگاه‌های دستی مجهز به فناوری تشخیص مکان (به عنوان مثال، تلفن‌های هوشمند و تبلت‌ها) خدمات مبتنی بر مکان را در دهه‌های گذشته رایج کرده است. این سیستم‌ها کاربردهای دنیای واقعی مانند بازی‌های واقعیت ترکیبی، برنامه‌ریزی استراتژی ارتش، نظارت بر اشیا در شبکه‌های حسگر بی‌سیم و خدمات اضطراری پیشرفته را امکان‌پذیر می‌کنند [ 1 ، 2 ]. حرکت مداوم اشیاء داده نیازمند تکنیک‌های جدید پردازش پرس و جو است که امکان به‌روزرسانی مکرر مکان را فراهم می‌کند. اگرچه تلاش قابل توجهی به پردازش پرس و جوی متحرک اختصاص داده شده است [ 3 ، 4 ، 5 ، 6 ، 7]، این مطالعات بر پرس و جوهای محدوده و پرس و جوهای نزدیکترین همسایه (NN) متمرکز شده اند. همچنان کمبود تحقیقاتی که به پرسش‌های نزدیک‌ترین همسایه معکوس پیوسته (RNN) رسیدگی می‌کند، وجود دارد. علاوه بر این، اکثر تحقیقات در فضای اقلیدسی انجام شده است، نه در یک شبکه جاده.

یک شی query q و مجموعه ای از اشیاء داده O (مثلاً مکان های اقامتی، رستوران ها و پمپ بنزین ها) را در نظر بگیرید. ما استفاده می کنیم

d i s t (o, q)

d i s t (o, o^{'})

برای نشان دادن کوتاه ترین فاصله از شی o تا پرس و جو q و یک شی داده دیگر o به ترتیب. یک جستار معکوس k نزدیکترین همسایه (Rk NN ) همه اشیاء داده را بازیابی می کند

o \in O

که q یکی از k نزدیکترین اشیاء آنهاست.

پرس و جوهای R k NN به طور کلی به دو نوع دسته بندی می شوند: پرس و جوهای معکوس k NN (MR k NN) تک رنگ و پرس و جوهای k NN معکوس دو رنگی (BR k NN). در MR k NN، تمام داده های متحرک و اشیاء پرس و جو از یک نوع هستند. کاربردهای پیوسته MR k NN شامل بازی‌های واقعیت ترکیبی است که هدف هر بازیکن شلیک به نزدیک‌ترین بازیکن است. هر بازیکن باید به طور مداوم RNN خود را کنترل کند تا از تیراندازی توسط بازیکنان دیگر جلوگیری کند. با توجه به یک مجموعه شی O و یک پرس و جو q ، پرس و جو MR k NN به طور رسمی به عنوان تعریف می شود

MR k NN (q) = {o \in O | q \in k NN (o)},

که در آن k NN( o ) مجموعه k NN o است .

بر خلاف پرس و جوهای MR k NN، در BR k NN، اشیاء پرس و جو و اشیاء داده به دو نوع مختلف شی تعلق دارند. کاربردهای پرس و جو پیوسته BR k NN شامل سیستم پشتیبانی تصمیم می باشد. برای مثال، اپلیکیشنی را در نظر بگیرید که هدف آن تعیین بهترین مکان برای افتتاح یک رستوران چینی است. عامل اصلی تصمیم گیری می تواند این باشد که “چند کاربر این مکان بالقوه را نزدیکترین رستوران غذای چینی می دانند؟” هر مکان نامزد برای رستوران غذای چینی یک درخواست RNN ایجاد می کند. سپس نتایج را می توان برای انتخاب بهترین مکان مقایسه کرد. مثال بالا از پرس و جوهای BR k NN استفاده می کند زیرا رستوران ها و کاربران به انواع مختلفی از اشیاء تعلق دارند. با توجه به دو مجموعه شی متفاوت Oو S و یک پرس و جو

q \in S

، یک پرس و جو BR k NN به طور رسمی به عنوان تعریف می شود

BR k NN (q) = {o \in O | q \in k NN (o, S)}

، جایی که

k NN (o, S)

k NN از o را در بین تمام اشیاء در مجموعه داده S نشان می دهد .

بسیاری از برنامه های کاربردی واقعی برای نشان دادن سودمندی جستجوهای Rk NN وجود دارد ، به ویژه در برنامه هایی که نیاز به نظارت مداوم بر معکوس نزدیکترین اجسام متحرک دارند. به عنوان مثال، برای خدمات بهبودیافته 911، هر زمان که یک مرکز خدمات تماس اضطراری را دریافت کند، تیمی که نزدیک‌ترین مکان تماس اضطراری است مطلع می‌شود. نمونه‌های دیگر می‌تواند شرکت تاکسی‌سازی باشد که تاکسی‌ها را به مسافران اعزام می‌کند، یا واحدهای پشتیبان ارتش علاقه‌مند به نظارت بر نزدیک‌ترین واحدهای خود که ممکن است به کمک نیاز داشته باشند.

چالش اصلی برای الگوریتم های نظارت مستمر، حفظ تازگی نتایج پرس و جو است، زمانی که پرس و جو و اشیاء داده آزادانه و خودسرانه حرکت می کنند. یک روش ساده افزایش دفعات به روز رسانی است. query q به صورت دوره ای درخواست هایی برای ارزیابی مجدد نتایج پرس و جو ارسال می کند. با این حال، این رویکرد تضمین نمی کند که نتایج تازه هستند، زیرا نتایج پرس و جو ممکن است بین هر تماس با سرور کهنه شود. علاوه بر این، یک بار محاسباتی بیش از حد ممکن است به سمت سرور تحمیل شود زیرا فرکانس ارتباطی بالا هزینه ارتباط را افزایش می دهد.

الگوریتم پیشرفته موجود به نام SAC [ 8 ] تلاش می‌کند تا به مشکل فوق الذکر رسیدگی کند و پرس‌وجوهای Rk NN را در دو مرحله اصلی، یعنی فیلتر کردن و تأیید، نظارت می‌کند . در مرحله فیلتر، با استفاده از قوانین هرس، بخشی از شبکه که نمی تواند حاوی Rk NN از q باشد ، هرس می شود. اشیایی که در شبکه هرس نشده قرار دارند، اشیاء کاندید cand نامیده می شوند . در مرحله تأیید، سرور نظارت می کند که آیا شی

c a n d \in c a n d i d a t e o b j e c t l i s t

R k NN q است . به طور خاص، یک کند به عنوان یک R k NN گزارش می شود اگر و فقط اگر q نزدیکترین شیء کند باشد . با این حال، در هر مهر زمانی، الگوریتم باید هر زمان که شیء کاندید را به‌روزرسانی می‌کند، آن را تأیید کند. راستی‌آزمایی بسیار گران است زیرا (الف) تأیید یک کند مستلزم بررسی این است که آیا q یکی از k نزدیک‌ترین اشیاء کند است یا خیر و (ب) هر زمان که یک کند مکان خود را تغییر می‌دهد، تأیید لازم است.

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

ما چارچوبی را برای نظارت مستمر پرس و جوهای Rk NN ارائه می کنیم که در آن اشیاء پرس و جو و داده در یک شبکه جاده حرکت می کنند.
الگوریتم ما پرس و جوهای MR k NN و BR k NN را برای مقادیر دلخواه k پردازش می کند.
ما قوانین هرس جدیدی را ارائه می کنیم که محاسبه نقاط خروج ایمن را با به حداقل رساندن اندازه شبکه هرس نشده و تعداد اشیاء بهینه می کند.
ما گسترش الگوریتم پیشنهادی را به یک شبکه جاده هدایت‌شده نشان می‌دهیم که در آن هر بخش جاده جهت‌گیری خاصی دارد و به یک شبکه جاده پویا که در آن وزن شبکه بسته به شرایط ترافیک تغییر می‌کند.
ما از طریق یک ارزیابی تجربی گسترده تأیید می‌کنیم که الگوریتم پیشنهادی از نظر هزینه‌های ارتباطی و محاسباتی برای اکثر تنظیمات، از الگوریتم پیشرفته برتری دارد.

ساختار باقی مانده این مقاله به شرح زیر است. بخش 2 کار موجود در مورد نظارت مستمر پرس و جوهای Rk NN در فضای اقلیدسی و شبکه های جاده را بررسی می کند . بخش 3 تعاریف اصطلاحات را ارائه می دهد و مشکل را شرح می دهد. بخش 4 الگوریتم خروج ایمن پیشنهادی (CORE-X) را برای محاسبه نقاط خروج ایمن پرس و جوهای Rk NN متحرک در شبکه های جاده ای توضیح می دهد . بخش 5 تجزیه و تحلیل عملکرد تکنیک پیشنهادی را ارائه می دهد. بخش 6 این مقاله را به پایان می رساند.

2. کارهای مرتبط

یک پرس و جوی RNN برای اشیاء متحرک آن اشیایی را جستجو می کند که شی q را به عنوان نزدیکترین همسایه خود انتخاب می کنند. پردازش پرس و جوهای RNN به یک حوزه تحقیقاتی جدید تبدیل شده است. الگوریتم های زیادی برای نظارت بر معکوس نزدیک ترین همسایگان، به ویژه در فضای اقلیدسی پیشنهاد شده است. با این حال، کمبود الگوریتم های کارآمد برای شبکه های جاده ای وجود دارد. کار مرتبط ما به دو بخش تقسیم می‌شود: بخش 2.1 به پردازش مستمر پرس و جوی RNN در فضای اقلیدسی می‌پردازد و بخش 2.2 پردازش پرس و جو RNN مستمر در شبکه‌های جاده‌ای را بررسی می‌کند.

2.1. الگوریتم هایی برای پردازش پرس و جوی معکوس پیوسته نزدیکترین همسایه در فضای اقلیدسی

کورن و همکاران [ 9 ] اولین کسانی بودند که مفهوم پرس و جوهای RNN را معرفی کردند. آنها از یک تکنیک پیش محاسبه برای جستجوی RNN استفاده کردند. اشکال اصلی رویکرد پیش پردازش این است که به پشتیبانی از پرس و جوهای Rk NN برای تعداد ثابت k محدود می شود .; علاوه بر این، هنگام پردازش حرکات شی ناکارآمد است. برای رفع کاستی‌های تکنیک پیش پردازش، دسته جدیدی از الگوریتم‌ها معرفی شده‌اند که به الگوریتم‌های Snapshot RNN معروف هستند. این الگوریتم های عکس فوری دو فاز اصلی دارند. فاز اول یک مرحله فیلتر است که بر هرس اشیاء غیر ضروری تمرکز دارد. مرحله دوم پالایش است، که تأیید می کند آیا اشیاء باقی مانده نتایج پرس و جو معتبر هستند یا خیر. دو روش اصلی فیلتر که برای پرس و جوهای Rk NN توسعه داده شده اند عبارتند از هرس 60 درجه [ 10 ] و هرس TPL [ 11 ] توسط Stanoi و همکاران. و تائو و همکاران به ترتیب.

دسته دیگر الگوریتم های پرس و جو RNN پیوسته هستند که می توانند نتایج RNN افزایشی تولید کنند. تعدادی الگوریتم نیز برای نظارت کارآمد پرس و جوهای NN، پرس و جوهای محدوده پیوسته و RNN پیشنهاد شده است [ 3 ، 8 ، 11 ، 12 ، 13 ، 14 ، 15 ، 16 ، 17 ]. روش های پردازش پرس و جو پیوسته موجود بر تعریف منطقه نظارت و به روز رسانی نتایج پرس و جو بر اساس مکان شی متحرک تمرکز می کنند. بنتیس و همکاران [ 18] اولین کسانی بودند که نظارت مستمر RNN را مطالعه کردند. با این حال، طرح پیشنهادی آنها فرض می‌کند که سرعت اجسام مشخص است. شیا و همکاران [ 19 ] یک الگوریتم افزایشی و مقیاس پذیر برای پرس و جوهای RNN تک رنگ بر اساس تکنیک هرس 60 درجه معرفی کرد. در رویکرد آنها، منطقه نظارت بر یک پرس و جو RNN پیوسته توسط شش ناحیه پای (تعیین شده توسط نقطه پرس و جو و شش نامزد) و شش منطقه قوس (که توسط شش نامزد و نزدیکترین همسایگان آنها تعیین می شود) تعریف می شود. کارایی این الگوریتم نسبت به روش های مرسوم برتر است زیرا به روز رسانی هایی را که در منطقه نظارت قرار می گیرند شناسایی و پردازش می کند. کانگ و همکاران [ 20] یک الگوریتم جدید برای نظارت بر RNN های پیوسته به نام IGERN پیشنهاد کرد. این کارآمدتر از راه حل های مبتنی بر هرس 60 درجه است زیرا تعداد کمی از نامزدها را به جای کل فضا زیر نظر دارد. علاوه بر این، این روش برای هر دو جستارهای MR k NN و BR k NN قابل اجرا است. مبادله این طرح این است که نمی توان آن را به راحتی به جستارهای Rk NN پیوسته برای k> 1 گسترش داد. بنابراین ، ناحیه نظارتی تعریف شده فقط برای RNN های پیوسته برای k = 1 اعمال می شود.

وو و همکاران [ 21 ] تکنیکی را برای نظارت بر Rk NN ارائه کرد که شامل فیلتر کردن مداوم و پالایش مداوم است. آنها یک چارچوب پالایشی جدید به نام CRange-k پیشنهاد کردند که اشیاء کاندید را با صدور پرس و جوهای kNN در هر منطقه به جای پرس و جوهای نزدیکترین همسایه منفرد تأیید می کند. کاربرانی که نزدیکتر از k NN در هر منطقه هستند، اشیاء کاندید هستند. اگر q یکی از k نزدیکترین امکانات باشد ، این اشیاء کاندید تأیید می شوند . برای نظارت بر نتایج، برای هر شیء کاندید، روش به طور پیوسته ناحیه دایره ای اطراف خود را که حاوی k نزدیکترین امکانات است، نظارت می کند. چیما و همکاران [ 8 ، 22] چندین طرح برای نظارت بر RNN های پیوسته پیشنهاد کرد. در [ 22 ]، آنها یک الگوریتم برای پرس و جوهای پیوسته BR k NN توسعه دادند. آنها از مفهوم ناحیه نفوذ استفاده کردند که در آن شی پرس و جو ثابت است و اشیاء داده در حال حرکت هستند. در [ 8 ]، آنها چارچوب جدیدی را بر اساس مناطق امن برای شبکه های اقلیدسی و جاده ای پیشنهاد کردند که در آن اشیاء پرس و جو و داده در حال حرکت هستند. این طرح به طور قابل‌توجهی هزینه محاسبات را بهبود می‌بخشد، زیرا به هر شی و پرس و جو یک منطقه امن اختصاص می‌دهد، به طوری که محاسبه مجدد گران قیمت مورد نیاز نیست، مشروط بر اینکه پرس و جو و اشیا در مناطق امن مربوطه خود باقی بمانند.

2.2. الگوریتم هایی برای پردازش پرس و جوی معکوس پیوسته نزدیکترین همسایه در شبکه های جاده ای

در سال های اخیر، پردازش پرس و جوی همسایه معکوس در شبکه های جاده ای مورد توجه جامعه تحقیقاتی سیستم های پایگاه داده فضایی قرار گرفته است. ییو و همکاران [ 17 ] ابتدا به موضوع RNN در شبکه‌های جاده‌ای پرداختند (آنها شبکه‌های جاده‌ای را به صورت نمودار نشان دادند) و الگوریتمی را برای هر دو جستجوی MR k NN و BR k NN پیشنهاد کردند. صفر و همکاران [ 23 ] چارچوبی را برای پرس و جوهای RNN بر اساس نمودارهای شبکه Voronoi (NVDs) ارائه کرد تا به طور موثر پرس و جوهای RNN را در شبکه های جاده ای پردازش کند. با این حال، طرح آنها برای پرس و جوهای RNN مداوم مناسب نیست زیرا NVD ها هر زمان که یک مجموعه داده مکان خود را تغییر می دهد تغییر می کند و در نتیجه هزینه های محاسباتی بالایی دارد.

سان و همکاران [ 16 ] نظارت مستمر پرس و جوهای RNN دورنگی را مورد مطالعه قرار داد. آنها یک درخت چندراهی را با هر پرس و جو مرتبط کردند تا منطقه مانیتورینگ را تعریف کنند و فقط به روز رسانی در منطقه نظارت بر نتایج تأثیر می گذارد. با این حال، این روش محدود به پرس‌و‌جوهای دو رنگی است و زمانی که k > 1 اعمال می‌شود، اعمال نمی‌شود . لی و همکاران [ 24 ] یک الگوریتم جدید برای نظارت مستمر Rk NN بر اساس یک درخت چند راهه دو لایه (درخت DLM) پیشنهاد کردند که در آن چندین لم برای کاهش ناحیه نظارت و فیلتر کردن اشیاء کاندید معرفی کردند. نظارت مستمر آنها بر R kروش NN شامل دو فاز است: فاز تولید نتیجه اولیه و فاز تعمیر و نگهداری افزایشی. چیما و همکاران [ 8 ] یک رویکرد منطقه ایمن برای نظارت بر جستارهای مستمر MR k NN و BR k NN در شبکه های اقلیدسی و جاده ای همانطور که در بخش 2.1 ذکر شد پیشنهاد کرد و قوانین هرس را ابداع کرد که منطقه نظارت را کاهش می دهد.

گوتو و همکاران [ 25 ] یک روش مسیریابی ساده برای پردازش پرس و جوهای BR k NN ارائه کرد. وانگ و همکاران [ 26 ] یک الگوریتم مبتنی بر منطقه نفوذ برای نظارت بر Rk NN پیوسته در یک شبکه جاده ای پیشنهاد کرد . آتیک و همکاران [ 27 ] یک طرح مبتنی بر خروج ایمن برای نظارت مستمر پرس و جوهای RNN پیشنهاد کرد. با این حال، این رویکرد برای پرس و جوهای BR k NN اعمال می شود. علاوه بر این، به حرکت اشیاء داده نمی پردازد. در این مقاله، ما طرحی را توسعه می‌دهیم که برای هر دو پرسش‌های MR k NN و BR k NN قابل اجرا است. همچنین می تواند حرکت اشیاء پرس و جو و اشیاء داده را مورد بررسی قرار دهد.

این مقاله نسخه توسعه یافته کار قبلی ما در مورد نظارت بر پرس و جوهای Rk NN برای جابجایی اشیاء داده و پرس و جو است [ 28 ]. با این حال، ما پنج افزونه مرتبط را ارائه می‌دهیم که در کار مقدماتی ما مورد بررسی قرار نگرفتند [ 28 ]. اولین برنامه افزودنی بر اشیاء هرس شده نظارت می کند ( بخش 4.2.2 ). توسعه دوم انطباق های الگوریتم پیشنهادی را برای آدرس دادن به یک شبکه جاده هدایت شده مطالعه می کند ( بخش 4.3.1 ). در توسعه سوم، ما CORE-X را به یک شبکه جاده پویا گسترش می دهیم که در آن فاصله شبکه بسته به شرایط ترافیکی تغییر می کند ( بخش 4.3.2 ). چهارمین پسوند پرس و جوهای دو رنگی R k NN را مطالعه می کند (بخش 4.3.3 ). در بخش پنجم، ما یک مطالعه تجربی گسترده را برای شبکه های جاده ای استاتیک و دینامیک انجام می دهیم ( بخش 5 ). علاوه بر این پسوندهای اصلی، ما همچنین تحلیل پیچیدگی زمانی الگوریتم پیشنهادی را ارائه می‌کنیم که در کار قبلی ما ارائه نشده بود ( بخش 4.4 ).

3. مقدمات

بخش 3.1 اصطلاحات و نمادهای مورد استفاده در این مقاله را تعریف می کند. بخش 3.2 شرح مشکل را بر اساس یک مثال ارائه می دهد.

3.1. تعریف اصطلاحات و نمادها

شبکه جاده ای: یک شبکه جاده ای با یک نمودار وزنی غیر جهت دار نشان داده می شود

G = (N, E, W),

که در آن N مجموعه ای از گره ها را شامل می شود

N = {n_{1}, n_{2}, \dots, n_{| N |}}

E

مجموعه ای از لبه ها است که دو گره مجزا را به هم متصل می کند

E = {e_{1}, e_{2}, \dots, e_{| E |}}

و W ( e ) وزن یک یال e را نشان می دهد . لبه بین دو گره با نشان داده می شود

e (n_{s}, n_{e})

، جایی که

n_{s}

n_{e}

به عنوان گره های مرزی نامیده می شوند. یک گره مرزی با شناسه گره کوچکتر به عنوان گره پایه دنباله نامیده می شود. این مطالعه فرض می کند که

n_{s} \leq n_{e}

. از این رو،

n_{s}

گره پایه است. هر لبه ای که دو گره مجزا را به هم متصل می کند وزن مثبتی دارد که نشان دهنده هزینه سفر در طول لبه است، به عنوان مثال، زمان لازم برای حرکت در امتداد لبه.

بخش: بخش

s_{(p_{1}, p_{2})}

بخشی از لبه بین دو نقطه است،

p_{1}

p_{2}

، روی لبه. یک لبه از یک یا چند بخش تشکیل شده است. یک یال نیز بخشی در نظر گرفته می شود که در آن گره ها نقاط انتهایی لبه هستند. وزن یک قطعه

s_{(p_{1}, p_{2})}

با W (s) نشان داده می شود.

شکل 1 نمونه ای از یک شبکه جاده بدون جهت با هفت گره، n ₁ تا n ₇ را نشان می دهد . چندین لبه و بخش با وزن مربوطه نشان داده شده است. به عنوان مثال، لبه

e (n_{1}, n_{2})

از بخش ها تشکیل شده است

s_{(n_{1}, o_{1})}

s_{(o_{1}, n_{2})}

، که به ترتیب دارای وزن های “1” و “2” هستند. هفت شی داده در این مثال وجود دارد

{o_{1}, o_{2}, \dots, o_{7}} \in O

و یک پرس و جوی تک شی q . Query q و اشیاء داده به ترتیب با مثلث و مستطیل نشان داده می شوند. با توجه به دو نقطه، p ₁ و p ₂ ، کوتاه ترین فاصله مسیر

d i s t (p_{1}, p_{2})

حداقل فاصله بین p ₁ و p ₂ است . در شکل 1 ، کوتاه ترین مسیر از

q

به

o_{3}

است

q \to n_{3} \to n_{6} \to o_{3}

;

d i s t (q, o_{3}) = 11

. جدول 1 نمادهای استفاده شده در این مقاله را نشان می دهد.

3.2. شرح مشکل

در این مقاله، ما در درجه اول به مشکل نظارت مستمر پرس‌و‌جوهای Rk NN روی پرس‌و‌جوهای متحرک و اشیاء داده در شبکه‌های جاده‌ای می‌پردازیم. برای ارائه یک توضیح واضح، از مثال شبکه جاده نشان داده شده در شکل 1 استفاده می کنیم ، که در آن هفت شیء، o ₁ تا o ₇ ، و یک پرس و جو q در یک شبکه جاده وجود دارد. برای توضیح، ما پرس و جوهای MR k NN را در نظر می گیریم که در آن اشیاء داده و اشیاء پرس و جو به یک نوع داده تعلق دارند. با این حال، روش ما همچنین می تواند برای نظارت بر پرس و جوهای پیوسته BR k NN گسترش یابد. در ادامه مقاله، از پرس و جوی Rk NN برای ارجاع به یک MR k استفاده می کنیمپرس و جوی NN مگر اینکه طور دیگری ذکر شده باشد. اجازه دهید فرض کنیم که یک پرس و جو متحرک یک RNN ( k = 1) در یک نقطه خاص p ₁ درخواست می کند . برای به دست آوردن یک RNN، شبکه جاده را از لبه فعالی که حاوی نقطه q است عبور می دهیم . برای هر شی داده

o \in O

. در صورت مواجهه با آن، ما یک پرس و جوی تأیید صحت ( o ، k ، q ) صادر می کنیم که بررسی می کند آیا RNN است یا خیر. اگر شی دیگری وجود داشته باشد

d i s t (o, o^{'}) < d i s t (o, q),

پس o یک RNN نیست. در غیر این صورت، o به مجموعه نتایج RNN که با R _p نشان داده شده است وارد می شود . بسط در هر مسیر زمانی خاتمه می یابد که k شیء در آن جهت پیدا شود. برای به دست آوردن یک RNN در نقطه p ₂ , روش ساده تکرار رویه اجرا شده در p ₁ است . با این حال، استفاده از محاسبه مجدد هر زمان که پرس و جوی q یا هر شی داده ای مکان خود را تغییر دهد به طور قابل توجهی عملکرد الگوریتم را کاهش می دهد. برای رفع این مشکل، رویکرد خروج ایمن را معرفی می کنیم.

در چارچوب پیشنهادی، سرور نقاط خروج ایمن را برای هر شی متحرک و شی پرس و جو محاسبه می کند. از آنجایی که ما در حال رسیدگی به یک مشکل پیچیده هستیم که در آن اشیاء پرس و جو و اشیاء داده در حال حرکت هستند، لازم است نقاط خروج ایمن برای هر شی داده متحرک محاسبه شود. سرور مجموعه ای از پرس و جوهای متحرک و مجموعه ای از اشیاء متحرک را نگهداری می کند. نتایج پرس و جو تا زمانی که همه اشیاء در نقاط خروج امن مربوطه خود قرار نگیرند یکسان خواهد بود. هر زمان که یک پرس و جو یا شی داده ای از نقاط خروج ایمن خود خارج شود، سرور R k را مجدداً محاسبه می کندNN و نقاط خروج ایمن برای پرس و جو و اشیاء داده. با این حال، محاسبه نقاط خروج ایمن برای همه اشیاء داده، عملکرد الگوریتم را کاهش می دهد. برای پرداختن به این موضوع، قوانین هرس را ابداع کردیم که به ما اجازه می دهد نقاط خروج ایمن را فقط برای اشیاء هرس نشده محاسبه کنیم.

همانطور که قبلاً ذکر شد، ما به مشکل نظارت مستمر پرس‌و‌جوهای RNN می‌پردازیم که در آن اشیاء پرس و جو و داده آزادانه در یک شبکه جاده‌ای حرکت می‌کنند. بنابراین، رویدادهای زیر می توانند نتیجه پرس و جو را تغییر دهند.

رویداد 1: شی پرس و جو q به خارج از نقاط خروج امن مربوطه حرکت می کند.

رویداد 2: یک شی

o \in U O

خارج از نقاط خروج امن مربوطه حرکت می کند.

رویداد 3: حرکت اجسام هرس شده مجموعه R k NN را تغییر می دهد.

شکل 2 جریان درخواست را برای پردازش پرس و جوهای Rk NN نشان می دهد . در ابتدا، شی پرس و جو q (مشتری) یک پرس و جو RkNN را به همراه مکان فعلی (مرحله 1) به سرور ارسال می کند. به محض دریافت یک درخواست، سرور مجموعه نتایج RkNN را محاسبه می _کندو نقاط خروج ایمن برای پرس و جو و اشیاء داده هرس نشده (مرحله 2 و 3). نتایج پرس و جو تا زمانی که هر یک از سه رویداد فوق الذکر رخ ندهد معتبر می مانند. برای نظارت بر رویداد 1، شی پرس و جو مکان خود را در برابر نقاط خروج ایمن دریافتی بررسی می کند (مرحله 5). اگر شی پرس و جو فراتر از هر خروجی ایمن حرکت کند، کلاینت یک پرس و جو RkNN را برای یک نتیجه به روز شده و نقاط خروج ایمن آن مجدداً به سرور صادر می کند. یک سرور حرکت اشیاء داده را برای تأیید رویدادهای 2 و 3 (مرحله 6) نظارت می کند. اگر رویداد 2 یا 3 رخ دهد، سرور نتایج پرس و جو را دوباره محاسبه می کند و به مشتری اطلاع می دهد.

4. الگوریتم خروج ایمن برای جابجایی پرس و جوهای R k NN و جابجایی اشیاء

در این بخش، ما تکنیک‌هایی را برای نظارت بر جستارهای متحرک Rk NN و اشیاء متحرک در یک شبکه جاده توسعه می‌دهیم . در بخش 4.1 ، ما یک الگوریتم برای محاسبه منطقه امن برای شی متحرک q ارائه می کنیم . نظارت بر اشیاء داده در بخش 4.2 توضیح داده شده است . ما توسعه‌های رویکرد پیشنهادی را برای انواع دیگر جستارهای Rk NN در بخش 4.3 ارائه می‌کنیم . در نهایت، بخش 4.4 پیچیدگی های زمانی و مکانی CORE-X را تحلیل می کند.

4.1. منطقه امن برای جابجایی q

در این بخش، ما یک الگوریتم خروج ایمن جدید را ارائه می‌کنیم که به مسئله جابجایی پرس‌وجوهای Rk NN و جابجایی اشیاء در یک شبکه جاده‌ای می‌پردازد. الگوریتم 1 اسکلت الگوریتم خروج ایمن پیشنهادی را برای محاسبه مناطق امن به تصویر می کشد. این شامل سه مرحله است: (1) تعیین اشیاء مفیدی که می توانند به منطقه امن کمک کنند. (2) محاسبه ناحیه تأثیر اشیاء مفید. (3) محاسبه نقاط خروج ایمن برای اشیاء پرس و جو.

الگوریتم 1: محاسبه مناطق امن (اسکلت)
ورودی: O : اشیاء داده، q : شی پرس و جو، k : عدد صحیح
خروجی: SR : منطقه امن
1:	مجموعه شی $O^{'} \leftarrow r o a d n e t w o r k (O, q, k)$
2:	مجموعه شی $O^{+} \leftarrow {o^{+} \in O^{'} \| d i s t (o, q) < d i s t (o, o_{k + 1})}$
3:	مجموعه شی $O^{-} \leftarrow {o^{-} \in O^{'} \| d i s t (o, q) > d i s t (o, o_{k})}$
4:	در حالی که $O^{+}$ یا $O^{-}$ انجام غیر خالی است
5:		هدف – شی $o = p i c k o b j e c t (O^{+}, O^{-})$
6:		اگر $o \in O^{+}$ سپس
7:			$I R^{+} \leftarrow c o m p u t e I R (O^{+}, O^{-}, k)$
8:			$S R \leftarrow S R \cap I R^{+}$
9:		دیگر
10:			$I R^{-} \leftarrow c o m p u t e I R (O^{+}, O^{-}, k)$
11:			$S R \leftarrow S R - \cup I R^{-}$
12:	پایان در حالی که
13:	SR را برگردانید

الگوریتم 1 اسکلت ایده پیشنهادی را ارائه می دهد. الگوریتم با تعیین اشیاء پاسخ و بدون پاسخ شروع می شود. جزئیات روش در بخش 4.1.1 توضیح داده شده است . سپس، در فاز 2، الگوریتم ناحیه تأثیر اشیاء پاسخ و اشیاء بدون پاسخ را محاسبه می کند ( بخش 4.1.2 ). در نهایت، منطقه امن را با انجام تقاطع و تنظیم عملیات تفاوت در بخش های جاده محاسبه می کند ( بخش 4.1.3 ).

4.1.1. تعیین اشیاء مفید

هدف این مرحله تعیین اشیاء بالقوه است که می توانند به محاسبه منطقه امن کمک کنند. هدف بازیابی مجموعه کوچکی از اشیاء داده برای کاهش سربار محاسبات است. در مطالعه ما، اشیاء داده‌ها به دو دسته تقسیم می‌شوند: اشیاء پاسخ (مشخص شده با

O^{+}

) و اشیاء بدون پاسخ (با علامت گذاری شده است

O^{-}

تعریف 1.

یک شی o را شئ پاسخی if می نامند

d i s t (o, q) \leq d i s t (o, o^{'})

جایی که o هر شیء دیگری در شبکه راه است. به طور مشابه، می‌توانیم این تعریف را برای RkNN تعمیم دهیم: یک شی o را یک شی پاسخی if می‌گویند

d i s t (o, q) \leq d i s t (o, o_{k + 1})

، که در آن o _k₊₁ (k + 1) امین شیء NN از o است. یعنی می توان گفت که تمام اشیاء پاسخ RkNN های query q هستند، بنابراین،

o^{+} \in R_{k}

تعریف 2.

یک شی o را یک شی بدون پاسخ if می نامند

d i s t (o, q) > d i s t (o, o^{'})

، جایی که o هر شیء دیگری در شبکه راه است.

به طور مشابه، می‌توانیم این تعریف را برای R k NN تعمیم دهیم: یک شی o یک شی بدون پاسخ نامیده می‌شود اگر

d i s t (o, q) > d i s t (o, o_{k})

، جایی که o _k k امین شی NN از o است . یعنی می توان گفت که همه اشیاء بدون پاسخ R k NN پرس و جو q نیستند ، بنابراین،

o^{-} \notin R_{k}

یک روش ساده برای بازیابی

R_{k}

set برای پیمایش شبکه از q و برای هر شی داده است

o \in O

مواجه شد، یک پرس و جو نزدیکترین همسایه را صادر کنید. اگر

q \in N N (o)

، q نزدیکترین شی به o است . در نتیجه،

o^{+} \in R_{k} .

با این حال، این رویکرد باید تمام اشیاء داده را ارزیابی کند زیرا اندازه

R_{k}

ثابت نیست و شبکه راه ممکن است دارای نقاط دور از q باشد . برای جلوگیری از اکتشاف غیرضروری شبکه جاده ای، لم هرس را ارائه می دهیم.

قبل از ارائه لم، لازم است گره های بسته را تعریف کنیم. گره n گره بسته نامیده می شود اگر یک شی o وجود داشته باشد که به گونه ای باشد

d i s t (n, o) < d i s t (n, q)

. شی o یک شی مسدود کننده نامیده می شود زیرا باعث می شود گره n یک گره بسته باشد. در شکل 1 ، گره n ₂ یک گره بسته است زیرا

d i s t (n_{2}, o_{1}) < d i s t (n_{2}, q)

، که o _{1 را} به یک شی مسدود کننده تبدیل می کند.

لم 1.

یک شی o نمی تواند RNN q باشد اگر کوتاه ترین مسیر بین q و o شامل یک گره بسته با یک شی مسدود کننده o’ باشد، جایی که

o^{'} \neq o .

اثبات

فرض کنید یک گره بسته n در کوتاه ترین مسیر بین o و q وجود دارد . کوتاه ترین فاصله بین o و q است

d i s t (o, q) = d i s t (n, o) + d i s t (n, q)

. اجازه دهید o” شی مسدود کننده و

d i s t (o, o^{'}) = d i s t (n, o) + d i s t (n, o^{'})

. همانطور که می دانیم

d i s t (n, o^{'}) < d i s t (n, q),

از این رو،

d i s t (o, o^{'}) < d i s t (o, q)

. بنابراین، o نمی تواند یک RNN از q باشد .

در شکل 1 ، شی داده o ₂ نمی تواند RNN q باشد زیرا کوتاه ترین فاصله بین o ₂ و q از n ₂ می گذرد . زیرا

d i s t (n_{2}, o_{1}) = 2

d i s t (n_{2}, q) = 3

، شی داده o _{1 به}o ₂ نزدیکتر از q است . لم فوق را می توان به راحتی تا R k NN گسترش داد. یک شی o نمی تواند R k NN q باشد اگر کوتاه ترین مسیر بین q و o شامل یک گره n باشد و k شی داده ای وجود داشته باشد به طوری که برای هر شی o’ ،

d i s t (n, o^{'}) < d i s t (n, q)

، جایی که

o^{'} \neq o .

الگوریتم 2 شبه کد را برای تعیین اشیاء پاسخ ارائه می دهد. CORE-X شبکه را در اطراف q به روشی مشابه الگوریتم Dijkstra طی می کند. با استفاده از Lemma 1، گره هایی را که ممکن است به RNN منتهی نشوند حذف می کند. الگوریتم با کاوش در لبه فعالی که شی پرس و جو q در آن قرار دارد شروع می شود و شبکه را به ترتیب افزایش فاصله از شی پرس و جو q گسترش می دهد . هر ورودی در صف دارای فرم 〈

p_{a}, e d g e

〉، جایی که p _a نشان دهنده نقطه لنگر در لبه است. برای یک یال فعال، q تبدیل به نقطه لنگر می شود. در غیر این صورت، هیچ یک از گره های مرزی لبه، به عنوان مثال،

n_{s}

یا

n_{e}

، به نقطه لنگر تبدیل می شود. اگر تعداد مورد نظر از اشیاء پاسخ در یک یال فعال یافت نشد، لبه های مجاور گره های مرزی در صف قرار می گیرند. لبه ها به ترتیب فزاینده فاصله از q بریده می شوند . پیمایش لبه ها با پایان یافتن صف خاتمه می یابد. خط 4 با قرار دادن لبه فعال یک صف را مقداردهی اولیه می کند. اگر یک لبه حاوی یک شی داده o باشد ، باید بررسی کنیم که آیا

o \in R k NN (q)

. بنابراین، الگوریتم یک پرس و جو تأیید ( o ، k ، q ) صادر می کند (خط 10). پرس و جوی راستی‌آزمایی با اعمال یک پرس‌وجوی range-NN در اطراف شی o با محدوده تنظیم شده بررسی می‌کند که آیا q در میان k NN‌های شی داده o است یا خیر.

d i s t (o, q)

. اگر

q = k NN (o)

, o R k NN q است . بنابراین، o به مجموعه نتیجه R _k (خط 12) اضافه می شود. اگر لبه حاوی هیچ شی داده ای o نباشد ، الگوریتم به گسترش خود ادامه می دهد و لبه های مجاور گره مرزی را در صف قرار می دهد.

الگوریتم 2: پاسخ دادن به شی ( q , k )
ورودی: q: محل پرس و جو، k : عدد صحیح
خروجی: R _k : نتیجه پرس و جو (اشیاء پاسخ)
1:	$q u e u e \leftarrow \emptyset$						/* صف یک صف اولویت است با یال های مرتب شده بر اساس فاصله تا q */
2:	$A_{k} \leftarrow \emptyset$						/* مجموعه ای از اشیاء پاسخ*/
3:	$v i s i t e d \leftarrow \emptyset$						/اطلاعات لبه های بازدید شده را ذخیره می کند /
4:	صف فشار ( q ، لبه _فعال )						/* لبه _فعال نشان دهنده لبه فعال است */
5:	در حالی که صف خالی نیست انجام دهید
6:		$〈 p_{a}, e d g e 〉 \leftarrow q u e u e . p o p ()$
7:		اگر $〈 p_{a}, e d g e 〉 \notin v i s i t e d$ سپس
8:			$v i s i t e d \leftarrow v i s i t e d \cup {e d g e}$
9:				اگر لبه حاوی یک شی داده o باشد
10:					k NN( o ): تأیید ( o ، k ، q )
11:					اگر q با تأیید کشف شود
12:						$R_{k} \leftarrow R_{k} \cup o$
13:				دیگر
14:					$q u e u e . p u s h 〈 n_{β}, e d g e 〉$
15:	پایان در حالی که
16:	R _kرا برگردانید

اجازه دهید مثال ارائه شده در شکل 1 را در نظر بگیریم ، جایی که پرس و جو q یک RNN درخواست کرد ( k = 1). ما این مثال را در سراسر این بخش بررسی خواهیم کرد. الگوریتم گسترش را از لبه فعال شروع می کند که این است

e (n_{2}, n_{3})

. از آنجایی که هیچ شیء داده ای در آن لبه کشف نمی شود، یال های مجاور گره های مرزی به صف اضافه می شوند. ابتدا لبه های مجاور نزدیکترین گره مرزی در صف قرار می گیرند. بنابراین، لبه ها

e {(n_{3}, n_{4}), (n_{3}, n_{6})}

در صف قرار می گیرند. شی داده o ₆ برای اولین بار در کشف شد

(n_{3}, n_{4})

، که پرس و جوی راستی آزمایی verify( o ₆ , 1, q ) را راه اندازی می کند. چون q = NN( o ₆ )، o ₆ به مجموعه نتیجه R _k اضافه می شود . به یاد بیاورید که توسط لم 1، گره n ₄ یک گره بسته با شی o ₆ به عنوان شی مسدود کننده است. بنابراین، تمام اجسام دیگری که کمترین فاصله را از n ₄ می گذرد به جز o ₆ به طور خودکار هرس می شوند. سپس، شی داده o ₄ در آن کشف می شود

e (n_{3}, n_{6})

با تأیید o ₄ ،

q \neq NN (o_{4})

; بنابراین، جستجو نیز در این جهت خاتمه می یابد. سپس، لبه های مجاور n ₂ به صف اضافه می شوند.

e {(n_{1}, n_{2}), (n_{2}, n_{5}), (n_{2}, n_{7})}

و داده های شی o ₁ بر روی بازیابی می شوند

e (n_{1}, n_{2})

. شی داده o ₁ تایید شده و به مجموعه نتیجه اضافه می شود زیرا q = NN( o ₁ ). جستجو خاتمه می یابد زیرا نیازی به گسترش بیشتر در این جهت نیست زیرا گره n ₂ یک گره بسته است.

در مرحله بعد، اشیاء بدون پاسخی را که می توانند به منطقه امن کمک کنند، تعیین می کنیم. اشیاء مفید بدون پاسخ

U O^{-} \in O^{-}

اشیایی هستند که برای آنها هر

o^{+} = N N (o^{-})

. به عبارت دیگر،

U O^{-}

RNNهای اشیاء پاسخ هستند. RNNهای اشیاء مفید (UO) را می توان با همان الگوریتمی که این تغییرات را انجام می دهد تعیین کرد: (1) نقطه لنگر به جای q o ^{+ است و (2)}تأیید پرس و جو تأیید ( o ، k ، q ) برای تأیید ( o) اصلاح می شود. , k , o ⁺ ). الگوریتم از نتایج جستجوهای range-NN صادر شده در اشیاء داده استفاده مجدد می کند تا از تأیید چندگانه اشیاء داده مشابه جلوگیری کند. هنگامی که محاسبات کامل شد، نتایج جستجوی کش حذف می شوند تا مصرف حافظه کاهش یابد.

در نهایت، می توان نتیجه گرفت که اشیاء مفید عبارتند از: (1) همه اشیاء پاسخ و (2) RNN اشیاء پاسخ. حال، اجازه دهید اشیاء UO را برای k = 2 در مثال داده شده در شکل 1 تعیین کنیم . برای توضیح، جدول 2 k NNهای هر شی داده را نشان می دهد .

از جدول 2 مشخص است که o ₁ و o ₆ هر دو مفعول پاسخ هستند زیرا q یکی از 2NN است. اکنون، از اشیاء بدون پاسخ، می‌توانیم ببینیم که o ₂ RNN o ₁ است زیرا o ₁ = 2NN( o ₂ ). به طور مشابه، o ₇ RNN o ₆ است . از این رو، مجموعه اشیاء مفید است

U O = {o_{1}, o_{2}, o_{6}, o_{7}}

. اشیاء داده o ₃ ، o ₄ و o ₅ هرس شده اند.

4.1.2. منطقه تأثیر محاسباتی برای اشیاء مفید

بعد از اینکه مجموعه اشیاء مفید را بازیابی کردیم، مرحله بعدی محاسبه ناحیه تاثیر اشیاء پاسخ و غیر پاسخ است.

نفوذ منطقه پاسخ اشیاء

ناحیه تأثیر اشیاء پاسخ به صورت زیر تعریف می شود:

منآر+= { ص∣∣دمن نیستم ( _o+، ص ) ≤دمن نیستم ( _o+،ok + 1) }منآر+={پ|دمنستی(�+،پ)≤دمنستی(�+،�ک+1)}

(1)

در اینجا، o _k+1 نشان دهنده ( k +1)امین نزدیکترین همسایه o است . طبق تعریف، ناحیه تأثیر اشیاء پاسخ شامل تمام نقاطی است که برای آنها $q = N N (o^{+})$ . یعنی شامل تمام نقاطی است که شی o باقی می ماند $o^{+}$ .

ناحیه تأثیر اشیاء پاسخ را می توان با کاوش در شبکه اطراف شیء پاسخ به روشی مشابه آنچه در بخش 4.1.1 توضیح داده شد، محاسبه کرد . کاوش با کشف ( k +1)امین نزدیکترین همسایه شی پاسخ پایان می یابد. منطقه نفوذ با محدوده ( o ، d ) نشان داده می شود، جایی که d است

d i s t (o, o_{k + 1})

شکل 3 ناحیه نفوذ شی o ₁ را برای سناریوی مثالی که در بالا مورد بحث قرار گرفت نشان می دهد. گسترش شبکه راه ها از o _{1 شروع می شود تا زمانی که}o _k+1 را پیدا کند که در این مثال 3NN است. شی o ₇ 3NN از o ₁ و است

d i s t (o_{1}, o_{7}) = 8

. الگوریتم a را صادر خواهد کرد

r a n g e (o_{1}, 8)

پرس و جوی که تمام نقاط را به عنوان ناحیه نفوذ o ₁ همانطور که در شکل 3 نشان داده شده است علامت گذاری می کند . به طور مشابه، منطقه نفوذ از

o_{6}

در شکل 3 نشان داده شده است . شی داده o ₄ 3NN o ₆ و است

d i s t (o_{6}, o_{4}) = 7.

بنابراین،

r a n g e (o_{6}, 7)

پرس و جو تمام نقاط در فاصله “7” از را علامت گذاری می کند

o_{6}

. خطوط پررنگ در شکل 3 و شکل 4 ناحیه نفوذ را نشان می دهد

o_{1}

o_{6}

، به ترتیب.

منطقه نفوذ اشیاء بدون پاسخ

ناحیه تأثیر اشیاء بدون پاسخ به صورت زیر تعریف می شود:

منآر–= { ص∣∣دمن نیستم ( _o–، ص ) ≤دمن نیستم ( _o–،oک) }منآر–={پ|دمنستی(�–،پ)≤دمنستی(�–،�ک)}

(2)

ناحیه تأثیر اشیاء بدون پاسخ را می توان از فاصله بین شی بدون پاسخ و k امین شی محاسبه کرد. در اینجا o _k نشان دهنده k نزدیکترین همسایه o است . به عبارت دیگر، منطقه تاثیر اشیاء بدون پاسخ شامل تمام نقاطی است که شی o در آن باقی می ماند

o^{-}

. ناحیه تأثیر اشیاء بدون پاسخ به همان روشی محاسبه می شود که ناحیه تأثیر اشیاء پاسخ، تنها تفاوت این است که الگوریتم به جای ( k + 1)NN فاصله تا شی k NN را بررسی و محاسبه می کند .

شی o ₇ را در شکل 1 در نظر بگیرید : 2NNs of

o_{7} = (o_{6}, o_{5})

با وزنه ها (5، 7). در این مثال، o ₅ دومین NN از است

o_{7}

d i s t (o_{7}, o_{5}) = 7

. بنابراین، ناحیه نفوذ جسم o _{7 از}o ₇ در هر جهت متصل “7” واحد است . به طور مشابه، می‌توانیم ناحیه تأثیر o ₂ را محاسبه کنیم . خطوط پررنگ در شکل 5 و شکل 6 ناحیه نفوذ o ₂ و o _{7 را نشان می دهد.}، به ترتیب. NN برای اشیاء پاسخ زمانی تغییر می کند که شی پرس و جو به خارج از منطقه تأثیر حرکت کند، در حالی که در مورد اشیاء بدون پاسخ، هنگامی که شی پرس و جو در یک منطقه تأثیر حرکت می کند، نتیجه تغییر می کند. یعنی NN های شی پاسخ یکسان می مانند تا زمانی که شی پرس و جو در منطقه تأثیر قرار گیرد و برای اشیاء بدون پاسخ، NN ها تا زمانی که شی پرس و جو در خارج از ناحیه تأثیر قرار گیرد، یکسان می مانند. توجه داشته باشید که هنگامی که یک ناحیه نفوذ محاسبه می شود، تا زمانی که q و UO در مناطق امن مربوطه خود قرار دارند، معتبر باقی می ماند. بنابراین، محاسبه مجدد ناحیه نفوذ تنها زمانی مورد نیاز است که q یا UO مناطق امن مربوطه خود را ترک کنند.

الگوریتم 3 ناحیه تأثیر اشیاء پاسخ و اشیاء بدون پاسخ را محاسبه می کند.

الگوریتم 3: محاسبه منطقه تأثیر ( $O^{+}$ ، $O^{-}$ ، ک )
ورودی : $O^{+}$ : پاسخ مجموعه اشیاء، $O^{-}$ : مجموعه اشیاء بدون پاسخ، k: عدد صحیح
خروجی : $I R^{+}$ ناحیه تأثیرگذاری اشیاء پاسخ، $I R^{-}$ منطقه تحت تأثیر اشیاء بدون پاسخ
1:	$I R^{+} \leftarrow \emptyset$ ، $I R^{-} \leftarrow \emptyset$
	/* ناحیه نفوذ اشیاء پاسخ */
2:	برای هر کدام $O^{+}$ انجام دادن
3:		شبکه جاده را تا o _k₊₁ گسترش دهید .
4:		$d \leftarrow d i s t (o, o_{k + 1})$
5:		علامت گذاری محدوده (o, d)؛
6:		$I R^{+} \leftarrow I R^{+} \cup I R^{+}$ ;
7:	پایان برای
	/* ناحیه نفوذ اشیاء بدون پاسخ */
8:	برای هر کدام $O^{-}$ انجام دادن
9:		شبکه راه را تا o _k گسترش دهید .
10:		$d \leftarrow d i s t (o, o_{k})$ ;
11:		علامت گذاری محدوده ( o , d );
12:		$I R^{-} \leftarrow I R^{-} \cup I R^{-}$ ;
13:	پایان برای
14:	R بازگشت $I R^{+}$ و $I R^{-}$

4.1.3. محاسبه نقاط خروج ایمن

ناحیه امن SR یک کوئری q به صورت زیر تعریف می شود:

اس R = {\cap I آر + - \cup من آر -}

(3)

جایی که $I R^{+}$ نشان دهنده ناحیه تأثیر اشیاء پاسخ و $I R^{-}$ منطقه تأثیر اشیاء بدون پاسخ را نشان می دهد. از تعریف، می‌توان دریافت که هر نقطه‌ای که در تقاطع ناحیه تأثیر شیء پاسخ قرار دارد $O^{+}$ به عنوان یک منطقه امن در نظر گرفته می شود و هر نقطه p که در ناحیه نفوذ شی غیر پاسخ قرار دارد $O^{-}$ باید مستثنی شوند.

در یک شبکه راه، منطقه امن با مجموعه ای از بخش ها بیان می شود. در شکل 1 ، به یاد بیاورید که o ₁ و o ₆ اشیاء پاسخی هستند و o ₂ و o ₇ اشیاء غیرجواب مفیدی هستند. با اعمال فرمول بالا، منطقه امن را می توان به صورت زیر بیان کرد:

اس R = {(I R (o 1) \cap من R (o 6)) - (I R (o 2) \cup من R (o 7))}

(4)

جدول 3 محاسبه نقاط خروج ایمن را برای شی query q در شکل 1 خلاصه می کند . در بخش قبل، منطقه تأثیر IR همه اشیاء مفید را محاسبه کردیم که با مجموعه ای از بخش ها توضیح داده شد. برای به دست آوردن منطقه ایمن، باید عملیات تقاطع را انجام دهیم و عملیات تفاضلی را در بخش های جاده تنظیم کنیم. بخش هایی را به دست می آوریم

e (n_{2}, n_{3})

s {(n_{3}, s_{2}), (n_{3}, s_{3})}

از تقاطع IR ( o ₁ ) و IR ( o ₆ ). از آنجایی که o ₂ و o ₇ اشیایی بدون پاسخ هستند، منطقه امن باید IR ( o ₂ ) و IR ( o ₇ ) را حذف کند. بنابراین، منطقه امن بخش ها خواهد بود

s {(s_{5}, n_{3}), (n_{3}, s_{2})}

. مجموعه نقاط مرزی s ₂ و s ₅ به مجموعه نقاط خروج ایمن تبدیل می شود. شکل 7 نقاط خروج ایمن q را نشان می دهد .

4.2. نظارت بر اشیاء داده

همانطور که قبلا ذکر شد، ما در حال مطالعه یک مورد خاص هستیم که در آن اشیاء داده و اشیاء پرس و جو می توانند به طور تصادفی در یک شبکه جاده حرکت کنند. R k NN برای یک پرس و جو q را می توان با حرکت اشیاء داده تغییر داد. در این بخش، تکنیک‌هایی را برای نظارت مداوم بر اشیاء داده ارائه می‌کنیم. همانطور که در بخش 4.1.1 بحث شد ، اشیاء داده به انواع تقسیم می شوند: (1) اشیاء UO و (2) اشیاء هرس شده. از آنجایی که حرکت UO حیاتی است و یک حرکت جزئی می تواند نتایج را تغییر دهد، ما نقاط خروج ایمن تمام UO را محاسبه می کنیم، در حالی که برای اشیاء هرس شده، از شبکه نظارت شده بر اساس ناحیه نفوذ محاسبه شده در بخش 4.1.2 استفاده می کنیم .. محاسبه نقاط خروج ایمن تمام اشیاء هرس شده نیز هزینه محاسبات را افزایش می دهد.

4.2.1. محاسبه نقاط خروج ایمن اشیاء مفید ( UO )

به یاد بیاورید که اشیاء پاسخ آن دسته از اشیایی هستند که شی پرس و جوی آنها q یکی از k اشیاء NN آن باشد. این بدان معنی است که یک شی پاسخ در نقاط خروج امن قرار دارد تا زمانی که k اشیاء NN آن یکسان باقی بمانند. به طور مشابه، اشیاء مفید بدون پاسخ آن دسته از اشیایی هستند که هر یک از اشیاء پاسخ در میان k NN آن قرار می گیرند. این بدان معناست که تا زمانی که k NN مربوطه آنها یکسان باشد، همه اشیاء مفید در نقاط خروج ایمن قرار دارند. بنابراین، ما باید نزدیکترین همسایگان اجسام متحرک را در یک شبکه جاده نظارت کنیم. ما از رویکرد چو و همکاران استفاده می کنیم. [ 3]، الگوریتم خروج ایمن (SEA)، که می تواند به طور موثر نقاط خروج ایمن یک جستار نزدیکترین همسایه متحرک را در شبکه جاده محاسبه کند.

ابتدا، ما به طور رسمی مجموعه ای از نقاط خروج ایمن را برای یک جستجوی NN متحرک در شبکه جاده تعریف می کنیم. اجازه دهید

Ω

مجموعه ای از نقاط خروج ایمن برای یک نقطه پرس و جو kNN q و

O = {o_{1}, o_{2}, \dots, o_{| O |}}

مجموعه ای از اشیاء مورد علاقه q باشد . فرض کنید مجموعه پاسخ ها (یعنی

O^{+}

) از q و مجموعه بدون پاسخ آن (یعنی،

O^{-}

) هستند

O^{+} = {o_{1}^{+}, o_{2}^{+}, \dots, o_{k}^{+}}

O^{-} = {o_{k + 1}^{-}, o_{k + 2}^{-}, \dots, o_{| O |}^{-}}

، به ترتیب. سپس، آن را نگه می دارد

d (q, o^{+}) \leq d (q, o^{-})

برای یک شی پاسخ

o^{+} \in O^{+}

و یک شیء بدون پاسخ

o^{-} \in O^{-}

. سرانجام،

Ω

به صورت زیر تعریف می شود:

Ω = {ω \in G ∣ ∣ م یک X (د (ω, o + 1) ، د (ω, o + 2) ، \dots ، د (ω, o + ک)) = م من ن (د (ω, o - k + 1) ، د (ω, o - k + 2) ، \dots د (ω, o - | o |))}

(5)

جایی که $M I N ()$ و $M A X ()$ حداقل و حداکثر مقدار آرایه ورودی را به ترتیب برمی گرداند. یعنی یک نقطه خروجی امن $ω$ نقطه مرکزی است، یعنی $A X (d (ω, o_{1}^{+}), \dots, d (ω, o_{k}^{+})) = M I N (d (ω, o_{k + 1}^{-}), \dots, d (ω, o_{| o |}^{-}))$ ، بین دورترین شی پاسخ و نزدیکترین شی بدون پاسخ.

دو لم اصلی زیر برای تعیین اینکه آیا یک نقطه خروج ایمن در بخش وجود دارد ارائه شده است.

لم 2.

اگر

A_{n_{β}} \cup O_{(n_{β}, p_{a})} \neq A_{p_{a}}

، یک نقطه خروج امن وجود دارد

ω

در بخش .

اثبات

لطفاً به [ 3 ] مراجعه کنید. این لم نشان می دهد که یک نقطه خروج ایمن در یک بخش وجود دارد اگر مجموعه پاسخ ها در شیء باشند

n_{β}

با مجموعه اشیاء پاسخ در p _a برابر نیست .

لم 3.

اگر

A_{n_{β}} \cup O_{(n_{β}, p_{a})} = A_{p_{a}}

، هیچ نقطه خروج امنی در بخش وجود ندارد.

اثبات

لطفاً به [ 3 ] مراجعه کنید. این لم نشان می‌دهد که اگر مجموعه پاسخ‌ها در یک قطعه باشد، نقطه خروج امن در یک قطعه وجود ندارد

n_{β}

برابر است با مجموعه اشیاء پاسخ در p _a .

برای این منظور معرفی می کنیم

o_{n}^{-}

o_{f}^{+}

. برای سادگی، اجازه دهید این را فرض کنیم

A_{n_{β}} \cup O_{(n_{β}, p_{a})} - A_{p_{a}}

مطابقت دارد

O^{-} = {o_{1}^{-}, o_{2}^{-}, \dots, o_{| O^{-} |}^{-}}

A_{p_{a}}

مطابقت دارد

O^{+} = {o_{1}^{+}, o_{2}^{+}, \dots, o_{| O^{+} |}^{+}}

. سپس، در یک نقطه

p \in [n_{β}, p_{a}],

o_{n}^{-}

به عنوان نزدیکترین شیء بدون پاسخ به p نامیده می شود به طوری که

d (p, o_{n}^{-}) = M I N (d (p, o_{1}^{-}), d (p, o_{2}^{-}), \dots, d (p, o_{| o^{-} |}^{-}))

. به همین ترتیب، در یک نقطه

p \in [n_{β}, p_{a}]

o_{f}^{+}

به دورترین شی پاسخ از p گفته می شود به طوری که

d (p, o_{f}^{+}) = M A X (d (p, o_{1}^{+}), d (p, o_{2}^{+}), \dots, d (p, o_{| o^{+} |}^{+}))

. نقطه وسط بین

o_{n}^{-}

o_{f}^{+}

به یک نقطه خروجی امن تبدیل می شود

ω

. به این معنا که،

d (ω, o_{n}^{-}) = d (ω, o_{f}^{+})

ما اکنون در مورد محاسبه نقاط خروج ایمن برای پاسخ شی o ₁ در شبکه جاده ای مثال ارائه شده در شکل 1 بحث می کنیم . جدول 4 محاسبه نقاط خروج ایمن برای شی داده o ₁ را برای سناریوی مثال در شکل 1 خلاصه می کند . به یاد داشته باشید که ما در حال بررسی هستیم

k = 2

. اشیاء پاسخ داده شی o ₁ هستند

A_{o_{1}} = {q, o_{2}}

SEA کاوش را از لبه فعال حاوی شی o ₁ آغاز می کند . زیرا

e (n_{1}, n_{2})

دنباله فعال است، محل o ₁ نقطه لنگر است. هر یک از دو بخش

s (n_{1}, o_{1})

s (o_{1}, n_{2})

در داخل

e (n_{1}, n_{2})

به صورت جداگانه بررسی می شود. همانطور که در جدول 4 نشان داده شده است ، برای

s (n_{1}, o_{1})

p_{a} = o_{1}

A_{o_{1}} = {q, o_{2}}

A_{n_{1}} = {q, o_{2}}

، و

O_{(n_{1}, o_{1})} = {\emptyset}

. توسط لما 3،

A_{n_{1}} \cup O_{(n_{1}, o_{1})} = A_{o_{1}}

; بنابراین، هیچ نقطه خروج امنی در داخل وجود ندارد

s (n_{1}, o_{1})

. به طور مشابه، برای بخش

s (o_{1}, n_{2})

هیچ نقطه خروج امنی بر اساس Lemma 3 وجود ندارد.

بنابراین، لبه های مجاور n ₂ با کاوش می شوند

n_{2} = p_{a}

. لبه

e (n_{2}, n_{3})

در ادامه بررسی خواهد شد. همانطور که در جدول 4 نشان داده شده است ، برای

e (n_{2}, n_{3})

p_{a} = n_{2}

A_{n_{2}} = {q, o_{2}}

A_{n_{3}} = {q, o_{6}}

، و

O_{(n_{2}, n_{3})} = {q}

. توسط لم 2، به عنوان مثال،

A_{n_{3}} \cup O_{(n_{2}, n_{3})} \neq A_{n_{2}}

، یک نقطه خروج امن در لبه وجود دارد. برای هر نقطه

p \in e (n_{2}, n_{3}),

o_{f}^{+}

از میان اشیاء پاسخ در انتخاب خواهد شد

A_{n_{2}} = {q, o_{2}}

، در حالیکه

o_{n}^{-}

از بین اشیاء بدون پاسخ در انتخاب خواهد شد

A_{n_{3}} \cup O_{(n_{2}, n_{3})} - A_{n_{2}} = {o_{6}, o_{4}}

. همانطور که در شکل 8 نشان داده شده است ،

o_{f}^{+} = o_{2}

زیرا برای هر نقطه

\in e (n_{2}, n_{3}),

d i s t (p, o_{2}) > d i s t (p, q)

، در حالیکه

o_{n}^{-} = o_{6}

زیرا برای هر نقطه

p \in e (n_{2}, n_{3}),

d i s t (p, o_{6}) < d i s t (p, o_{4})

. نقطه خروج امن

ω_{1}

نقطه وسط بین o ₂ و o ₆ است . به این معنا که،

d i s t (ω_{1}, o_{2}) = d i s t (ω_{1}, o_{6})

، جایی که

d i s t (ω_{1}, o_{2}) = x + 4

d i s t (ω_{1}, o_{4}) = - x + 7

برای

0 < x < 5

. در نتیجه،

x = 1.5

، به این معنی که فاصله از n ₂ تا

ω_{1}

1.5 است.

در مرحله بعد، یک نقطه خروج ایمن در لبه تعیین می کنیم

e (n_{2}, n_{5})

. همانطور که در جدول 4 نشان داده شده است ، برای

e (n_{2}, n_{5})

p_{a} = n_{2}

A_{n_{2}} = {q, o_{2}}

A_{n_{5}} = {o_{2}, o_{3}}

، و

O_{(n_{2}, n_{5})} = {o_{2}}

. توسط لم 2، به عنوان مثال،

A_{n_{6}} \cup O_{(n_{2}, n_{6})} \neq A_{n_{2}}

، یک نقطه خروج امن در لبه وجود دارد. برای هر نقطه

p \in e (n_{2}, n_{6}),

o_{f}^{+}

از میان اشیاء پاسخ در انتخاب خواهد شد

A_{n_{2}} = {q, o_{2}}

، در حالیکه

o_{n}^{-}

از بین اشیاء بدون پاسخ در انتخاب خواهد شد

A_{n_{6}} \cup O_{(n_{2}, n_{6})} - A_{n_{2}} = {o_{3}}

. همانطور که در شکل 9 نشان داده شده است ،

o_{f}^{+} = q

زیرا برای هر نقطه

\in e (n_{2}, n_{6}),

d i s t (p, q) > d i s t (p, o_{2})

، زیرا فقط یک شی بدون پاسخ برای وجود دارد

e (n_{2}, n_{6})

، از این رو،

o_{n}^{-} = o_{3}

. نقطه خروج امن

ω_{2}

نقطه وسط بین q و o ₃ است . به این معنا که،

d i s t (ω_{2}, q) = d i s t (ω_{2}, o_{3})

، جایی که

d i s t (ω_{2}, q) = x + 3

d i s t (ω_{2}, o_{3}) = - x + 10

برای

0 < x < 7

. در نتیجه،

x = 3.5

، به این معنی که فاصله از n ₂ تا

ω_{2}

“3.5” است.

به طور مشابه، یک نقطه خروج ایمن را در لبه محاسبه می کنیم

e (n_{2}, n_{7})

. شکل 10 نقطه خروج ایمن را نشان می دهد

ω_{3}

در لبه

e (n_{2}, n_{7})

. نقطه خروج ایمن

ω_{3}

نقطه وسط بین است

o_{2}

و o ₇ . به این معنا که،

d i s t (ω_{3}, o_{2}) = d i s t (ω_{3}, o_{7}),

جایی که

d i s t (ω_{3}, o_{2}) = x + 4

d i s t (ω_{3}, o_{7}) = - x + 6

برای

0 < x

. در نتیجه،

x = 1

، به این معنی که فاصله از n ₂ تا

ω_{3}

“1.” است.

4.2.2. نظارت بر اشیاء هرس شده

به یاد بیاورید که سه رویداد مختلف وجود دارد که می تواند نتایج R k NN را تحت تاثیر قرار دهد. بخش 4.1 و بخش 4.2.1 به ترتیب نظارت مستمر پرس و جو و UO را ارائه می کنند. در این قسمت به بررسی مانیتورینگ اجسام هرس شده می پردازیم. برای جلوگیری از هر گونه محاسبات اضافی، ما از ناحیه تأثیر از پیش محاسبه شده UO به عنوان منطقه نظارت برای اشیاء هرس شده استفاده می کنیم. طبق تعریف، ناحیه تأثیر یک شیء پاسخ تا زمانی معتبر است که q یک k NN از شیء پاسخ باشد، در حالی که در مورد یک شیء بدون پاسخ، ناحیه تأثیر تا زمانی معتبر می ماند که q یک عدد نباشد. یک kNN از شی بدون پاسخ. بنابراین، نظارت بر اشیایی که وارد یا خارج می شوند، ضروری است زیرا حرکت اجسام به داخل و خارج از منطقه تأثیر می تواند نتایج را تغییر دهد. بنابراین، ما نظارت بر حرکت یک شی هرس شده را تنها زمانی شروع می کنیم که وارد منطقه نفوذ یا خارج شود.

بگذارید o یک شی هرس شده باشد که در خارج از ناحیه نفوذ هر UO قرار دارد. نظارت بر شی o راه اندازی نمی شود مگر اینکه وارد منطقه نفوذ هر UO شود. هنگامی که وارد منطقه نفوذ شد، نظارت شروع می شود و مجموعه نتایج تنها زمانی تغییر می کند که NN هر UO تغییر کند. اگر حرکت یک شی هرس شده، مجموعه NN هیچ UO را تغییر ندهد، مجموعه نتیجه معتبر باقی می‌ماند و نیازی به فراخوانی مجدد فاز تعیین‌کننده UO نیست. فاز تعیین کننده UO فقط زمانی فراخوانی می شود که مجموعه NN تغییر کند.

4.3. برنامه های افزودنی

4.3.1. پرس و جوهای R k NN در شبکه های جاده ای جهت دار

بخش‌های قبلی نظارت بر پرس‌وجوهای Rk NN در یک شبکه جاده‌ای را که با نمودارهای دو طرفه نشان داده می‌شوند، مورد بحث قرار دادند . در این بخش، اصلاحات مورد نیاز برای گسترش تکنیک پیشنهادی به یک شبکه جاده هدایت‌شده را که در آن هر بخش جاده دارای جهت‌گیری خاص است، شناسایی می‌کنیم.

ابتدا، تغییرات مورد نیاز برای محاسبه نقاط خروج ایمن q را مورد بحث قرار می دهیم . اکثر تغییرات لازم است در فاز 1 (یعنی تعیین اشیاء مفید) اجرا شوند و به طور خودکار با تعریف مجدد مورد بررسی قرار می گیرند.

d i s t (p_{1}, p_{2})

. با توجه به دو نقطه p ₁ و p ₂ ، کوتاهترین فاصله مسیر

d i s t (p_{1}, p_{2})

حداقل فاصله از p ₁تا p ₂ است . با اعمال این تعریف اصلاح شده، دسته بندی اشیاء پاسخی و بدون پاسخ بدون تغییر باقی می ماند. تعریف گره بسته یکسان خواهد بود. در نتیجه، لم 1 معتبر باقی می ماند. الگوریتم 2 را می توان به روشی مشابه استفاده کرد. تنها تفاوت این است که برای تعیین UO، شبکه را در جهت معکوس، یعنی یک لبه بررسی می کنیم

e (n_{1}, n_{2})

لبه مجاور در نظر گرفته می شود

n_{1}

اگر و فقط اگر لبه دو طرفه باشد یا جهت لبه از آن باشد

n_{2}

به

n_{1}

فاز 2 هم همینطور است، به جز تعیین

o_{k + 1}

یا

o_{k}

شبکه راه را در جهت لبه ها گسترش می دهیم. علاوه بر این، محاسبه منطقه نفوذ

o^{+}

به جز فاصله یکسان است

d i s t (o^{+}, o_{k + 1})

کوتاه ترین مسیر از

o^{+}

به

o_{k + 1}

به جای کوتاه ترین مسیر از

o^{+}

به

o_{k + 1}

. به طور مشابه، محاسبه منطقه نفوذ از

o^{-}

به جز فاصله یکسان است

d i s t (o^{-}, o_{k})

کوتاه ترین مسیر از

o^{-}

به

o_{k}

به جای کوتاه ترین مسیر بین

o^{-}

o_{k}

. فاز 3 مانند شبکه راه های هدایت شده است. در نهایت، ما تغییرات در محاسبه نقاط خروج ایمن UO را مورد بحث قرار می دهیم. SEA به روشی مشابه عمل می کند با این تفاوت که فقط شبکه را در جهت لبه ها بررسی می کند. بقیه روش، یعنی لم 2، لم 3، و تعریف

Ω

، بدون تغییر باقی می ماند.

4.3.2. پرس و جوهای R k NN در شبکه های جاده ای پویا

در این بخش، CORE-X را به شبکه‌های جاده‌ای پویا گسترش می‌دهیم که فاصله شبکه بسته به شرایط ترافیکی تغییر می‌کند. نتیجه پرس و جو یا ناحیه امن پرس و جو یا شی داده اغلب ممکن است با به روز رسانی وزن برخی از یال ها باطل شود، حتی اگر شی پرس و جو q یا شی داده o در منطقه امن مربوطه خود باقی بماند. بنابراین، ما یک منطقه امن فشرده را برای کاهش فراوانی ارزیابی‌های منطقه امن در یک شبکه جاده‌ای پویا معرفی می‌کنیم. در این بخش، منطقه امن در یک شبکه جاده ایستا به عنوان منطقه امن اصلی مشخص می شود.

S R_{o r}

، در حالی که منطقه امن در یک شبکه جاده پویا به عنوان منطقه امن فشرده نشان داده می شود،

S R_{c o}

، که به وضوح زیر مجموعه ای از

S R_{o r}

. برای ساده‌تر کردن توضیح، تأثیر یک شبکه جاده‌ای پویا را تنها با توجه به q مطالعه می‌کنیم .

بر خلاف منطقه امن اصلی، منطقه امن فشرده تنها در توالی فعال تعیین می شود. شکل 11 تفاوت بین را نشان می دهد

S R_{o r}

S R_{c o}

، جایی که

n_{2} n_{3}

لبه فعال است. خط پررنگ در شکل 11 a نشان می دهد که برای

S R_{o r}

s_{1}

s_{2}

، و

s_{3}

نقاط خروجی امن هستند در شبکه های جاده ای پویا، منطقه امن به لبه فعال فشرده می شود

n_{2} n_{5}

همانطور که در شکل 11 ب در خطوط پررنگ نشان داده شده است.

در مرحله بعد، ما یک منطقه بحرانی را برای نظارت موثر بر اعتبار منطقه ایمن هنگامی که وزن لبه تغییر می‌کند، معرفی می‌کنیم. منطقه بحرانی CR به صورت تعریف شده است

C R = I R^{+} \cup I R^{-}

، جایی که

I R^{+}

I R^{-}

به ترتیب ناحیه تأثیر اشیاء پاسخ و بدون پاسخ هستند. طبق تعریف، منطقه بحرانی شامل تمام نقاط است

p_{c r}

به طوری که

p_{c r} \in {I R^{+}, I R^{-}}

. همانطور که در شکل 12 الف نشان داده شده است، دو شی داده وجود دارد

o_{1}

o_{2}

و یک شی پرس و جو q. برای

k = 1

، بدیهی است که

o_{1}

یک شی پاسخ است زیرا

q = N N (o_{1})

o_{2}

یک شی بدون پاسخ است زیرا

o_{1} = N N (o_{2})

. بنابراین، منطقه بحرانی شامل تمام نقاط است

p_{c r} \in {I R (o_{1}), I R (o_{2})},

به عنوان خط پررنگ در شکل 12 b نشان داده شده است

c_{1}

c_{2}

به عنوان نقاط مرزی زمانی که وزن لبه مربوط به ناحیه بحرانی تغییر می کند، ناحیه امن q ممکن است تحت تأثیر قرار گیرد. بنابراین، مناطق بحرانی q ذخیره و نمایه می شوند تا به سرعت بررسی شود که آیا یک تغییر بر منطقه امن تأثیر می گذارد یا خیر. اگر منطقه نفوذ هر UO به روز شود، منطقه بحرانی q نیز بر این اساس به روز می شود. واضح است که تغییرات لبه هایی که با ناحیه بحرانی مرتبط نیستند را می توان با خیال راحت نادیده گرفت.

شکل 13 a ناحیه بحرانی را با خطوط پررنگ در زمان نشان می دهد

t_{i}

. فرض کنید، به دلیل شرایط ترافیکی سنگین، وزن دو لبه

n_{1} n_{2}

n_{2} n_{5}

در زمان تغییر می کنند

t_{j}

از “3” تا “6” همانطور که در شکل 13 نشان داده شده است . به روز رسانی به لبه

n_{2} n_{5}

، که با یک منطقه بحرانی مرتبط است، ممکن است منطقه امن را تحت تاثیر قرار دهد. با این حال، به روز رسانی به لبه

n_{1} n_{2}

، که بخشی از یک منطقه بحرانی نیست، بر منطقه امن تأثیر نمی گذارد و بنابراین می توان با خیال راحت از آن چشم پوشی کرد.

4.3.3. پرس و جوهای دو رنگی R k NN

برخلاف حالت تک رنگ که در آن همه اشیا از یک نوع هستند، در RNN دو رنگی ، ما بین دو نوع شی O و S تمایز قائل می شویم . برای یک شی پرس و جو از نوع S ، هدف تعیین اشیاء داده از نوع O است که نقطه پرس و جو نزدیکترین شی آنها در مجموعه S است . با این تفاوت اساسی بین MR k NN و BR k NN، CORE-X روش شناسی یکسانی را برای مدیریت هر دو نوع پرس و جو حفظ می کند. این بخش تغییرات مورد نیاز در تکنیک پیشنهادی برای پردازش پرس و جوهای BR k NN را ارائه می دهد.

در تعیین فاز UO، فقط اشیاء از نوع S به عنوان اشیاء مسدود کننده برای هرس شبکه در نظر گرفته می شوند. بنابراین، یک گره بسته را می توان به عنوان یک گره n که یک شی برای آن وجود دارد، دوباره تعریف کرد $s \in S$ به طوری که $d i s t (n, s) < d i s t (n, q)$ . باقی مانده لما 1 بدون تغییر باقی می ماند. اشیاء نوع O که در شبکه هرس نشده قرار دارند، به عنوان اشیاء UO در نظر گرفته می شوند، در حالی که اشیاء نوع S در شبکه هرس نشده، اشیاء فعال نامیده می شوند.
مشابه با MR k NN، اشیاء UO به اشیاء پاسخی و غیر پاسخی طبقه بندی می شوند. اشیاء پاسخ برای پرس و جوهای BRkNN را می توان به عنوان یک شی o برای آن تعریف کرد $d i s t (o, q) < d i s t (o, s_{k + 1})$ که در آن s _k_{+1 (}k +1)امین شیء NN o در مجموعه داده S است . به طور مشابه، یک شیء بدون پاسخ به عنوان یک شیء o تعریف می شود که $d i s t (o, q) > d i s t (o, s_{k})$ ، که در آن s _k k امین شی NN o در مجموعه داده S است .
منطقه تأثیر یک شی پاسخ به صورت تعریف می شود $I R^{+} = {p | d i s t (o^{+}, p) \leq d i s t (o^{+}, s_{k + 1})}$ ، جایی که $d i s t (o^{+}, s_{k + 1})$ فاصله بین شی پاسخ و ( k +1)امین NN در مجموعه S است . به طور مشابه، منطقه تأثیر یک شیء بدون پاسخ به این صورت تعریف می شود $I R^{-} = {p | d i s t (o^{-}, p) \leq d i s t (o^{-}, s_{k})},$ جایی که $d i s t (o^{-}, s_{k})$ فاصله بین شی بی پاسخ و k نزدیکترین شی در مجموعه S است . فاز 3 برای BR k NN بدون تغییر باقی می ماند.
محاسبه نقاط خروج ایمن برای UO یکسان است. تنها تفاوت این است که برای BR k NN، دورترین شی پاسخ و نزدیکترین شی غیر پاسخ متعلق به مجموعه S است . بنابراین، نقطه خروج امن نقطه مرکزی بین است $s_{f}^{+}$ و $s_{n}^{-}$ .
ناحیه امن یک شی فعال را می توان به روشی مشابه q محاسبه کرد زیرا هر دو به یک نوع داده تعلق دارند.

4.4. تحلیل پیچیدگی های زمانی و مکانی

در این بخش، پیچیدگی‌های زمانی و مکانی الگوریتم CORE-X را تحلیل می‌کنیم. به یاد بیاورید که ما در حال مطالعه پرس و جوهای Rk NN در یک شبکه جاده بدون جهت هستیم که به صورت G = ( N ، E، W ) نمایش داده می شود. اجازه دهید

N_{k}^{p}

E_{k}^{p}

به ترتیب مجموعه گره ها و لبه های نقطه p در داخل k اشیاء NN باشد.

ابتدا، پیچیدگی زمانی CORE-X را تحلیل می‌کنیم. CORE-X مجموعه ای از اشیاء UO را با عبور از شبکه جاده از محل پرس و جو q ، که دارای پیچیدگی زمانی است، بازیابی می کند.

T (2 | E_{k}^{q} | + | N_{k}^{q} | l o g N_{k}^{q})

زیرا یک یال حداکثر دو بار بازدید می شود، ابتدا برای تعیین اشیاء پاسخ و سپس برای تعیین اشیاء مفید بدون پاسخ. در اینجا، پیچیدگی زمانی از

T (| N_{k}^{q} | l o g N_{k}^{q})

به پیچیدگی زمانی الگوریتم کوتاه ترین مسیر از یک نقطه پرس و جو تا k شی RNN اشاره دارد [ 29 ]. سپس، CORE-X نقاط خروج ایمن را با استفاده از اشیاء UO بازیابی شده محاسبه می کند. برای هر شی داده

o \in U O

، ناحیه نفوذ شی داده o برای کشف نقاط خروج ایمن جستجو می شود که دارای پیچیدگی زمانی است

T (| E_{k}^{q} | + | N_{k}^{q} | l o g N_{k}^{q})

. بنابراین، پیچیدگی زمانی CORE-X است

T ((2 | E_{k}^{q} | + | N_{k}^{q} | l o g N_{k}^{q}) + | U O | (| E_{k}^{q} | + | N_{k}^{q} | l o g N_{k}^{q}))

. پیچیدگی کلی زمانی CORE-X را می توان به بهبود بخشید

T ((2 | E_{k}^{q} | + | N_{k}^{q} |) + | U O | (| E_{k}^{q} | + | N_{k}^{q} |))

با استفاده از ترتیب پیش پردازش شده گره ها در شبکه های جاده ایستا. با این حال، در مورد شبکه‌های جاده‌ای پویا، تکنیک پیش‌پردازش طبیعتاً ناچیز است، زیرا به‌روزرسانی وزن برخی از لبه‌ها اغلب اطلاعات پیش‌پردازش‌شده را باطل می‌کند. فضای جستجوی CORE-X به منطقه ای در فاصله k RNN از q و ( k +1)NN از اشیاء داده تبدیل می شود، زیرا برای محاسبه ناحیه تأثیر یک NN لازم است که ( k +1)امین NN کاوش شود. پاسخ شی در نهایت، پیچیدگی فضایی CORE-X است

| O_{k}^{q} | + | O_{k + 1}^{U O} |

5. ارزیابی عملکرد

در این بخش، عملکرد الگوریتم پیشنهادی (CORE-X) را از طریق آزمایش‌های شبیه‌سازی ارزیابی می‌کنیم. ما تنظیمات آزمایشی خود را در بخش 5.1 توصیف می کنیم و نتایج تجربی خود را برای شبکه های جاده ایستا و پویا به ترتیب در بخش 5.2 و بخش 5.3 ارائه می کنیم .

5.1. تنظیمات آزمایشی

آزمایش‌های ما با استفاده از یک شبکه جاده واقعی [ 30 ] برای شهرستان سن‌واکین، کالیفرنیا، ایالات‌متحده انجام شد که شامل 18263 گره و 23874 لبه است. شبکه جاده شامل مجموعه ای از پرس و جوها و مجموعه ای از اشیاء داده است که می توانند به طور تصادفی در شبکه حرکت کنند. ما اشیاء متحرک (اعم از پرس و جو و اشیاء داده) را با استفاده از مولد شی متحرک مبتنی بر شبکه [ 31 ] شبیه سازی می کنیم. در هر آزمایش، عملکرد را با تغییر یک پارامتر واحد در محدوده مشخص شده ارزیابی کردیم. تمام پارامترهای دیگر بر روی مقادیر پیش فرض نشان داده شده با پررنگ تنظیم شدند. همه پرس و جوها به طور مداوم برای 600 مهر زمانی نظارت شدند. جدول 5 پارامترهای پیش فرض مورد استفاده در آزمایشات ما را فهرست می کند.

ما عملکرد CORE-X را با استفاده از معیارهای زیر ارزیابی کردیم: (1) مقدار کل زمان CPU سرور به ازای هر مُهر زمان، که زمان پردازش پرس و جو را نشان می‌دهد و (2) هزینه کل ارتباط را به عنوان تعداد کل نقاط (یعنی به‌روزرسانی‌های مکان) نشان می‌دهد. ارسال شده توسط داده ها و اشیاء پرس و جو، و نتایج پرس و جو و نقاط خروج ایمن که توسط سرور برگردانده می شود) بین کلاینت ها و سرور منتقل می شود. کل زمان پردازش پرس و جو تحت تسلط محاسبات (یعنی تعیین UO، منطقه تأثیر محاسبات و نقاط خروج ایمن) است که در انتهای سرور انجام می شود، بنابراین ما فقط زمان CPU را در سرور اندازه گیری می کنیم. مصرف باتری و پهنای باند بی سیم معمولاً با مقدار داده های منتقل شده بین اشیاء (کلاینت ها) و سرورها افزایش می یابد. بنابراین ما از مقدار داده های منتقل شده به عنوان یک معیار برای ارزیابی هزینه ارتباطات استفاده می کنیم. برای شبکه های جاده ای استاتیک، ما CORE-X را با الگوریتم پیشرفته SAC مقایسه کردیم [8 ] و یک الگوریتم پایه. SAC به طور مداوم پرس و جوهای Rk NN را با اختصاص یک منطقه امن به پرس و جو و اشیاء داده نظارت می کند ، در حالی که الگوریتم خط پایه نتایج را در هر مهر زمانی دوباره محاسبه می کند. برای شبکه‌های جاده‌ای پویا، ما الگوریتم پیشنهادی را تنها با خط پایه مقایسه کردیم زیرا SAC به شبکه‌های جاده‌ای پویا رسیدگی نمی‌کند. تمامی الگوریتم ها در جاوا پیاده سازی و بر روی کامپیوتر رومیزی، 2.80 گیگاهرتز، Intel Core i5 با 4 گیگابایت حافظه اجرا شدند.

5.2. نتایج تجربی برای شبکه های جاده ایستا

شکل 14 a عملکرد پایه، SAC و CORE-X را با توجه به تعداد اشیاء نشان می دهد. توجه داشته باشید که هر سه الگوریتم به افزایش تعداد اشیاء حساس هستند زیرا الگوریتم باید به‌روزرسانی‌های تعداد زیادی از اشیاء را بررسی کند. عملکرد SAC با تعداد زیادی از اشیاء داده کاهش می یابد زیرا فیلتر و تأیید اشیاء داده بیشتری مورد نیاز است. زمان پردازش پرس و جو CORE-X با افزایش اشیاء داده عمدتاً به دلیل ناحیه نفوذ و

ω

برای تعداد زیادی از اشیاء باید محاسبه شود. با این حال، CORE-X بهتر از پایه و SAC مقیاس می شود.

شکل 14 ب مقایسه هزینه محاسباتی CORE-X، SAC و خط پایه را با مقادیر مختلف N _qry نشان می دهد . نتایج تجربی نشان می دهد که زمان محاسبه همه الگوریتم ها با افزایش تعداد پرس و جوها افزایش می یابد. با این حال، CORE-X و SAC به طور قابل توجهی زمان CPU کمتری را نسبت به خط پایه مصرف کردند، زیرا نتایج پرس و جو تا زمانی معتبر هستند که پرس و جو و اشیاء داده در منطقه امن مربوطه خود باقی بمانند. شکل 14ج، تأثیر نسبت پرس و جو و اشیاء داده در حال حرکت را مطالعه می کند. با افزایش درصد اجسام متحرک، عملکرد همه الگوریتم ها کاهش می یابد. زمان محاسبات CORE-X عمدتاً افزایش می‌یابد زیرا با تحرک داده‌ها، منطقه امن بیشتر منقضی می‌شود و الگوریتم باید نتایج را مرتباً دوباره محاسبه کند.

شکل 14 d تأثیر سرعت اشیاء داده و پرس و جو را بر عملکرد CORE-X، SAC و الگوریتم های پایه نشان می دهد. نتایج تجربی نشان می‌دهد که الگوریتم‌های پایه و SAC هزینه‌های محاسباتی ثابتی را متحمل می‌شوند. عملکرد SAC به طور قابل توجهی تحت تأثیر سرعت قرار نمی گیرد زیرا اشیاء کاندید باید بدون توجه به سرعت آنها در هر مهر زمانی تأیید شوند. برعکس، عملکرد CORE-X با افزایش سرعت اشیاء به تدریج کاهش می‌یابد زیرا اشیا بیشتر مناطق امن مربوطه خود را ترک می‌کنند. شکل 14 e زمان پردازش پرس و جو CORE-X، SAC و خط پایه را به عنوان تابعی از k نشان می دهد.تعداد RNN های درخواستی نتایج تجربی نشان می‌دهد که زمان محاسبه همه الگوریتم‌ها با افزایش مقدار k افزایش می‌یابد . این مورد انتظار است زیرا با افزایش k ، اشیاء داده بیشتری مورد نیاز است که کاوش و تأیید شوند. با این حال، CORE-X بهتر از SAC و پایه است.

در شکل 15 الف، تأثیر تعداد اشیاء بر هزینه ارتباط را مطالعه می کنیم. این شکل نشان می دهد که با افزایش تعداد اشیا، تعداد پیام های ارسال شده توسط همه الگوریتم ها افزایش می یابد. با این حال، واضح است که الگوریتم‌های مبتنی بر منطقه امن SAC و CORE-X به طور قابل‌توجهی از خط پایه بهتر عمل کردند. الگوریتم پیشنهادی عملکرد برتر را در مقایسه با SAC نشان می‌دهد، زیرا زمانی که پرس و جو و اشیاء داده در نقاط خروج امن باقی می‌مانند، ارتباط کلاینت-سرور مورد نیاز نیست، در حالی که در SAC، اشیاء کاندید باید مکان خود را برای تأیید به سرور گزارش دهند. مکان آنها را تغییر دهید

شکل 15 ب تأثیر تعداد پرس و جوها را بر هزینه ارتباط نشان می دهد. خط مبنا بدون توجه به مقادیر مختلف N _qry هزینه ارتباط ثابت را متحمل می شود . برعکس، هزینه ارتباط CORE-X و SAC با افزایش تعداد درخواست‌ها افزایش می‌یابد. هزینه ارتباط SAC عمدتاً به این دلیل افزایش می‌یابد که اشیاء داده بیشتری در هر مهر زمانی مورد نیاز است که تأیید شود، که تعداد به‌روزرسانی‌های آغاز شده توسط سرور را افزایش می‌دهد. CORE-X تنها زمانی شی مفید را تأیید می کند که از منطقه امن خود خارج شود، که به طور قابل توجهی هزینه ارتباط را کاهش می دهد.

شکل 15 c روند عملکرد CORE-X، SAC و خط پایه را به عنوان تابعی از تحرک پرس و جو و شی داده نشان می دهد. همانطور که انتظار می رود، خط پایه بدترین عملکرد را دارد زیرا باید هر شی داده را در هر مهر زمانی به روز کند. هزینه ارتباط SAC به دلیل روش تأیید گران قیمت آن از CORE-X بالاتر است. شکل 15 d کل هزینه ارتباط CORE-X، SAC و خط مبنا را با توجه به سرعت داده ها و اشیاء پرس و جو نشان می دهد. این شکل روندهای مشابه شکل 14 د را نشان می دهد. SAC هزینه ارتباط ثابتی را متحمل می شود زیرا درخواست آغاز شده توسط سرور برای تأیید اشیاء نامزد به سرعت بستگی ندارد. برای CORE-X، با افزایش سرعت، اشیاء زودتر به نقطه خروج ایمن می رسند که هزینه ارتباط را افزایش می دهد. همانطور که درشکل 15 e، هزینه های ارتباطی CORE-X، SAC و الگوریتم پایه با k افزایش می یابد . هر دو CORE-X و SAC بهتر از روش پایه عمل می کنند. با این حال، CORE-X به دلیل هزینه تأیید پایین به طور قابل توجهی از SAC برای همه موارد بهتر است.

5.3. نتایج تجربی برای شبکه های جاده ای پویا

شکل 16 مقایسه ای از زمان پردازش پرس و جو را برای یک شبکه جاده پویا نشان می دهد که در آن مقادیر R _upd (%) همه یال ها وزن خود را در هر مهر زمانی تغییر می دهند. لبه های به روز شده بدون توجه به مکان داده ها و اشیاء پرس و جو به طور تصادفی انتخاب می شوند. طول یک لبه به روز شده به طور تصادفی از 0.1 تا 10 برابر طول اصلی انتخاب می شود.

شکل 16 a زمان پردازش پرس و جو را به عنوان تابعی از درصد لبه های به روز شده ( R _upd ) در هر زمان نشان می دهد. اینجا،

R_{u p d} = 0

نشان دهنده یک شبکه جاده ایستا است. به طور طبیعی، زمان پردازش پرس و جو در خط مبنا بدون توجه به مقدار R _upd تقریباً ثابت است ، زیرا اشیاء پرس و جو در خط مبنا در هر مهر زمانی پرس و جوهای Rk NN را صادر می کنند. زمان پردازش پرس و جو CORE-X با R _upd افزایش می یابد . این عمدتاً به این دلیل است که اگر یک لبه با منطقه بحرانی داده یا شی پرس و جو مرتبط باشد، منطقه امن یک پرس و جو و شی داده باید به روز شود. رعایت کنید برای

R_{u p d} \leq 25

، CORE-X به طور قابل توجهی بهتر از پایه عمل می کند، در حالی که برای

R_{u p d} = 50

، زمان پردازش پرس و جو CORE-X بیشتر از خط پایه است.

شکل 16 ب تأثیر تعداد اشیاء داده بر زمان پردازش پرس و جو را نشان می دهد. زمان محاسبه برای هر دو الگوریتم معمولاً با N _داده افزایش می یابد . در این مورد، CORE-X به طور قابل توجهی بهتر از پایه است. در شکل 16 ج، اثر N _qry بر هزینه محاسبات را مطالعه می کنیم. نتایج تجربی نشان می دهد که هر دو الگوریتم به افزایش تعداد اشیاء پرس و جو حساس هستند. زمان پردازش پرس و جو CORE-X عمدتاً به این دلیل افزایش می یابد که محاسبه منطقه بحرانی و منطقه امن برای اشیاء بیشتر مورد نیاز است. شکل 16d روندی را نشان می دهد که هزینه محاسبات هر دو الگوریتم با افزایش تحرک پرس و جو و شی داده افزایش می یابد. با این حال، مقیاس CORE-X به طور قابل توجهی بهتر از پایه است.

شکل 16 e زمان پردازش پرس و جو CORE-X و خط پایه به عنوان تابعی از سرعت داده ها و اشیاء پرس و جو است. Baseline یک زمان پردازش پرس و جو تقریباً پایدار دارد. با این حال، هزینه محاسباتی CORE-X با V _obj افزایش می‌یابد، زیرا با حرکت سریع‌تر اشیا، زودتر به نقاط خروج امن مربوطه می‌رسند و در نتیجه به‌روزرسانی‌های مکرر نتایج پرس و جو می‌شود. شکل 16 f تأثیر k تعداد RNN های درخواستی را بر عملکرد هر دو الگوریتم نشان می دهد. همانطور که انتظار می رود، محاسبه هر دو الگوریتم با افزایش k افزایش می یابدارزش. با CORE-X، ناحیه بحرانی اشیاء داده بیشتری که نیاز به محاسبه دارند، اندازه ناحیه بحرانی را افزایش می‌دهد. در نتیجه، تعداد لبه‌های مرتبط با ناحیه بحرانی نیز افزایش می‌یابد که زمان پردازش پرس و جو را افزایش می‌دهد.

شکل 17 مقایسه ای از هزینه ارتباط CORE-X و خط پایه را با استفاده از شرایط مشابه در شکل 16 نشان می دهد . شکل 17 a اثر R _upd را بر هزینه ارتباط هر دو الگوریتم نشان می دهد. عملکرد خط پایه به طور قابل توجهی تحت تاثیر R _upd قرار نمی گیرد . با این حال، هزینه ارتباط CORE-X با R _upd افزایش می‌یابد ، زیرا مناطق بحرانی داده‌ها و اشیاء پرس و جو با افزایش R _upd بیشتر به‌روزرسانی می‌شوند . در نتیجه، مناطق امن پرس و جو و اشیاء داده دوباره ارزیابی می شوند.

در شکل 17 ب، تأثیر کاردینالیته اشیاء داده بر هزینه های ارتباطی را مطالعه می کنیم. نتایج تجربی نشان می‌دهد که CORE-X بهتر از خط پایه عمل می‌کند، زیرا در CORE-X، ارتباط سرور-کلینت تنها زمانی مورد نیاز است که پرس و جو و اشیاء داده مناطق امن خود را ترک کنند یا زمانی که مناطق بحرانی داده‌ها و اشیاء پرس و جو به روز می‌شوند. شکل 17c هزینه ارتباط CORE-X و خط پایه را با توجه به تعداد اشیاء پرس و جو نشان می دهد. توجه داشته باشید که هزینه ارتباط خط مبنا به تعداد اشیاء پرس و جو بستگی ندارد زیرا هر شیء داده هر زمان که مکان خود را تغییر می دهد مکان خود را گزارش می دهد. از سوی دیگر، هزینه ارتباط CORE-X افزایش می یابد زیرا برای تعداد زیادی از اشیاء پرس و جو، اشیاء داده بیشتری مورد نیاز است تا تأیید شوند.

شکل 17 د تأثیر تحرک پرس و جو و شی داده را بر هزینه های ارتباطی نشان می دهد. واضح است که تعداد نقاط منتقل شده با افزایش R _obj افزایش می یابد . با این حال، CORE-X به طور مداوم عملکرد بهبود یافته ای را در مقایسه با پایه ارائه می دهد. شکل 17 اثر سرعت داده ها و اشیاء پرس و جو را بر هزینه های ارتباطات نشان می دهد. در CORE-X، تعداد نقاط منتقل شده با V _obj به همان دلیلی که قبلا در مورد شکل 15 d بحث شد، افزایش می‌یابد. همانطور که در شکل 17 نشان داده شده است ، هزینه های ارتباطی CORE-X و الگوریتم پایه با k افزایش می یابد.. این عمدتاً به این دلیل است که تعداد اشیاء داده ای که نیاز به تأیید و نظارت دارند با k افزایش می یابد .

6. نتیجه گیری

ما یک الگوریتم جدید به نام CORE-X برای پردازش کارآمد k نزدیکترین همسایه معکوس پیوسته (Rk ) پیشنهاد کردیم.NN) پرس و جوها در شبکه های جاده ای که در آن اشیاء پرس و جو و داده در حال حرکت هستند. رویکرد پیشنهادی مبتنی بر نقاط خروج ایمن است که می تواند نه تنها هزینه محاسباتی بلکه هزینه ارتباط بین سرور و شی پرس و جو را نیز به طور قابل توجهی بهبود بخشد. علاوه بر این، ما تکنیک‌های هرس را ارائه کردیم و بر نظارت بر منطقه تأثیر گذاشتیم تا از پردازش اشیاء داده‌های نامربوط جلوگیری کنیم. CORE-X می تواند با معرفی یک منطقه امن فشرده و منطقه بحرانی، به طور موثر یک منطقه امن در یک شبکه جاده پویا ایجاد کند. نتایج آزمایش‌های انجام‌شده با استفاده از مجموعه داده‌های واقعی تأیید می‌کند که الگوریتم پیشنهادی به طور قابل‌توجهی هزینه محاسبات و هزینه ارتباطات را در مقایسه با یک الگوریتم پایه و پیشرفته (SAC) کاهش می‌دهد.

چندین جهت امیدوارکننده برای تحقیقات آینده وجود دارد. اول، پرس و جوهای RNN را می توان برای سیستم های آگاه از حریم خصوصی مورد مطالعه قرار داد تا از حریم خصوصی مکان یک شی پرس و جو از یک مهاجم اطمینان حاصل شود. علاوه بر این، این مطالعه را می توان برای اشیاء داده نامشخص، که ممکن است مکان دقیقی نداشته باشند، گسترش داد. تعیین مکان تقریبی آنها و ایجاد مرزهای دقت در نتایج پرس و جو بسیار مهم است.

منابع

سیونزو، دی. بوونانو، آ. D’Urso، M. Palmieri, F. طبقه بندی توزیع شده اهداف متحرک چندگانه با شبکه حسگر بی سیم باینری. در مجموعه مقالات چهاردهمین کنفرانس بین المللی در همجوشی اطلاعات (FUSION)، شیکاگو، IL، ایالات متحده آمریکا، 5-8 ژوئیه 2011; صص 1-8.
بوونانو، آ. D’Urso، M. پریسکو، جی. فلاکو، م. ملیادو، EF; ماتی، م. پالمیری، اف. Ciuonzo، D. شبکه های حسگر موبایل مبتنی بر سیستم عامل های مستقل برای امنیت داخلی. در مجموعه مقالات کارگاه Tyrrhenian در مورد پیشرفت در رادار و سنجش از دور (TyWRRS)، ناپل، ایتالیا، 12-14 سپتامبر 2012. صص 80-84.
چو، اچ. کوون، اس. Chung, T. یک الگوریتم خروج ایمن برای نظارت مداوم نزدیکترین همسایه در شبکه های جاده ای. اوباش Inf. سیستم 2013 ، 9 ، 37-53. [ Google Scholar ] [ CrossRef ]
چو، اچ. ریو، ک. Chung, T. یک الگوریتم کارآمد برای محاسبه نقاط خروج ایمن پرس و جوهای محدوده متحرک در شبکه های جاده هدایت شده. Inf. سیستم 2014 ، 41 ، 1-19. [ Google Scholar ] [ CrossRef ]
وانگ، اچ. Zimmermann, R. پردازش پرس و جوهای محدوده مبتنی بر مکان پیوسته بر روی اجسام متحرک در شبکه های جاده ای. IEEE Trans. بدانید. مهندسی داده 2011 ، 23 ، 1065-1078. [ Google Scholar ] [ CrossRef ]
یونگ، دی. ییو، م. Lo, E. یک رویکرد خروج ایمن برای جستجوهای محدوده متحرک مبتنی بر شبکه کارآمد. دانستن داده ها مهندس 2012 ، 72 ، 126-147. [ Google Scholar ] [ CrossRef ]
ژانگ، جی. زو، ام. پاپادیاس، دی. تائو، ی. لی، دی. پرس و جوهای فضایی مبتنی بر مکان. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 2003 در مدیریت داده ها، سن دیگو، کالیفرنیا، ایالات متحده آمریکا، 10-12 ژوئن 2003. صص 443-454.
چیما، م. Lin، MX; ژانگ، ی. ژانگ، دبلیو. Li، X. جستارهای معکوس پیوسته k نزدیکترین همسایگان در فضای اقلیدسی و در شبکه های فضایی. VLDB J. 2012 ، 21 ، 69-95. [ Google Scholar ] [ CrossRef ]
کورن، اف. Muthukrishnan، S. مجموعه های نفوذ بر اساس پرس و جوهای معکوس نزدیکترین همسایه. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD در سال 2000 در مورد مدیریت داده ها، دالاس، تگزاس، ایالات متحده آمریکا، 16-18 می 2000. ص 201-212.
استانویی، آی. آگراوال، اس. Abbadi, A. معکوس کردن پرس و جوهای نزدیکترین همسایه برای پایگاه های داده پویا. در مجموعه مقالات کارگاه ACM SIGMOD در مورد مسائل تحقیقاتی در داده کاوی و کشف دانش، دالاس، تگزاس، ایالات متحده آمریکا، 14 مه 2000. صص 44-53.
تائو، ی. پاپادیاس، دی. لیان، ایکس. جستجوی k NN در ابعاد دلخواه. در مجموعه مقالات سی امین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تورنتو، ژاپن، 31 اوت تا 3 سپتامبر 2004. صص 744-755.
کلاهدوزان، م. شهابی، سی. ورونوی مبتنی بر k نزدیکترین همسایه جستجو برای پایگاه داده شبکه فضایی. در کارگاه ACM SIGMOD در مورد مسائل تحقیقاتی در داده کاوی و کشف دانش، مجموعه مقالات سی امین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تورنتو، ژاپن، 31 اوت تا 3 سپتامبر 2004 . ACM: نیویورک، نیویورک، ایالات متحده آمریکا؛ صص 840-851.
گائو، ی. ژنگ، بی. چن، جی. لی، دبلیو. تره فرنگی.؛ لی، Q. جستارهای k معکوس قابل مشاهده – نزدیکترین همسایه. در مجموعه مقالات بیست و پنجمین کنفرانس بین المللی IEEE در زمینه مهندسی داده، شانگهای، چین، 29 مارس تا 2 آوریل 2009. ص 1314–1327.
لی، جی. فن، پ. لی، ی. Du، J. یک تکنیک کارآمد برای پردازش پیوسته k-نزدیکترین همسایه بر روی اجسام متحرک در یک شبکه جاده ای. در مجموعه مقالات دهمین کنفرانس بین المللی IEEE در زمینه کامپیوتر و فناوری اطلاعات (CIT)، برادفورد، انگلستان، 29 ژوئن تا 1 ژوئیه 2010. صص 627-634.
آهنگ، ز. Roussopoulos، N. K-نزدیکترین همسایه جستجو برای نقطه جستجوی متحرک. در مجموعه مقالات سمپوزیوم بین المللی در پایگاه های داده مکانی و زمانی (SSTD)، ردوندو بیچ، کالیفرنیا، ایالات متحده آمریکا، 12 تا 15 جولای 2001. ص 79-96.
سان، اچ. جیانگ، سی. لیو، جی. Sun، L. پرس و جوهای معکوس پیوسته نزدیکترین همسایه در مورد اجسام متحرک در شبکه های جاده ای. در مجموعه مقالات نهمین کنفرانس بین المللی مدیریت اطلاعات عصر وب (WAIM)، Zhangjiajie، هونان، چین، 20-22 ژوئیه 2008.
ییو، م. مامولیس، ن. پاپادیاس، دی. تائو، ی. نزدیکترین همسایه را در نمودارهای بزرگ معکوس کنید. IEEE Trans. بدانید. مهندسی داده 2006 ، 18 ، 540-553. [ Google Scholar ]
بنتیس، آر. جنسن، سی. کارچیاوسکاس، جی. Saltenis، S. جستجوهای نزدیکترین همسایه و معکوس نزدیکترین همسایه برای اجسام متحرک. در مجموعه مقالات سمپوزیوم مهندسی و کاربردهای پایگاه داده بین المللی، ادمونتون، AB، کانادا، 17-19 ژوئیه 2002. صص 44-53.
شیا، تی. Zhang، D. نظارت معکوس مداوم نزدیکترین همسایه. در مجموعه مقالات بیست و دومین کنفرانس بین المللی مهندسی داده (ICDE)، آتلانتا، GA، ایالات متحده آمریکا، 3-7 آوریل 2006. پ. 77.
کانگ، جی. موکبل، م. شکر، س. شیا، تی. ژانگ، دی. ارزیابی مستمر نزدیکترین همسایگان معکوس تک رنگ و دو رنگ. در مجموعه مقالات بیست و سومین کنفرانس بین المللی مهندسی داده IEEE (ICDE)، استانبول، ترکیه، 16-20 آوریل 2007. ص 806-815.
وو، دبلیو. یانگ، اف. چان، سی. قهوهای مایل به زرد، K. پیوسته معکوس k -نزدیکترین همسایه نظارت. در مجموعه مقالات نهمین کنفرانس بین المللی مدیریت داده های تلفن همراه (MDM)، پکن، چین، 27-30 آوریل 2008. صص 132-139.
چیما، م. لین، ایکس. ژانگ، دبلیو. Zhang، Y. منطقه نفوذ: پردازش معکوس k پرس و جوهای نزدیکترین همسایگان. در مجموعه مقالات بیست و هفتمین کنفرانس بین المللی IEEE در مهندسی داده (ICDE)، هانوفر، آلمان، 11-16 آوریل 2011. صص 577-588.
صفر، م. ابراهیمی، د. پردازش پرس و جوی معکوس نزدیکترین همسایه مبتنی بر Taniar، D. Voronoi در شبکه های فضایی. چندتایی. سیستم 2009 ، 15 ، 295-308. [ Google Scholar ] [ CrossRef ]
لی، جی. لی، ی. لی، جی. شو، ال. یانگ، ف. نظارت معکوس پیوسته k نزدیکترین همسایه بر روی اجسام متحرک در شبکه های جاده ای. Inf. سیستم 2010 ، 35 ، 860-883. [ Google Scholar ]
Gotoh, Y. یک روش مسیریابی ساده برای پرس و جوهای k- نزدیکترین همسایه معکوس در شبکه های فضایی. در مجموعه مقالات هفدهمین کنفرانس بین المللی IEEE در مورد سیستم های اطلاعاتی مبتنی بر شبکه، سالرنو، ایتالیا، 10-12 سپتامبر 2014. صص 615-620.
وانگ، اس. چیما، م. Lin, X. نظارت کارآمد معکوس k- نزدیکترین همسایگان در شبکه های فضایی. محاسبه کنید. J. 2015 ، 58 ، 40-56. [ Google Scholar ] [ CrossRef ]
آتیک، م. هایلو، ی. آیله، اس. چو، اچ. Chung, T. یک رویکرد خروج ایمن برای نظارت مداوم بر معکوس نزدیکترین همسایگان در شبکه های جاده ای. بین المللی عرب J. Inf. فنی 2015 ، 12 ، 540-549. [ Google Scholar ]
آتیک، م. چو، اچ. Chung, T. CORE: نظارت مداوم بر معکوس k نزدیکترین همسایه بر روی اجسام متحرک در شبکه های جاده ای. گل میخ. محاسبه کنید. هوشمند 2016 ، 2015 ، 109-124. [ Google Scholar ]
کورمن، تی. لیزرسون، سی. ریست، آر. Stein, C. Introduction to Algorithms , 3rd ed.; MIT Press and McGraw-Hill: Cambridge, MA, USA, 2009. [ Google Scholar ]
مجموعه داده های واقعی برای پایگاه های داده فضایی. در دسترس آنلاین: https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm (در تاریخ 2 آوریل 2016 قابل دسترسی است).
Brinkhoff, T. چارچوبی برای تولید اشیاء متحرک مبتنی بر شبکه. GeoInformatica 2002 ، 6 ، 153-180. [ Google Scholar ] [ CrossRef]

شکل 1. نمونه ای از شبکه راه.

شکل 2. جریان درخواست برای پردازش پرس و جوهای R k NN.

شکل 3. منطقه نفوذ o ₁ .

شکل 4. منطقه نفوذ o ₆ .

شکل 5. منطقه نفوذ o ₂ .

شکل 6. منطقه نفوذ o ₇ .

شکل 7. نقاط خروج ایمن q.

شکل 8. تعیین نقطه خروج ایمن

ω_{1}

شکل 9. تعیین نقطه خروج ایمن

ω_{2}

شکل 10. تعیین نقطه خروج ایمن

ω_{3}

شکل 11. تفاوت بین منطقه امن اصلی و منطقه امن فشرده

S R_{o r}

و منطقه امن فشرده

S R_{c o}

. ( الف ) منطقه امن اصلی

S R_{o r}

; ( ب ) منطقه امن فشرده

S R_{c o}

شکل 12. تفاوت بین منطقه امن اصلی

S R_{o r}

و منطقه امن فشرده

S R_{c o}

. ( الف ) مثال شبکه راه. ( ب ) منطقه بحرانی q.

شکل 13. به روز رسانی وزن دو لبه

n_{1} n_{2}

n_{2} n_{3}

جایی که

t_{i} < t_{j}

. ( الف ) منطقه بحرانی q در

t_{i}

; ( ب ) به روز رسانی به

n_{1} n_{2}

n_{2} n_{3}

در

t_{j}

شکل 14. مقایسه هزینه محاسباتی. ( الف ) اثر N _داده . ( ب ) اثر N _qry ; ( ج ) اثر R _obj ; ( د ) اثر V _obj ; ( ه ) اثر k.

شکل 15. مقایسه هزینه ارتباطات. ( الف ) اثر N _داده . ( ب ) اثر N _qry ; ( ج ) اثر R _obj ; ( د ) اثر V _obj ; ( ه ) اثر k.

شکل 16. مقایسه هزینه محاسباتی. ( الف ) اثر R _upd . ( ب ) اثر N _داده . ( ج ) اثر N _qry ; ( د ) اثر R _obj ; ( ه ) اثر V _obj ; ( و ) اثر k .

شکل 17. مقایسه هزینه ارتباطات. ( الف ) اثر R _upd . ( ب ) اثر N _داده . ( ج ) اثر N _qry ; ( د ) اثر R _obj ; ( ه ) اثر V _obj_j ; ( و ) اثر k.

جدول 1. خلاصه نمادهای استفاده شده در این مقاله.

جدول 2. خلاصه 2NN برای

o \in O

جدول 3. محاسبه ناحیه ایمن q .

جدول 4. محاسبه نقاط خروج ایمن برای o ₁ .

جدول 5. تنظیمات پارامترهای آزمایشی.

© 2016 توسط نویسندگان؛ دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC-BY) (http://creativecommons.org/licenses/by/4.0/) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

2. کارهای مرتبط

2.1. الگوریتم هایی برای پردازش پرس و جوی معکوس پیوسته نزدیکترین همسایه در فضای اقلیدسی

2.2. الگوریتم هایی برای پردازش پرس و جوی معکوس پیوسته نزدیکترین همسایه در شبکه های جاده ای

3. مقدمات

3.1. تعریف اصطلاحات و نمادها

3.2. شرح مشکل

4. الگوریتم خروج ایمن برای جابجایی پرس و جوهای R k NN و جابجایی اشیاء

4.1. منطقه امن برای جابجایی q

4.1.1. تعیین اشیاء مفید

4.1.2. منطقه تأثیر محاسباتی برای اشیاء مفید

4.1.3. محاسبه نقاط خروج ایمن

4.2. نظارت بر اشیاء داده

4.2.1. محاسبه نقاط خروج ایمن اشیاء مفید ( UO )

4.2.2. نظارت بر اشیاء هرس شده

4.3. برنامه های افزودنی

4.3.1. پرس و جوهای R k NN در شبکه های جاده ای جهت دار

4.3.2. پرس و جوهای R k NN در شبکه های جاده ای پویا

4.3.3. پرس و جوهای دو رنگی R k NN

4.4. تحلیل پیچیدگی های زمانی و مکانی

5. ارزیابی عملکرد

5.1. تنظیمات آزمایشی

5.2. نتایج تجربی برای شبکه های جاده ایستا

5.3. نتایج تجربی برای شبکه های جاده ای پویا

6. نتیجه گیری

منابع

قبلیتغییرات فضایی و زمانی رژیم بارش در چین از سال 1961 تا 2014 از شاخص استاندارد بارش

بعدییک روش پرس و جوی دامنه پیوسته مبتنی بر نمودار خطی برای جابجایی اشیاء در شبکه ها

بدون نظر

دیدگاهتان را بنویسید لغو پاسخ