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

خلاصه

رشد سریع خدمات مبتنی بر مکان، انگیزه توسعه پرس و جوهای دامنه پیوسته در شبکه ها شده است. الگوریتم های پرس و جوی موجود معمولاً یک درخت بسط را برای استفاده مجدد از نتایج پرس و جو قبلی برای دستیابی به کارایی بهتر اتخاذ می کنند. با این حال، هزینه های نگهداری بالای درخت گسترش سنتی منجر به کاهش شدید راندمان می شود. در این مقاله، ما یک الگوریتم پرس و جو مبتنی بر نمودار خطی محدوده پیوسته (LGCR) برای اشیاء متحرک در شبکه‌ها پیشنهاد می‌کنیم که با ساختار درخت بسط مبتنی بر نمودار جدید (GET) مشخص می‌شود که برای نظارت بر پرس‌و‌جوها به صورت افزایشی استفاده می‌شود. به طور خاص، GET بر اساس مدل نمودار خطی شبکه ها توسعه یافته است و به طور همزمان از پیش محاسبات آفلاین برای تطبیق بهتر الگوریتم پیشنهادی ما با اندازه های مختلف شبکه ها پشتیبانی می کند. برای بهبود عملکرد، ما یک سری از ساختارهای داده مرتبط، مانند لبه های قابل پل زدن و یال های فاصله ایجاد می کنیم. به همین ترتیب، ما چندین الگوریتم، از جمله راه‌اندازی اولیه، درج اشیاء، فیلتر و اصلاح و به‌روزرسانی مکان را توسعه می‌دهیم تا به صورت تدریجی پرس‌وجوهای محدوده پیوسته را ارزیابی کنیم. در نهایت، ما GET و الگوریتم های مرتبط را در پایگاه داده گراف بومی Neo4J پیاده سازی می کنیم. ما آزمایش‌هایی را با استفاده از شبکه‌های دنیای واقعی و اشیاء متحرک شبیه‌سازی شده انجام می‌دهیم و LGCR پیشنهادی را با الگوریتم کلاسیک موجود مقایسه می‌کنیم تا کارایی آن را تأیید کنیم و کارایی بیشتر آن را نشان دهیم. در نهایت، ما GET و الگوریتم های مرتبط را در پایگاه داده گراف بومی Neo4J پیاده سازی می کنیم. ما آزمایش‌هایی را با استفاده از شبکه‌های دنیای واقعی و اشیاء متحرک شبیه‌سازی شده انجام می‌دهیم و LGCR پیشنهادی را با الگوریتم کلاسیک موجود مقایسه می‌کنیم تا کارایی آن را تأیید کنیم و کارایی بیشتر آن را نشان دهیم. در نهایت، ما GET و الگوریتم های مرتبط را در پایگاه داده گراف بومی Neo4J پیاده سازی می کنیم. ما آزمایش‌هایی را با استفاده از شبکه‌های دنیای واقعی و اشیاء متحرک شبیه‌سازی شده انجام می‌دهیم و LGCR پیشنهادی را با الگوریتم کلاسیک موجود مقایسه می‌کنیم تا کارایی آن را تأیید کنیم و کارایی بیشتر آن را نشان دهیم.

کلید واژه ها:

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

1. معرفی

با پیشرفت شبکه‌های بی‌سیم و توسعه فناوری‌های موقعیت‌یابی، مانند GPS، RFID و WiFi، خدمات آنلاین مبتنی بر مکان و سیستم‌های نظارت هوشمند توجه روزافزونی را به خود جلب کرده‌اند [ 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ]. با انگیزه این امر، پرس و جوهای مکانی-زمانی برای اجسام متحرک به طور گسترده در زمینه های پایگاه داده های شی متحرک (MOD) و سیستم های اطلاعات جغرافیایی (GIS) مورد مطالعه قرار گرفته اند [ 8 ، 9 ، 10 ، 11]. بسیاری از انواع پرس و جوها و الگوریتم های پرس و جوی کارآمد متناظر پیشنهاد شده اند، مانند جستارهای محدوده [ 12 ، 13 ]، پرس و جوهای k- نزدیکترین همسایه [ 14 ، 15 ، 16 ]، پرس و جوهای نزدیکترین همسایه معکوس [ 17 ]، پرس و جوهای خط افق [ 18 ]، پرس و جوهای چگالی [ 19 ، 20 ] و پرس و جوهای نزدیکترین همسایه قابل مشاهده [ 21 ].

پرس و جوهای دامنه پرکاربرد و اساسی برای اشیاء در حال حرکت در فضای اقلیدسی یا شبکه ها مجموعه ای از اشیاء را در یک ناحیه معین در یک زمان پرس و جو معین برمی گرداند [ 22 , 23 , 24 , 25 , 26 , 27]. این مقاله به مشکل پردازش پرس و جوهای محدوده پیوسته برای اشیاء متحرک در شبکه می پردازد. یعنی اشیاء پرس و جو و اجسام متحرک هر دو در حرکت با سرعت بالا هستند و توسط شبکه های زیرین محدود می شوند. بر خلاف پرس و جوهای محدوده فوری که فقط یک بار ارزیابی می شوند، پرس و جوهای محدوده پیوسته نیاز به حفظ فعالیت در یک دوره زمانی و بازیابی مداوم نتایج پرس و جو دارند. بسیاری از برنامه های کاربردی دنیای واقعی به طور قابل ملاحظه ای به این نوع پرسش ها مانند نظارت بر ناوگان، نجات وسیله نقلیه و کنترل و مدیریت ترافیک بستگی دارند [ 28 ، 29]]. به عنوان مثال، به دلیل طولانی بودن مسیر تا ایستگاه راه آهن، ابتدا باید سوار اتوبوس و سپس تاکسی شویم. در این شرایط، ما باید به طور مداوم اعلان دریافت کنیم که چه زمانی و کجا می توانیم به تاکسی مجاور در فاصله 500 متری اتوبوس در حال حرکت ترانسفر دریافت کنیم.

ارزیابی مستمر پرس و جوهای محدوده به دلیل اطمینان از کامل بودن و صحت نتایج پرس و جو منجر به افزایش چالش ها برای کارایی و بار کاری سرور می شود [ 19 ، 30 ]. پاسخ دادن به پرس و جوهای محدوده پیوسته برای اجسام متحرک در شبکه ها در یک دوره زمانی آسان نیست. دو رویکرد برای پرس و جوهای دامنه پیوسته وجود دارد. رویکردهای افزایشی که با به حداکثر رساندن استفاده مجدد از نتایج قبلی مشخص می شوند، کارایی بهتری نسبت به سایر رویکردهایی دارند که پرس و جو دامنه پیوسته را به پرس و جوهای محدوده عکس فوری گسسته تقسیم می کنند [ 22 , 29 , 31]. با این حال، وابستگی شدیدی به طراحی ساختارهای داده درون حافظه برای حفظ نامزدهای قابل استفاده مجدد، مانند درخت توسعه و یک منطقه امن دارد [ 13 ، 25 ، 32 ]. با این حال، زمانی که مقیاس شبکه ها بزرگ است، اما توزیع اشیاء متحرک نسبتاً کم است، این ساختارهای داده به محاسبات مجدد آنلاین بیشتری نیاز دارند تا نامزدهای جستجوی به روز را حفظ کنند، زیرا اشیا اغلب وارد مناطق می شوند و از آن خارج می شوند. درخت گسترش [ 16 ، 17 ]. که این ساختارهای داده را باطل می کند و منجر به کاهش عملکرد می شود. بنابراین، ما نیاز به توسعه ساختارهای داده جدید برای حفظ نامزدهای پرس و جو داریم.

در این مقاله، ما یک الگوریتم جستجوی محدوده پیوسته مبتنی بر نمودار خط خطی جدید (LGCR) برای اجسام متحرک در شبکه‌ها ارائه می‌کنیم. ابتدا شبکه به صورت نمودار خطی مدل سازی می شود

G_{l g} = (V_{l g}, E_{l g})

. بخش ها به عنوان گره های گراف نشان داده می شوند

V_{l g}

، و لبه ها

E_{l g}

(یعنی روابط فضایی) دو بخش جاده مجاور را به هم متصل می کند. علاوه بر این، ما همچنین اشیاء متحرک را به عنوان یک ساختار گراف مدل می کنیم

G_{m o}

. بر اساس دو ساختار گراف نسبتا مستقل، یک لبه خاص

E_{m o \to l g}

از یک گره از نمودار شی

G_{m o}

به یک گره در نمودار خطی

G_{l g}

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

E_{m o \to l g}

علاوه بر این، ما یک ساختار درخت بسط مبتنی بر گراف (GET) ابتکاری را پیشنهاد می‌کنیم که اجسام متحرک نامزد را حفظ می‌کند. این یک گره پرس و جو منحصر به فرد ایجاد می کند

v_{q}

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

E_{q \to l g}

برای نشان دادن روابط نامزد بین یک گره پرس و جو

v_{q}

و گره گراف خطی

v_{l g}

. از این رو، با توجه به اینکه هزینه به روز رسانی GET به هزینه حذف یا ایجاد لبه ها بستگی دارد

E_{q \to l g}

، بار کاری سرور بیشتر کاهش می یابد. ما الگوریتم پرس و جو LGCR و ساختارهای داده مرتبط را در سیستم پایگاه داده گراف بومی Neo4J پیاده سازی می کنیم. ما ارزیابی تجربی را با استفاده از یک مجموعه داده شبیه سازی شده تولید شده توسط GT-MobiSIM انجام می دهیم تا کارایی و عملکرد را در مقایسه با یک الگوریتم پرس و جوی محدوده پیوسته کلاسیک نشان دهیم. سهم این مقاله در جنبه های زیر نهفته است:

ما یک درخت بسط مبتنی بر گراف جدید (GET) را بر اساس مدل نمودار خطی شبکه‌ها توسعه می‌دهیم. از پیش محاسبات آفلاین پشتیبانی می کند و می تواند به طور موثر زمان نگهداری آنلاین درخت گسترش سنتی را در پرس و جوهای مداوم کاهش دهد.
بر اساس GET، ما یک الگوریتم جستجوی محدوده پیوسته مبتنی بر نمودار خطی (LGCR) برای اشیاء متحرک در شبکه‌ها، از جمله الگوریتم‌هایی برای مقداردهی اولیه، درج، به‌روزرسانی مکان، فیلتر و اصلاح پیشنهاد می‌کنیم.
ما آزمایش‌هایی را برای ارزیابی LGCR پیشنهادی خود با استفاده از شبکه‌های دنیای واقعی و اشیاء متحرک شبیه‌سازی‌شده و مقایسه با الگوریتم‌های کلاسیک موجود برای تأیید اثربخشی آن انجام دادیم.

ادامه این مقاله به شرح زیر سازماندهی شده است. بخش 2 کارهای مرتبط را خلاصه می کند. بخش 3 ساختارهای داده مرتبط را برای پرس و جوهای محدوده پیوسته در شبکه ها ارائه می کند. بخش 4 الگوریتم پیشنهادی پرس و جو LGCR را توضیح می دهد. بخش 5 تنظیمات آزمایشی و نتایج را نشان می دهد. در نهایت، بخش 6 مقاله را به پایان می‌رساند و پیشرفت‌های بیشتر را پیشنهاد می‌کند.

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

یک رویکرد ساده برای پردازش پرس و جوهای محدوده پیوسته، تقسیم آنها به پرس و جوهای گسسته عکس فوری [ 8 ، 16 ، 33 ] است. وانگ و همکاران الگوریتم اجسام متحرک در شبکه های جاده ای (MOVNet) را برای پردازش پرس و جوهای پیوسته بر اساس پرس و جوهای محدوده عکس فوری برای اجسام متحرک در شبکه های جاده ای پیشنهاد کرد [ 34 ]. چندین ویژگی مهم و کوتاه‌ترین درخت مبتنی بر فاصله (SD-tree) را معرفی کرد که برای حفظ اتصال شبکه و اطلاعات فاصله شبکه برای کاهش اثرات به‌روزرسانی مکرر اشیاء در جست‌وجوهای دامنه پیوسته مورد استفاده قرار گرفت. کلاهدوزان و همکاران. یک الگوریتم کران بالایی برای بهبود عملکرد k پیوسته ایجاد کرد-نزدیکترین همسایه پرس و جو فقط با انجام پرس و جوهای عکس فوری در مکانی که آنها مورد نیاز هستند [ 16 ]. الگوریتم UNICONS یک مسیر پرس و جو را بر اساس اصل شباهت به چند مسیر فرعی تقسیم کرد و فواصل معتبر را محاسبه کرد. نتایج پرس و جو برای مسیرهای فرعی برای به دست آوردن نتایج نهایی ترکیب شدند [ 8]. مزیت این رویکرد این است که روش‌های موجود پرس‌و‌جوهای محدوده عکس فوری را می‌توان مستقیماً بدون تعدیل شدید در پرس‌وجوهای محدوده پیوسته اعمال کرد. با این حال، نقص این است که چگونه می توان نقاط تقسیم را به طور موثر پیدا کرد، که مکان و لحظه زمانی را مشخص می کند که نتایج جستجوهای محدوده را یکسان نگه می دارد. اگر یک الگوریتم پرس و جو به طور مکرر در هر لحظه ارزیابی شود، عملکرد به وضوح کاهش می یابد. با این حال، اگر یک الگوریتم پرس و جو در بازه های زمانی طولانی ارزیابی شود، نمی توان صحت پرس و جو را تضمین کرد.

یکی دیگر از استراتژی های پرکاربرد رویکردهای افزایشی اتخاذ شده در مقاله ما را به کار می گیرد. هزینه ارزیابی پرس و جوهای دامنه پیوسته را می توان با استفاده مجدد از نتایج تاریخچه حفظ شده توسط ساختارهای داده خاص در حافظه کاهش داد. به ویژه، هنگامی که به روز رسانی از اشیاء متحرک در این درخت می افتد، آنها باعث تغییر نتایج پرس و جو می شوند. در مقابل، به روز رسانی های نامربوط نادیده گرفته شدند [ 9 ، 25 ]. موراتیدیس و همکاران یک ساختار درختی گسترش را در الگوریتم نظارت افزایشی (IMA) و الگوریتم نظارت گروهی (GMA) پیشنهاد کرد [ 32 ]. الگوریتم ها با موقعیت شی پرس و جو در فاصله شبکه شروع می شوند

q . k N N_d i s t

، در اطراف بخش های جاده پیمایش کنید و یک درخت انبساط بسازید. سپس، IMA/GMA بر تغییرات شی پرس و جو و موقعیت شی متحرک نظارت می کند، این ساختار درختی بسط را هرس می کند و از نتایج کاندید برای تولید نتیجه پرس و جو از پرس و جوهای مداوم مجددا استفاده می کند. به طور مشابه، مفهوم مناطق امنی که نزدیکترین اجسام متحرک را به مرز پرس و جو محاسبه می کنند برای به حداقل رساندن هزینه ارتباطی و محاسباتی نظارت مستمر یک پرس و جو محدوده متحرک [35] پیشنهاد شد . مفهوم خروج ایمن به عنوان نمایش مختصر منطقه امن که مرز منطقه امن مبتنی بر شبکه را در بر می گیرد، پیشنهاد شد. علاوه بر این، الگوریتم های کارآمد برای محاسبه خروجی های ایمن توسعه داده شد [ 11 ، 36]. محدوده اقلیدسی محدودیت (RER) و گسترش شبکه محدوده (RNE) الگوریتم های پردازش پرس و جو معروف بر اساس این ایده هستند [ 37 ]. با این حال، شبکه های مقیاس بزرگ می توانند عملکرد پرس و جوهای پیوسته بر اساس درخت گسترش را به دلیل هزینه های بالای نگهداری کاهش دهند. از این رو، GET پیشنهادی در این مقاله ساختار درخت بسط اولیه را گسترش و بهینه می‌کند. به طور همزمان، از پیش محاسبات آفلاین پشتیبانی می کند تا الگوریتم پیشنهادی ما قابلیت اطمینان بالاتری برای اندازه های مختلف شبکه ها داشته باشد.

3. ساختارهای داده پیشنهادی

در این بخش، ساختارهای داده مرتبط را در الگوریتم پرس و جو LGCR، که شامل نمودار خط، نمودار فاصله و GET است، توضیح می دهیم.

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

G_{n e t}

شامل 12 بخش

(s_{1}, s_{2}, \dots, s_{12})

و 13 تقاطع

(j_{1}, j_{2}, \dots, j_{13})

. 9 شیء متحرک (نقاط سبز) در طول شبکه در حال حرکت هستند و به روز رسانی مکان را به سرور ارسال می کنند. شی پرس و جو q (نقاط زرد) به طور مداوم پرس و جوهای محدوده را در یک دوره زمانی صادر می کند.

(1) انواع اساسی:

ما مجموعه ای از انواع پایه را که برای تعاریف استفاده می شود در قسمت های زیر ارائه می کنیم. سه نوع اساسی برای تعاریف زیر پیشنهاد شده است:

i n t = Z

(1)

r e a l = R

(2)

b o o l = {t r u e, f a l s e}

(3)

دو نوع زمان برای نمایش زمان ارائه شده است:

i n s t a n t = R

(4)

p e r i o d = {(s ، e) | s, e \in i n s t a n t}

(5)

انواع هندسه از OGC استفاده می شود که یک سری مشخصات در مورد مدل شی هندسی منتشر می کند. LGCR پیشنهادی شامل سه نوع هندسه اساسی است:

p o i n t = {(l a t, l o n) | l a t, l o n \in r e a l}

(6)

l i n e = {< p تی 1 ، ص تی 2 ، . . . ، ص تی n > | n \in i n t, \forall i \in [1, n], p تی من \in p o i n t}

(7)

پی و یا _go n = { <ل1،ل2، . . . ،لn> | n ∈ i n t , ∀ i ∈ [ 1 , n ] ,لمن∈ l i n e }پ�ل����={<ل1،ل2،...،ل�>|�∈من�تی،∀من∈[1،�]،لمن∈لمن�ه}

(8)

(2) ساختار نمودار خطی:

شبکه

G_{n e t}

شامل مجموعه ای از بخش ها است

S e g

. اجازه دهید دامنه بخش ها به صورت زیر تعریف شود:

اسeg _= { ( s i d، ل ، گe o , s t a r t ) | s i d∈ i n t , l ∈ r e a l , ge o ∈ l i n e , s t a r t ∈ { s m a l l e r , l a r ge r } }اسه�={(سمند،ل،�ه�،ستیآ�تی)|سمند∈من�تی،ل∈�هآل،�ه�∈لمن�ه،ستیآ�تی∈{سمترآلله�،لآ��ه�}}

(9)

با یک شناسه $s i d$ ، طول l و پرچم $s t a r t$ که جهت یک خط هندسی را مشخص می کند $g e o$ .

نمودار خطی

G_{l g}

نمودار دیگری است که در آن هر رأس از

G_{l g}

نشان دهنده بخشی از

G_{n e t}

. تعریف رسمی به شرح زیر است:

جی l g = (V l g ، E l g)

(10)

جایی که:

Vl g= { < s eg1، s eg2، . . . ، s egn> | n ∈ i n t , ∀ i ∈ [ 1 , n ] , s egمن∈ اسeg _}�ل�={<سه�1،سه�2،...،سه��>|�∈من�تی،∀من∈[1،�]،سه�من∈اسه�}

(11)

و:

E l g = {< g r e ل 1 ، گ r e ل 2 ، . . . ، گ r e ل n > | n \in i n t, \forall i \in [1, n], g r e ل من \in آر g}

(12)

E_{g}

مجموعه ای از روابط فضایی بین دو بخش را نشان می دهد. ما از مدل نه تقاطع سازگار با OGC استفاده می کنیم، که یک تعریف جامع از روابط توپولوژیکی بین اشیاء فضایی در فضای دو بعدی ارائه می دهد [ 38 ، 39 ]. در این مقاله روابط توپولوژیکی

R_{g}

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

آرg= { ( s egمن، s egj, t yp e ) | s egمن، s egj∈Vl g, t yp e ∈ { m e e t , e qتو یک } } _��={(���من،سه��،تی�په)|سه�من،سه��∈�ل�،تی�په∈{مترههتی،ه�توآل}}

(13)

جایی که رابطه $m e e t$ نشان دهنده موردی است که در کدام بخش ها وجود دارد $s e g_{i}$ و $s e g_{j}$ در مجاورت یکدیگر هستند و $e q u a l$ حالتی را نشان می دهد که در آن دو بخش یکسان هستند.

شکل 2 نمونه ای از یک نمودار خطی را نشان می دهد که با شبکه در شکل 1 مطابقت دارد . بخش

s_{1}

به عنوان یک گره گراف مدل شده است. رابطه اتصال بین بخش ها

s_{1}

s_{2}

به عنوان روابط فضایی ساخته شده است

m e e t

(3) ساختار گراف شی:

یک جسم متحرک به صورت زیر تعریف می شود:

م o = {(m i d, n a m e, p a r a m) | m i d \in i n t ، n a m e \in s t r i n g}

(14)

جایی که $m i d$ و $n a m e$ نشان دهنده شناسه و نام شیء و $p a r a m$ مجموعه ای از ویژگی های دیگر شی را نشان می دهد.

ساختار گراف شی اشیاء متحرک و روابط اجتماعی بین آنها را مدل می کند. به صورت زیر تعریف می شود:

جی m o = (V m o ، E m o)

(15)

جایی که $V_{m o}$ به اجسام متحرک اشاره می کند و به صورت زیر تعریف می شود:

V m o = {< m o 1 ، م o 2 ، . . . ، م o n > | n \in i n t, \forall i \in [1, n], m o من \in م o}

(16)

و $E_{m o}$ روابط اجتماعی بین دو جسم متحرک را نشان می دهد و به صورت زیر تعریف می شود:

Em o= { < s r eل1s r e _ل2، . . . s r e _لn> | n ∈ i n t , ∀ i ∈ [ 1 , n ] , s r eلمن∈آرm o}�متر�={<س�هل1،س�هل2،...،س�هل�>|�∈من�تی،∀من∈[1،�]،س�هلمن∈آرمتر�}

(17)

جایی که:

آر m o = {(m o من ، م o j, t y p e) | متر o من ، م o j \in V m o, t y p e \in s t r i n g}

(18)

و $t y p e$ نشان دهنده روابط اجتماعی بین اجسام متحرک است.

(4) مکان شبکه

موقعیت شبکه یک جسم متحرک

g l o c

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

g l o c = {(s i d ، د) | s i d \in int ، د \in r e a l, 0 \leq d \leq l}

(19)

جایی که $s i d$ یک شناسه قطعه و d است یک عدد واقعی را نشان می دهد که موقعیتی را در آن بخش ارائه می دهد.

بردار متحرک یک جسم

m v e c t o r

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

m v e c t o r = {(m i d ، گ l o c, v, t) | m i d \in i n t, v \in r e a l, t \in i n s t a n t}

(20)

جایی که $m i d$ شناسه یک جسم متحرک است، $g l o c$ نشان دهنده موقعیت شبکه اشیاء در یک قطعه خاص و v نشان دهنده سرعت لحظه ای در زمان t است .

(5) لبه های قابل پل زدن:

E_{m o \to l g}

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

E m o \to l g = {< m l r e ل 1 ، m l r e ل 2 ، . . . ، m l r e ل n > ∣ ∣ n \in i n t, \forall i \in [1, n], m l r e ل من \in آر l g m o}

(21)

جایی که:

آر l g m o = {(m o من ، s e g j, t y p e) | متر o من \in V m o ، s e g j \in V l g, t y p e \in s t r i n g}

(22)

شکل 3 نمونه ای از لبه های قابل پل زدن را نشان می دهد، جایی که یک شی پرس و جو q از بخش حرکت می کند.

s_{1}

بخش بندی کردن

s_{2}

همانطور که در شکل 3 الف نشان داده شده است. لبه (خط فلش آبی) از گره

s_{1}

به گره q حذف خواهد شد و یک لبه جدید (خط فلش قرمز) از گره

s_{5}

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

(6) لبه های فاصله

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

E_{l g \to l g}

برای نشان دادن فاصله شبکه سپس، می‌توانیم از عملیات پیمایش نمودار برای بازیابی مقدار فاصله با هزینه پرس و جو کمتر استفاده کنیم.

E_{l g \to l g}

مجموعه ای از یال ها را بین هر دو گره گراف خطی نشان می دهد. ویژگی های آن مقدار فاصله شبکه بین دو بخش را ذخیره می کند و به صورت زیر تعریف می شود:

E l g \to l g = {< l l r e ل 1 ، l l r e ل 2 ، . . . ، l l r e ل n > ∣ ∣ n \in i n t, \forall i \in [1, n], l l r e ل من \in آر l g l g}

(23)

جایی که:

آر l g l g = {< s e g من ، s e g j ، د e d g ه > | s e g من ، s e g j \in V l g ، د e d g ه \in r e a l}

(24)

مفهوم فاصله لبه را معرفی می کنیم

d_{e d g e}

، که به عنوان فاصله بین دو لبه (یعنی بخش های جاده) با توجه به انواع گره های بخش ها تعریف می شود [ 40 ]. فاصله لبه را می توان به چهار نوع طبقه بندی کرد:

S S, S E, E S, E E

، جایی که

E S

فاصله از گره انتهایی E را مشخص می کند

e d g e_{i}

به گره شروع S از

e d g e_{j}

. انواع فاصله

S E, E S

E E

به طور مشابه تعریف می شوند.

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

s_{2}

d_{e s} (s_{2}, s_{3})

به عنوان فاصله از

j_{2 - e}

به

j_{3 - s}

، و

d_{e s} (s_{1}, s_{2})

به عنوان فاصله از

j_{1 - e}

به

j_{2 - s}

(7) درخت بسط مبتنی بر نمودار:

GET شامل مجموعه ای از بخش ها است و به صورت زیر تعریف می شود:

جی ای تی = {(s e g q ، (s e g 1 ، . . . ، s e g n)) | n \in i n t, \forall i \in [1, n], s e g q ، s e g من \in V l g} ، \forall i \in {1, 2, . . ., n}, د e d g ه (s e g q ، s e g من) < r g

(25)

جایی که $r g$ پارامترهای فاصله داده شده پرس و جوهای دامنه پیوسته را نشان می دهد و $s e g_{q}$ نشان دهنده بخشی است که شی پرس و جو روی آن حرکت می کند. واضح است، بخش $s e g_{q}$ و پارامترهای ورودی $r g$ برای محاسبه GET حیاتی هستند. از این رو، برای هر بخش در یک شبکه، می‌توانیم GET آفلاین را برای بهبود کارایی الگوریتم پرس و جو LGCR از قبل محاسبه کنیم.

شکل 5 نمونه ای از GET را نشان می دهد. هنگامی که شی پرس و جو q از بخش خارج می شود

s_{1}

، GET باید دوباره محاسبه شود تا نتایج نامزدها به روز بماند. با توجه به اینکه GET قبلاً محاسبه شده است، این امر زمان مورد نیاز برای پردازش الگوریتم پرس و جو LGCR را به میزان قابل توجهی کاهش می دهد.

4. الگوریتم پرس و جو LGCR

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

4.1. الگوریتم ها

(1) راه اندازی:

اولیه سازی الگوریتم پرس و جو LGCR ساختارهای نمودار خطی را می سازد و فرآیند ایجاد لبه های فاصله را طبق الگوریتم 1 به پایان می رساند. پارامتر ورودی الگوریتم شبکه است. برای بهبود کارایی الگوریتم پرس و جو LGCR، یک درخت R ایجاد می کنیم

I_{r t r e e}

برای نمایه سازی بخش ها، همانطور که در خط 2 نشان داده شده است، که تمام بخش ها را طی می کند و گره های نمودار مربوطه را در نمودار خطی ایجاد می کند.

G_{l g}

همانطور که در خطوط 4-5 نشان داده شده است. سپس، الگوریتم گره‌های بخش مجاور را جستجو می‌کند و لبه‌های پیوندی را برای حفظ روابط توپولوژیکی کامل بین بخش‌ها ایجاد می‌کند (خط 8-10). به طور همزمان، یک تقریب حداقل مستطیل مرزی (MBR) از بخش ها ایجاد می کند و گره برگ را به هم مرتبط می کند.

I_{r t r e e}

به گره های بخش مربوطه (خطوط 6-7). سپس، الگوریتم تمام بخش‌ها را طی می‌کند تا فاصله لبه شبکه بین هر دو بخش را محاسبه کند و یال‌های فاصله را می‌سازد (خطوط 13-20).

در نهایت، الگوریتم گره قطعه را در نمودار خطی طی می کند و گره های بخش جاده مجاور را بازیابی می کند (خطوط 22-23). سپس مقدار فاصله لبه شبکه را بدست می آورد

d_{e d g e}

. اگر فاصله لبه

d_{e d g e}

کمتر از پارامتر محدوده پرس و جو پیوسته ورودی است

r g

، یک یال ایجاد می شود و در ساختار نمودار خطی درج می شود (خطوط 24-27). توجه داشته باشید که مقداردهی اولیه فقط یک بار برای الگوریتم پرس و جو LGCR قابل اجرا است.

الگوریتم 1: الگوریتم اولیه سازی.

(2) درج اشیاء متحرک و اشیاء پرس و جو:

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

E_{m o \to l g}

(خطوط 3-7).

الگوریتم 2: درج اشیاء متحرک و اشیاء پرس و جو.

(3) مرحله فیلتر و اصلاح برای الگوریتم های پرس و جو LGCR:

الگوریتم 3 مرحله فیلتر و اصلاح الگوریتم پرس و جو LGCR را نشان می دهد. مرحله فیلتر از GET عبور می کند تا همه اشیاء متحرک نامزد را با استفاده از لبه های قابل پل پیدا کند

E_{m o \to l g}

همانطور که در خط 1 نشان داده شده است. مرحله پالایش به صورت دوره ای انجام می شود. الگوریتم نتایج کاندید را پیمایش می‌کند و تعیین می‌کند که آیا زمان فعلی شی متحرک و فاصله شبکه تا شی پرس و جو شرایط پرس و جوی محدوده پیوسته داده شده را برآورده می‌کند (خطوط 3-8). اگر چرخه عمر الگوریتم پرس و جو LGCR شامل زمان جاری شیء باشد و مکان شیء محدوده پرس و جو را قطع کند، آنگاه شی کاندید به مجموعه نتایج پرس و جو افزایشی منتقل می شود (خط 6).

الگوریتم 3: مرحله فیلتر و پالایش.

(4) به روز رسانی مکان اشیاء متحرک:

سه نوع استراتژی به‌روزرسانی مکان برای اشیاء متحرک وجود دارد: به‌روزرسانی موقعیت مکانی تحریک‌شده با آستانه سرعت (STTLU)، به‌روزرسانی موقعیت مکانی راه‌اندازی شده با آستانه فاصله (DTTLU) و به‌روزرسانی مکان با شناسایی شناسایی (IDTLU) [41 ] . با توجه به اینکه به روز رسانی مکان با تبدیل شی متحرک به یک بخش جاده جدید آغاز می شود، استراتژی IDTLU برای الگوریتم پرس و جو LGCR مناسب تر است. الگوریتم 4 آن به روز رسانی های مکان را مدیریت می کند. ابتدا شی را تعیین می کند

n o d e_{m o}

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

m i d

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

n o d e_{l g}^{o l d}

با استفاده از لبه های قابل پل زدن به راحتی قابل بازیابی است

E_{m o \to l g}

(خطوط 1-2). سپس، خطوط 3-4 شی را به روز می کنند

n o d e_{m o}

ارزش با مکان و زمان جدید از به‌روزرسانی‌های مکان. علاوه بر این، یک لبه قابل پل زدن جدید به یک بخش جدید ایجاد می کند. در مرحله بعد، هنگامی که شی متعلق به شی پرس و جو است، GET باید به روز شود، همانطور که در خط 7 نشان داده شده است. در غیر این صورت، مرحله فیلتر و پالایش باید انجام شود (8-12).

الگوریتم 4: به روز رسانی مکان یک شی متحرک یا شی پرس و جو.

4.2. تجزیه و تحلیل پیچیدگی الگوریتم

فرض کنید که لبه های E در شبکه ها، M اشیاء متحرک و اشیاء پرس و جو Q وجود دارد . پیچیدگی زمانی الگوریتم پرس و جو LGCR را می توان به صورت زیر تعریف کرد:

تی = تی f من هستم___+ تی u p + تی r e f

(26)

جایی که $T_{f i l t e r}$ نشان دهنده زمان CPU مورد نیاز برای محاسبه نامزدهای پرس و جو به دست آمده توسط GET است، $T_{u p}$ نشان دهنده زمان مورد نیاز CPU برای به روز رسانی مکان و $T_{r e f}$ نشان دهنده زمان مورد نیاز CPU برای مرحله پالایش است. زمان مورد نیاز برای بازیابی نامزدهای درخواست شامل زمان پیمایش GET است. سپس، پیچیدگی $T_{f i l t e r}$ از این الگوریتم به صورت تعریف شده است $O (Q n)$ . به روز رسانی مکان اشیاء یک عملیات لبه و پیچیدگی زمانی را آغاز می کند $T_{u p}$ است $O (M n)$ . زمان مورد نیاز برای محاسبه فاصله شبکه به زمان پیمایش نمودار به دلیل لبه های فاصله بستگی دارد. سپس، پیچیدگی زمانی $T_{r e f}$ بستگی به اندازه نتایج کاندید دارد و به این صورت تعریف می شود $O (\frac{Q}{M} n)$ .

5. آزمایشات

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

ما آزمایش‌هایی را روی یک رایانه شخصی استاندارد با پردازنده Intel i7-4790، رم 8G و یک هارد دیسک مکانیکی 1 ترابایتی انجام دادیم. ما از ژنراتور GT-MobiSIM [ 42 ] که توسط یک فایل پیکربندی XML هدایت می‌شود برای شبیه‌سازی اشیاء متحرک استفاده کردیم، و اشیاء پرس‌وجو به‌طور تصادفی انتخاب شدند تا درخواست‌های پرس و جوی محدوده پیوسته را صادر کنند. به منظور آزمایش عملکرد و کارایی LGCR پیشنهادی ما، دو آزمایش را آماده کردیم. آزمایش اول 5000 شی متحرک را در یک شبکه شبیه سازی کرد و 500 شی پرس و جو را به طور تصادفی انتخاب کرد تا درخواست های پرس و جوی دامنه پیوسته با پارامترهای محدوده مختلف را صادر کند، همانطور که در شکل 7 الف نشان داده شده است. آزمایش دوم 10000 شی متحرک را شبیه سازی کرد و 1000 شی پرس و جو را به طور تصادفی انتخاب کرد، همانطور که در نشان داده شده است. شکل 7 نشان داده شده است.ب همانطور که در شکل نشان داده شده است، نقاط قرمز اشیاء متحرک و نقاط آبی اشیاء پرس و جو بودند. ورودی از مجموعه داده های شبکه واقعی از پکن، با 26220 بخش و 18856 تقاطع استفاده می کند. ژنراتور شامل مدل‌های مختلف تحرک در شبکه‌ها می‌شد، مانند ایستگاه بین راه تصادفی و سفر تصادفی. علاوه بر این، سه راه برای نمایش ردیابی های زمان پیوسته وجود داشت، از جمله تابع گام-مکان، تابع تنظیم سرعت و تابع-گام شتاب. همچنین شامل توزیع پارامترهای مختلف برای اجسام متحرک، مانند توزیع گاوسی و توزیع نرمال است. در آزمایش‌ها، توزیع پارامتر را روی توزیع گاوسی تنظیم کردیم و هر جسم متحرک کوتاه‌ترین مسیر را به مقصد نهایی که از یک مدل تحرک نقطه‌ای تصادفی از پیش تعریف‌شده تولید شده بود دنبال کرد. ساختارهای داده مرتبط با استفاده از پایگاه داده گراف بومی Neo4J 1.9.7 پیاده سازی شدند. الگوریتم پرس و جو پیشنهادی LGCR با استفاده از جاوا به عنوان زبان برنامه نویسی اصلی و Eclipse به عنوان محیط توسعه پیاده سازی شد.

برای مقایسه، ما از الگوریتم کلاسیک پیشنهاد شده توسط Stojanovic و همکاران، معروف به StojanovicCR [ 13 ] برای پرس و جوی محدوده پیوسته بر روی اشیاء متحرک در شبکه هایی با کارایی و اثربخشی بالا استفاده کردیم، که خدمات و برنامه های کاربردی مبتنی بر مکان را در دنیای واقعی راضی کرد. این الگوریتم مجموعه ای از ساختارهای داده در حافظه، بخش R*-tree (SR*-tree)، جدول پرس و جو پیوسته (CQT)، جدول اتصال شبکه (NCT) و جدول شی موبایل (MOT) را برای پشتیبانی از ارزیابی پرس و جوی محدوده پیوسته به طور خاص، SR*-tree R*-tree را برای ذخیره اطلاعات MBR بخش های جاده گسترش داد. ورودی گره برگ SR*-tree به صورت نمایش داده شد

(s e g i d, m b r, o l i s t, q l i s t)

، جایی که

m b r

حداقل مستطیل مرزی بود،

o l i s t

q l i s t

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

s e g i d

. جدول NCT اطلاعات اتصال بخش های جاده را ذخیره می کند. یک ورودی جدول NCT به عنوان نشان داده شد

(s e g i d, r t E n t r y, s e g L e n g t h, s t a r t C o n, e n d C o n)

، جایی که

s e g i d

شناسه بخش جاده بود،

r t E n t r y

نشانگر را به SR*-tree نشان داد،

s e g L e n g t h

طول بخش جاده و عناصر را نشان می دهد

s t a r t C o n

e n d C o n

لیستی از بخش های جاده مجاور را نشان می دهد. جدول CQT اطلاعات مربوط به پرس و جوهای دامنه پیوسته را ذخیره می کرد. یک ورودی CQT به عنوان نشان داده شد

(q i d, o i d, r a n g e, v a l i d P e r i o d, a n s w e r S e t)

، جایی که

q i d

شناسه پرس و جوهای دامنه پیوسته بود،

o i d

نشان دهنده شی پرس و جو است،

r a n g e

پارامترهای محدوده را تعریف کرد،

a n s w e r S e t

نشان دهنده پاسخ پرس و جو اولیه و

v a l i d P e r i o d

دوره معتبر پرس و جو را نشان می دهد. جدول MOT اطلاعات اجسام متحرک را ذخیره می کرد. یک ورودی MOT به عنوان نشان داده شد

(m o i d, l o c, t i m e, s p e e d, q u e r y S e t)

، جایی که

m o i d

شناسه اجسام متحرک بود،

l o c

مکان فعلی در آن زمان بود

t i m e

s p e e d

سرعت جاری را نشان می دهد. این

q u e r y S e t

لیستی از پرس و جوهایی را که این شی در آنها شرکت می کند نشان می دهد. StojanovicCR ابتکاری یک مرحله پیش پالایش را برای اصلاح بیشتر اشیاء متحرک توسط مرحله فیلتر در یک استراتژی پردازش پرس و جو سنتی معرفی کرد. ابتدا، با توجه به شرایط پرس و جو، مرحله فیلتر، اشیاء متحرک کاندید را با استفاده از شاخص SR*-tree انتخاب کرد. مرحله پیش پالایش، پالایش بیشتر اجسام متحرک به دست آمده توسط مرحله فیلتر بود. مرحله پالایش به صورت دوره ای با پردازش اشیاء نامزد تولید شده توسط مرحله پیش پالایش انجام شد و پاسخ پرس و جو را ایجاد کرد.

5.2. نتایج تجربی

مقداردهی اولیه LGCR در آزمایش حدود 983 ثانیه طول کشید. این عمدتا شامل سه بخش زیر است: وارد کردن شبکه ها، ساخت ساختارهای داده پیشنهادی و ساخت ساختار GET. GET کلید بهبود عملکرد الگوریتم پرس و جو LGCR به روشی افزایشی است. با توجه به محدوده پرس و جو، پرس و جوها به گروه های مختلفی طبقه بندی می شوند. میانگین زمان محاسبه کاندیدای پرس و جو را برای هر گروه با همان محدوده پرس و جو محاسبه می کنیم. شکل 8زمان صرف شده برای بازیابی اشیاء کاندید با استفاده از GET را نشان می دهد. نتایج نشان می‌دهد که بازیابی اشیاء کاندید به زمان CPU بیشتری با افزایش دامنه پرس و جو نیاز دارد. با توجه به اینکه عملیات اصلی پیمایش گراف در GET است، محدوده پرس و جو بزرگ به عملیات پیمایش گراف بیشتری نیاز دارد که منجر به صرف زمان بیشتر می شود.

شکل 9 نشان می دهد که میانگین تعداد اشیاء متحرک در نتایج پرس و جو (نوار نارنجی) بسیار نزدیک به میانگین تعداد اجسام متحرک در نتایج کاندید (نوار آبی) است. میانگین نسبت استفاده از اشیاء کاندید بازیابی شده توسط GET به 81.2 درصد افزایش یافته است، یعنی GET به طور موثر شی متحرک کاندید قابل استفاده مجدد را برای جستجوهای دامنه پیوسته افزایشی برای الگوریتم پرس و جو LGCR حفظ می کند. واحد اصلی GET یک بخش جاده است. از این رو، طول یک بخش جاده با تعداد نامزدها مرتبط است. یک بخش طولانی تر جاده منجر به کاهش نسبت بین نتایج پرس و جو و نتایج نامزد شد. میانگین طول بخش‌های جاده در پکن در آزمایش‌ها 202.25 متر بود که فاصله نسبتاً کوتاهی است. از این رو، GET مجموعه های نامزد دقیق تری را حفظ می کند.

شکل 10 a میانگین زمان CPU برای هر پرس و جو را در آزمایش با 5000 شی متحرک و 500 شی پرس و جو نشان می دهد.شکل 10b نتایج تجربی را با 10000 شی متحرک و 1000 شی پرس و جو نشان می دهد. نتایج تجربی نشان می دهد که الگوریتم پرس و جو LGCR عملکرد و پایداری بهتری را برای ارزیابی پرس و جوهای پیوسته نسبت به StojanovicCR ارائه می دهد. میانگین زمان CPU به ازای هر پرس و جو برای هر دو رویکرد به طور کلی با افزایش دامنه پرس و جو افزایش می یابد. StojanovicCR به زمان بیشتری برای به روز رسانی ساختارهای داده درون حافظه مانند SR*-tree، MOT و CQT نیاز داشت. الگوریتم پرس و جو LGCR همچنین زمان اجرای طولانی تری را برای کاندیدهای پرس و جو برای پرس و جوهای محدوده پیوسته ایجاد می کند. با این حال، عملگرهای اصلی نمودار، مانند ایجاد یا حذف یال ها و پیمایش نمودار، زمان کمتری را صرف می کنند. از این رو، الگوریتم پرس و جو LGCR پایدارتر و کارآمدتر بود. علاوه بر این،

5.3. بحث

الگوریتم پرس و جو پیشنهادی LGCR برای پرس و جوهای محدوده پیوسته بر روی اشیاء متحرک در شبکه کارآمد بود. با این حال، هنوز محدودیت هایی وجود دارد که ارزش توجه دارند.

(1) برای الگوریتم پرس و جو LGCR، ساختارهای داده خاص، از جمله لبه های قابل پل زدن، لبه های فاصله و مراحل پیش محاسباتی GET و آفلاین، به طور قابل توجهی کارایی را بهبود بخشید. با این حال، مقیاس بزرگ شبکه، این مراحل پیش پردازش را بسیار وقت گیر کرد و به فضای ذخیره سازی عظیمی نیاز داشت. علاوه بر این، LGCR پیشنهادی ما می‌تواند به راحتی برای پشتیبانی از جستارهای جغرافیایی اجتماعی گسترش یابد، زیرا ساختار ObjectGraph توانایی مدل‌سازی روابط اجتماعی بین اشیاء متحرک، مانند همکاران، دوستی‌ها، پیروان، گروه‌های علاقه‌مند یا روابط طرفداران را دارد.

(2) به عنوان وظیفه کلیدی الگوریتم پرس و جو LGCR، واحد اصلی GET شامل مجموعه ای از بخش ها بود. با این حال، آن بخش ها هیچ معنای فیزیکی آشکاری نداشتند. آنها نمی توانند به خوبی با نهادهای مفهومی در محیط های شبکه جاده ای پیچیده در دنیای واقعی سازگار شوند [ 2 ، 15 ]. مفهوم مسیرهای مربوط به بزرگراه ها یا بزرگراه ها در دنیای واقعی را می توان برای مدل سازی شبکه های جاده ای معرفی کرد. از این رو، یک GET ترکیبی که شامل بخش‌های جاده و مسیرها می‌شود، می‌تواند انعطاف‌پذیری الگوریتم پرس و جو LGCR را بیشتر بهبود بخشد.

(3) ما فرض کردیم که ساختار شبکه کمی تغییر کرده است و به روز رسانی ها عمدتاً به روز رسانی مکان اشیاء متحرک را در نظر می گیرند. با این حال، در یک سناریوی واقعی، وزن یک بخش همیشه با اطلاعات ترافیک تغییر می‌کند و بخش‌های جاده‌ای جدید ممکن است درج شوند. این تأثیرگذارها بر نتایج پرس و جو کوئری های دامنه پیوسته تأثیر می گذارند. از این رو، انواع بیشتری از به روز رسانی ها باید در نظر گرفته شود تا الگوریتم پرس و جو LGCR گسترده تر شود.

6. نتیجه گیری

با انگیزه نیاز اساسی به خدمات مبتنی بر مکان و برنامه های کاربردی برای پرس و جوهای مکانی-زمانی، ما یک الگوریتم جدید پرس و جو LGCR را ارائه کردیم که به ساختار نمودار خطی و ساختار GET وابسته بود که می توانست مشکل پردازش کارآمد پرس و جوهای دامنه پیوسته را در محدوده وسیع حل کند. اجسام متحرک در شبکه ها این الگوریتم را می توان مستقیماً برای سرویس ها و برنامه های کاربردی مبتنی بر مکان در دنیای واقعی اعمال کرد.

کار آینده نیاز به پیاده سازی پردازش موازی پرس و جوهای دامنه پیوسته بر اساس الگوریتم پرس و جو LGCR برای بهبود بیشتر عملکرد دارد. مزایای ساختار داده پیشنهادی شامل حالت نمودار خطی و ساختار GET است. الگوریتم پرس و جوی پیشنهادی LGCR به راحتی در محیط های محاسباتی توزیع شده با کمک یک چارچوب پردازش تغییر گراف در مقیاس بزرگ، مانند Pregel و موازی همزمان انبوه (BSP) قابل استقرار است.

منابع

ولفسون، او. خو، بی. چمبرلین، اس. جیانگ، ال. پایگاه داده های اشیاء متحرک: مسائل و راه حل ها. در مجموعه مقالات دهمین کنفرانس بین المللی مدیریت پایگاه داده های علمی و آماری، واشنگتن دی سی، ایالات متحده آمریکا، 1 تا 3 ژوئیه 1998.
گوتینگ، RH; Ding, Z. مدلسازی و پرس و جو از اجسام متحرک در شبکه ها. بین المللی J. پایگاه داده های بسیار بزرگ 2006 ، 15 ، 165-190. [ Google Scholar ] [ CrossRef ]
سیونزو، دی. بوونانو، آ. D’Urso، M. Palmieri، FA طبقه بندی توزیع شده اهداف متحرک چندگانه با شبکه های حسگر بی سیم باینری. در مجموعه مقالات سال 2011 مجموعه مقالات چهاردهمین کنفرانس بین المللی در همجوشی اطلاعات (FUSION)، شیکاگو، IL، ایالات متحده آمریکا، 5 تا 8 ژوئیه 2011.
بوونانو، آ. D’Urso، M. پریسکو، جی. فلاکو، م. ملیادو، ای. متی، م. پالمیری، اف. شبکه‌های حسگر Ciuonzo، D. Mobil مبتنی بر پلت‌فرم‌های مستقل برای امنیت داخلی. در مجموعه مقالات کارگاه Tyrrhenian 2012 در مورد پیشرفت در رادار و سنجش از دور (TyWRRS)، ناپل، ایتالیا، 12-14 سپتامبر 2012.
پدر و مادر، سی. اسپاکاپیترا، اس. رنسو، سی. آندرینکو، جی. آندرینکو، ن. بوگورنی، وی. دامیانی، ام.ال. گکولالاس-دیوانیس، ع. مکدو، جی. پلکیس، N. مدلسازی و تحلیل مسیرهای معنایی. کامپیوتر ACM. Surv. 2013 ، 45 ، 1-42. [ Google Scholar ] [ CrossRef ]
شکر، س. جیانگ، ز. علی، RY; افتلی اوغلو، ای. تانگ، ایکس. گونتوری، وی. ژو، X. داده کاوی فضایی-زمانی: یک دیدگاه محاسباتی. ISPRS Int. J. Geo-Inf. 2015 ، 4 ، 2306-2338. [ Google Scholar ] [ CrossRef ]
ژنگ، ی. داده کاوی مسیر: یک مرور کلی. ACM Trans. هوشمند سیستم تکنولوژی 2015 ، 6 ، 1-29. [ Google Scholar ] [ CrossRef ]
چو، اچ.-جی. ریو، ک. چانگ، T.-S. یک الگوریتم کارآمد برای محاسبه نقاط خروج ایمن پرس و جوهای محدوده متحرک در شبکه های جاده هدایت شده. Inf. سیستم 2014 ، 41 ، 1-19. [ Google Scholar ] [ CrossRef ]
ژوان، ک. ژائو، جی. تانیار، د. رهایو، دبلیو. صفر، م. Srinivasan، B. پردازش پرس و جو مبتنی بر دامنه و دامنه پیوسته ورونوی در پایگاه داده های تلفن همراه. جی. کامپیوتر. سیستم علمی 2011 ، 77 ، 637-651. [ Google Scholar ] [ CrossRef ]
زو، تی. وانگ، سی. Lv، W. Huang, J. نظارت بر برد مداوم اجسام متحرک در شبکه های جاده ای. در مجموعه مقالات دهمین کنفرانس بین المللی 2010 در مورد طراحی و کاربردهای سیستم های هوشمند (ISDA)، قاهره، مصر، 29 نوامبر تا 1 دسامبر 2010.
یونگ، دی. Yiu، ML; Lo, E. یک رویکرد خروج ایمن برای جستجوهای محدوده متحرک مبتنی بر شبکه کارآمد. دانستن داده ها مهندس 2012 ، 72 ، 126-147. [ Google Scholar ] [ CrossRef ]
ژنگ، ک. ترایچفسکی، جی. ژو، ایکس. Scheuermann, P. پرس و جوهای محدوده احتمالی برای مسیرهای نامشخص در شبکه های جاده ای. در مجموعه مقالات چهاردهمین کنفرانس بین المللی گسترش فناوری پایگاه داده، اوپسالا، سوئد، 21 تا 24 مارس 2011.
استویانوویچ، دی. پاپادوپولوس، AN; پردیک، بی. جورجویچ-کاجان، اس. نانووپولوس، الف. نظارت برد مداوم اشیاء متحرک در شبکه های جاده ای. دانستن داده ها مهندس 2008 ، 64 ، 77-100. [ Google Scholar ] [ CrossRef ]
هوانگ، YK; چن، ZW; لی، سی. جستار پیوسته k-نزدیکترین همسایه بر روی اجسام متحرک در شبکه های جاده ای. Adv. مدیریت وب داده ها 2009 ، 5446 ، 27-38. [ Google Scholar ]
جنسن، CS; کولاور، ج. پدرسن، سل؛ Timko، I. پرسش های نزدیکترین همسایه در شبکه های جاده ای. در مجموعه مقالات سمپوزیوم بین المللی ACM در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، نیواورلئان، لس آنجلس، ایالات متحده آمریکا، 3-8 نوامبر 2003.
کلاهدوزان، محمدرضا; شهابی، ج. جستارهای پیوسته k-نزدیکترین همسایه در پایگاه داده شبکه های فضایی. در مجموعه مقالات STDBM’04، تورنتو، ON، کانادا، 30 اوت 2004.
صفر، م. ابراهیمی، د. پردازش پرس و جوی معکوس نزدیکترین همسایه مبتنی بر Taniar، D. Voronoi در شبکه های فضایی. سیستم چندرسانه ای 2009 ، 15 ، 295-308. [ Google Scholar ] [ CrossRef ]
صفر، م. الامین، د. تانیار، دی. پرسش‌های خط افق بهینه شده در شبکه‌های جاده‌ای با استفاده از نزدیک‌ترین همسایگان. پارس محاسبات همه جا حاضر. 2011 ، 15 ، 845-856. [ Google Scholar ] [ CrossRef ]
هائو، ایکس. منگ، ایکس. Xu, J. جستجوهای چگالی پیوسته برای اجسام متحرک. در مجموعه مقالات کارگاه بین المللی ACM در مورد مهندسی داده برای دسترسی بی سیم و موبایل، ونکوور، BC، کانادا، 13 ژوئن 2008.
جنسن، CS; لین، دی. Ooi، BC; ژانگ، آر. پرس و جوهای چگالی مؤثر بر روی اجسام متحرک پیوسته. در مجموعه مقالات کنفرانس بین المللی مهندسی داده، آتلانتا، GA، ایالات متحده آمریکا، 3-8 آوریل 2006.
گائو، ی. ژنگ، بی. چن، جی. لی، کیو. Guo, X. پردازش جستجوی نزدیکترین همسایه قابل مشاهده پیوسته در پایگاه داده های فضایی. VLDB J. 2011 ، 20 ، 371-396. [ Google Scholar ] [ CrossRef ]
علمری، س. تانیار، د. Safar, M. طبقه بندی برای پرس و جوهای شی متحرک در پایگاه داده های فضایی. ژنرال آینده. محاسبه کنید. سیستم 2014 ، 37 ، 232-242. [ Google Scholar ] [ CrossRef ]
گاید، وی. Günther, O. روش های دسترسی چند بعدی. کامپیوتر ACM. Surv. 1998 ، 30 ، 170-231. [ Google Scholar ] [ CrossRef ]
گوا، ایکس. ژنگ، بی. ایشیکاوا، ی. Gao, Y. درخواست‌های فراگیر مبتنی بر جهت برای توصیه‌های تلفن همراه. VLDB J. 2011 ، 20 ، 743-766. [ Google Scholar ] [ CrossRef ]
یونگ، اچ. کیم، YS; Chung, YD QR-tree: یک روش کارآمد و مقیاس پذیر برای ارزیابی پرس و جوهای محدوده پیوسته. Inf. علمی 2014 ، 274 ، 156-176. [ Google Scholar ] [ CrossRef ]
تائو، ی. شیائو، ایکس. چنگ، آر. جستجوی محدوده بر روی داده‌های نامشخص چند بعدی. ACM Trans. سیستم پایگاه داده 2007 ، 32 ، 1-15. [ Google Scholar ] [ CrossRef ]
خو، جی. گوتینگ، RH; ژنگ، ی. TM-RTree: شاخصی بر روی اشیاء متحرک عمومی برای جستجوهای محدوده. GeoInformatica 2015 ، 19 ، 487-524. [ Google Scholar ] [ CrossRef ]
سوول، بی. Salles، MV; کائو، تی. دمرز، ا. Gehrke, J. تجزیه و تحلیل تجربی اتصالات فضایی تکرار شده در حافظه اصلی. Proc. VLDB Enddow. 2013 ، 6 ، 1882-1893. [ Google Scholar ] [ CrossRef ]
تانیار، د. Rahayu، W. طبقه بندی برای پرس و جوهای منطقه در پایگاه داده های فضایی. جی. کامپیوتر. سیستم علمی 2014 ، 81 ، 1508-1531. [ Google Scholar ] [ CrossRef ]
هوانگ، YK; لین، LF; چانگ، YC; Su، IF پرس و جوی مستمر حداقل حداکثر فاصله محدود در شبکه های جاده ای. در فن آوری ها و برنامه های وب ; Springer: برلین، آلمان، 2012; صص 423-434. [ Google Scholar ]
لانگ، ج.ا. نلسون، TA مروری بر روش‌های کمی برای داده‌های حرکتی. بین المللی جی. جئوگر. Inf. علمی 2013 ، 27 ، 292-318. [ Google Scholar ] [ CrossRef ]
موراتیدیس، ک. Yiu، ML; پاپادیاس، دی. Mamoulis، N. نظارت مداوم نزدیکترین همسایه در شبکه های جاده ای. در مجموعه مقالات سی و دومین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، سئول، کره، 12 تا 15 سپتامبر 2006.
هوانگ، Y.-K. لین، L.-F. پردازش کارآمد پرس و جوی مستمر حداقل تا حداکثر فاصله محدود با به روز رسانی در شبکه های جاده ای. Inf. علمی 2014 ، 278 ، 187-205. [ Google Scholar ] [ CrossRef ]
وانگ، اچ. Zimmermann, R. پردازش پرس و جوهای محدوده مبتنی بر مکان پیوسته بر روی اجسام متحرک در شبکه های جاده ای. IEEE Trans. دانستن مهندسی داده 2011 ، 23 ، 1065-1078. [ Google Scholar ] [ CrossRef ]
الخالدی، ح. تانیار، د. بتز، جی. Alamri، S. مناطق امن پویا برای جابجایی جستجوهای محدوده در ناوبری تلفن همراه. بین المللی J. Ad Hoc Ubiquitous Comput. 2014 ، 16 ، 250-259. [ Google Scholar ] [ CrossRef ]
Cheema، MA; برانکوویچ، ال. لین، ایکس. ژانگ، دبلیو. وانگ، دبلیو. نظارت مستمر پرس و جوهای محدوده مبتنی بر فاصله. IEEE Trans. دانستن مهندسی داده 2011 ، 23 ، 1182-1199. [ Google Scholar ] [ CrossRef ]
پاپادیاس، دی. ژانگ، جی. مامولیس، ن. Tao, Y. پردازش پرس و جو در پایگاه های داده شبکه فضایی. در مجموعه مقالات بیست و نهمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، برلین، آلمان، 9 تا 12 سپتامبر 2003.
Egenhofer، MJ; Franzosa، روابط فضایی توپولوژیکی مجموعه نقطه RD. بین المللی جی. جئوگر. Inf. سیستم 1991 ، 5 ، 161-174. [ Google Scholar ] [ CrossRef ]
Egenhofer، MJ; هرینگ، جی. چارچوب ریاضی برای تعریف روابط توپولوژیکی. در مجموعه مقالات چهارمین سمپوزیوم بین المللی در مورد مدیریت داده های فضایی، زوریخ، سوئیس، 23-27 ژوئیه 1990.
لیو، اف. نقطه.؛ Hua, K. پرس و جو دامنه پویا در محیط های شبکه فضایی. در پایگاه داده و برنامه های کاربردی سیستم های خبره ; Springer: برلین، آلمان، 2006; صص 254-265. [ Google Scholar ]
دینگ، ز. Guting، RH مدیریت اجسام متحرک در شبکه های حمل و نقل پویا. در مجموعه مقالات شانزدهمین کنفرانس بین المللی مدیریت پایگاه داده های علمی و آماری، جزیره سانتورینی، یونان، 21-23 ژوئن 2004.
GT-Mobisim. 2015. در دسترس آنلاین: https://github.com/Sdcxv/gt-mobisim (در 14 دسامبر 2016 قابل دسترسی است).

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

شکل 2. ساختار نمودار خطی.

شکل 3. نمونه ای از لبه های قابل پل زدن. ( الف ) یک شی پرس و جو در شبکه. ( ب ) شماتیک لبه های قابل پل زدن

شکل 4. لبه فاصله.

شکل 5. درخت بسط مبتنی بر نمودار.

شکل 6. معماری سیستم.

شکل 7. GT-MobiSIM. ( الف ) شبیه سازی با 5000 شی متحرک و 500 شی پرس و جو. ( ب ) شبیه سازی با 10000 شی متحرک و 1000 شی پرس و جو.

شکل 8. زمان CPU مورد نیاز برای محاسبه نامزد پرس و جو.

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

شکل 10. مقایسه محدوده پیوسته Stojanovic (StojanovicCR) و محدوده پیوسته مبتنی بر نمودار خطی (LGCR). ( الف ) نتیجه آزمایش با 5000 شی متحرک و 500 شی پرس و جو. ( ب ) نتیجه آزمایش با 10000 شی متحرک و 1000 شی پرس و جو.

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

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

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

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

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

3. ساختارهای داده پیشنهادی

4. الگوریتم پرس و جو LGCR

4.1. الگوریتم ها

4.2. تجزیه و تحلیل پیچیدگی الگوریتم

5. آزمایشات

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

5.2. نتایج تجربی

5.3. بحث

6. نتیجه گیری

منابع

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

بعدیسیستم توصیه‌کننده مبتنی بر مکان با استفاده از رسانه‌های اجتماعی دارای برچسب جغرافیایی

بدون نظر

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