استراتژی های هرس هندسی کارآمد برای پرس و جوهای خط افق پیوسته

خلاصه

مشکل پردازش پرس و جو خط آسمان برای سال‌ها به خوبی مورد مطالعه قرار گرفته است. ادبیات الگوریتم های خط آسمان تا کنون عمدتاً نقاط پرس و جو ایستا را در ویژگی های استاتیک در نظر می گیرد. با استفاده محبوب از دستگاه های تلفن همراه همراه با افزایش تعداد برنامه های کاربردی تلفن همراه و کاربران، پردازش مستمر پرس و جو در خط آسمان در هر دو ویژگی استاتیک و پویا ضروری تر شده است. تلاش های موجود برای پشتیبانی از نقاط پرس و جو متحرک فرض می کند که نقطه پرس و جو تنها با یک جهت و سرعت ثابت حرکت می کند. در این مقاله، ما محاسبه خط افق پیوسته را بر روی یک مدل حرکت افزایشی پیشنهاد می‌کنیم. نقطه پرس و جو به صورت تدریجی در مراحل زمانی گسسته بدون محدودیت و قابل پیش بینی حرکت می کند. ویژگی‌های هندسی بر روی حرکت افزایشی که با ساختار داده‌های جنبشی نشان داده می‌شود، برای هرس بخشی از نقاط داده‌ای که در نتایج جستجوی خط افق نهایی گنجانده نشده‌اند، استفاده می‌شوند. استراتژی‌های هندسی مختلفی به صورت مجانبی برای هرس مجموعه داده‌های پرس‌وجو پیشنهاد شده‌اند، و مکانیسم‌های رویداد محور برای پردازش پرس‌وجوهای خط افق پیوسته اتخاذ می‌شوند. آزمایش‌های گسترده تحت مجموعه‌های داده‌ها و پارامترهای مختلف نشان می‌دهد که روش پیشنهادی قوی‌تر و کارآمدتر از عکس‌های فوری چندگانه از پرس‌وجوهای خط افق شاخه بهینه و محدود (BBS) I/O است.

کلید واژه ها:

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

1. معرفی

پرس و جو خط آسمان [ 1 ، 2 ] یک عملیات مفید برای بسیاری از برنامه های کاربردی مهم، از جمله تصمیم گیری بهینه چند معیاره است. با توجه به دو تاپل معین و چند بعدی u و v ، اگر u در همه ابعاد بدتر از v نباشد و کاملاً بهتر از v نباشد، u بر v مسلط است .حداقل در یک بعد با توجه به افزایش روزافزون استفاده از تلفن های هوشمند و در دسترس بودن موقعیت یاب های ارزان قیمت، خدمات مبتنی بر مکان (LBS) به طور فزاینده ای محبوب هستند، جایی که پرس و جوهای خط آسمان بر اساس مکان فعلی کاربر است، که به طور مداوم با حرکت کاربر تغییر می کند. با در نظر گرفتن نمونه ای از توریستی که به دنبال رستوران است، ممکن است به رستوران های نزدیک به محل خود که ارزان هستند و شهرت خوبی دارند علاقه مند باشد. از آنجایی که با سفر گردشگر فاصله بین گردشگر و رستوران در حال تغییر است، خط افق باید به طور مداوم به روز شود. علاوه بر این، گردشگر ممکن است مقصدی را در ذهن خود داشته باشد و به سمت آن مکان حرکت کند. همانطور که در شکل 1 نشان داده شده است ، کاربر در زمان

t_{0}

(یعنی در محل

q (t_{0})

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

t_{1}

، کاربر به محل می رسد

q (t_{1})

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

در دیگر برنامه‌های بلادرنگ مانند بازی‌های الکترونیکی و سیستم‌های نبرد دیجیتال، مسیر بین بازیکن و مقصدش ممکن است مستقیم نباشد. در عوض، مسیر پرپیچ و خم است، مانند مسیرهایی که در مثال رستوران قبلی یافت شد. هنگامی که بازیکن مبارز حرکت می کند، باید مراقب نگهبانانی باشد که از نظر انرژی، سلاح و غیره برای او نزدیک و خطرناک ترین هستند. رویکرد به روز رسانی نتایج پرس و جوی خط آسمان، محاسبه مجدد نتایج خط آسمان با استفاده از الگوریتم های کارآمد از ابتدا است، مانند خط افق شاخه و کران (BBS) [ 3 ، 4]]. با این حال، راه‌حل نسبتا مؤثر این است که آخرین نتایج محاسبه‌شده خط آسمان را در حافظه پنهان نگه دارید و فقط آن دسته از اشیاء داده‌ای را محاسبه کنید که ممکن است به نتایج خط آسمان وارد یا خارج شوند.

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

(v_{x}, v_{y})

. لین و همکاران [ 6 ] و گوو و همکاران. [ 7 ] حرکت نقطه پرس و جو a را یک خط در نظر گرفت و Lin و همکاران. [ 6 ] همچنین فرض کرد که نقطه پرس و جو در محدوده خاصی حرکت می کند. برای در نظر گرفتن حریم خصوصی مکان، نقطه پرس و جو کاربر گاهی اوقات در یک منطقه دیسک متفاوت فرض می شود [ 8 ]. در این مقاله، ما به حرکتی که معمولاً به صورت تدریجی در یک سری مراحل زمانی گسسته ارائه می‌شود، می‌پردازیم که برای کاربردهای واقعی عملی‌تر است.

از آنجایی که الگوهای حرکت گسسته برای نقاط متحرک مناسب تر هستند، ما از مدل حرکت افزایشی برای پرس و جوهای خط افق پیوسته استفاده می کنیم. یعنی نقاط پرس و جو به صورت تدریجی در مراحل زمانی گسسته حرکت می کنند. بر خلاف مدل های حرکتی موجود در [ 5 ، 6 ، 7 ، 8]، با توجه به مرز خطای رانش و سرعت رانش، مدل حرکت افزایشی هیچ محدودیتی برای حرکت یا پیش‌بینی‌پذیری آن قائل نیست (اگرچه جهت در این مقاله داده شده است، اما هیچ محدودیتی در جهت حرکت نداریم). تحت مدل حرکت افزایشی، ما از ویژگی‌های هندسی برای هرس منطقه‌ای استفاده می‌کنیم که در آن اشیاء داده در نتایج نهایی پرس و جوی خط آسمان قرار نخواهند داشت. برای جلوگیری از محاسبه نتایج خط آسمان از ابتدا در حالی که نقاط پرس و جو در حال حرکت هستند، ساختار داده ای مشابه ساختارهای داده جنبشی (KDSs) حفظ می کنیم [ 9 ، 10]] که در حوزه هندسه محاسباتی شهرت دارند. KDS با ذخیره تمام آن داده ها در برخی ساختارهای خاص رابطه، رابطه مورد نظر را بین داده ها حفظ می کند. محتویات در KDS تغییر نمی کند مگر اینکه رابطه بین برخی از نقاط داده تغییر کرده باشد. ساختار داده شامل فهرستی برای نتایج پرس و جوی خط آسمان در هر مرحله زمانی است. هنگامی که نقطه پرس و جو حرکت می کند، ساختار داده تصمیم می گیرد که آیا شی(های) داده وارد(های) نتایج خط آسمان می شود یا از مجموعه نتایج خارج می شود. پیاده سازی ساختار داده بر اساس مکانیسم های رویداد محور است. چارچوب پردازش پرس و جوهای خط آسمان پیوسته تحت یک مدل حرکت افزایشی همانطور که در شکل 2 نشان داده شده است نشان داده شده است.. ابتدا مجموعه داده ورودی با استفاده از ویژگی های هندسی بر اساس مدل حرکت افزایشی هرس می شود. سپس، نتایج اولیه خط آسمان را بر روی مجموعه داده هرس شده محاسبه می کنیم. مکانیسم‌های رویداد محور برای محاسبه نتایج پیوسته خط آسمان زمانی که نقطه پرس و جو در حال حرکت است، استفاده می‌شوند. به طور خلاصه، مشارکت های کلیدی به شرح زیر است:

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

بقیه مقاله به شرح زیر سازماندهی شده است. بخش 2 کارهای مرتبط را معرفی می کند. مقدمات در بخش 3 آورده شده است . بخش 4 استراتژی های هرس هندسی را ارائه می دهد. ساختارهای داده و مکانیسم‌های پردازش رویداد محور در بخش 5 ارائه شده‌اند . الحاقات به الگوهای حرکتی خاص در بخش 6 پیشنهاد شده است . نتایج مطالعات عملکرد جامع در بخش 7 مورد بحث قرار گرفته است . بخش 8 مقاله را به پایان می رساند.

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

پرس و جوهای خط افق عملگر skyline توسط Borzsonyi و همکاران به جامعه پایگاه داده معرفی شد. [ 1 ] در سال 2001. مطالعات متعاقب آن بر پردازش کارآمد پرس و جو خط افق متمرکز شده است. تان و همکاران [ 11 ] تکنیک های بیت مپ و فهرست را توسعه داد. چامیکی و همکاران [ 12 ] الگوریتم مرتب‌سازی-فیلتر-خط افق (SFS) را توسعه داد که حلقه تودرتو بلوک (BNL) را با از پیش مرتب‌سازی مجموعه داده بهبود بخشید. چندین بهینه سازی برای الگوریتم SFS (به عنوان مثال، [ 13 ]) کارایی آن را افزایش می دهد. کوسمن و همکاران [ 14 ] یک الگوریتم نزدیکترین همسایه (NN) ارائه کرد که به کاربران اجازه می داد تنظیمات ترجیحی را در طول زمان اجرا تغییر دهند. پاپادیاس و همکاران [ 4] یک الگوریتم پیشرو به نام خط افق شاخه و محدود (BBS) را پیشنهاد کرد که بر اساس تکنیک جستجوی نزدیکترین همسایه پشتیبانی شده توسط درختان R است. تغییرات اپراتور خط آسمان نیز مورد بررسی قرار گرفته است، مانند در یک محیط توزیع شده، شبکه های جاده، مکعب های خط افق، خطوط آسمان معکوس، و خطوط آسمان تقریبی، فقط به نام چند. برای برنامه های افزودنی بیشتر به [ 2 ] و [ 15 ] مراجعه کنید. با این حال، مطالعات فوق فقط نقاط پرس و جو ایستا را در ویژگی های استاتیک در نظر می گیرند. شریف زاده و همکاران [ 16 ] ابتدا پرس و جوهای خط افق فضایی را معرفی کرد که توسط دنگ و همکارانش نیز پرس و جوهای خط افق چند منبعی در شبکه های جاده ای نامیده می شوند. [ 17]. آنها ویژگی های اشیاء داده را به دو دسته متمایز می کنند: ویژگی های فضایی و ویژگی های غیر فضایی که به آنها ابعاد پویا و ایستا یا ویژگی های ایستا و ویژگی های پویا نیز می گویند. آنها همچنین فقط نقاط پرس و جو ایستا را در ویژگی های پویا در نظر گرفتند.

مدل سازی حرکت و پردازش خط آسمان. حوزه مرتبط دیگر نظارت بر حرکات پیوسته با استفاده از ساختارهای داده جنبشی (KDS) در هندسه محاسباتی است. باش و همکاران [ 9 ] ابتدا یک چارچوب مفهومی برای KDS پیشنهاد کرد تا به طور مداوم ویژگی های در حال تکامل داده های تلفن همراه را حفظ کند. یک فرض اساسی در چارچوب KDS این است که مسیرهای شیء مشخص هستند. اخیراً، تلاش‌های متعددی برای مقابله با داده‌ها در مدل‌های حرکتی بسیار محدودتر انجام شده است. مونت و همکاران [ 18 ] نگهداری ساختارهای هندسی را در محیطی که مسیرها ناشناخته است مورد مطالعه قرار دادند. آنها نگرانی های مربوط به ردیابی نقاط و به روز رسانی ساختار هندسی را به دو ماژول تقسیم کردند: پردازنده حرکت ( MP ) والگوریتم حرکت افزایشی ( IM ). آنها همچنین یک مدل آنلاین ساده ارائه کردند که در آن دو عامل به نام‌های مشاهده‌گر و سازنده برای حفظ حرکت افزایشی همکاری می‌کردند [ 19 ].

حرکت در نظر گرفته شده در پرس و جوهای خط آسمان شامل یک نقطه پرس و جو متحرک و اشیاء داده متحرک است. هوانگ و همکاران [ 5 ] یک ساختار داده مبتنی بر جنبشی برای به روز رسانی نتایج خط آسمان پیشنهاد کرد. نقطه پرس و جو همراه با الگوهای حرکتی از پیش تعریف شده حرکت می کرد (یعنی حرکت یکنواخت در یک خط مستقیم). لی و همکاران [ 20 ] نیز مشکل مشابهی را مورد مطالعه قرار داد. با این حال، هر دو تلاش بر این فرض تکیه می کنند که سرعت نقاط متحرک مشخص است. متأسفانه، این فرض در بسیاری از کاربردهای دنیای واقعی که نقاط (مثلاً اتومبیل‌ها، گردشگران) اغلب الگوهای حرکتی خود را تغییر می‌دهند (مثلاً سرعت و جهت) صادق نیست. علاوه بر این، گسترش تکنیک‌های آن‌ها برای سناریوهایی که سرعت‌ها ناشناخته هستند، بی‌اهمیت است. لین و همکاران [ 6] فرض کرد که نقطه پرس و جو در یک محدوده مکانی از پیش تعریف شده به جای مکان دقیق یا حرکت همراه با یک قطعه خط است. برای مدیریت حرکت اشیاء پرس و جو، نسخه افزایشی راه حل خط افق مبتنی بر خط ابداع شده است تا هم اندازه مجموعه نتایج و هم هزینه محاسبات را کاهش دهد. Hsueh et. al [ 21 ] الگوریتمی را برای به روز رسانی خط افق زمانی که اشیاء داده مقادیر ویژگی خود را تغییر می دهند، ارائه کرد. چیما و همکاران [ 22] یک رویکرد مبتنی بر منطقه امن برای نظارت بر پرس و جوهای خط افق متحرک پیشنهاد کرد که به درخواست ها اجازه می دهد به شکل دلخواه حرکت کنند. نتایج پرس و جو باید فقط زمانی به روز شوند که پرس و جو از منطقه امن خود خارج شود. در چارچوب، زمانی که یک نقطه پرس و جو در فاصله زمانی بین دو رویداد مجاور حرکت می کند، مسیر آن متعلق به یک منطقه امن است. وو و همکاران [ 23] عدم قطعیت را هم در نقطه پرس و جو و هم در نقاط مورد علاقه (POIs) برای پرس و جوهای خط افق فضایی معرفی کرد. عدم قطعیت ها در اینجا به صورت دیسک های مربعی با شعاع های متنوع نشان داده می شوند. در مقایسه با این روش، مدل حرکت افزایشی ما نه تنها عدم قطعیت ها (که توسط دیسکی که شعاع آن حداکثر سرعت است نشان داده می شود)، بلکه جهت ها را نیز در نظر می گیرد. تفاوت دیگر با این مطالعات این است که ما نقاط داده‌ای که به نتایج نهایی خط آسمان تعلق ندارند را بر اساس ویژگی‌های هندسی به عنوان یک مرحله پیش پردازش هرس می‌کنیم، که به نقاط داده کمتری دسترسی پیدا می‌کند و در نتیجه در زمان CPU بیشتر صرفه‌جویی می‌شود. نویسندگان در [ 3 ، 4 ، 24 ، 25 ، 26 ] خطوط افق پویا را مطالعه کردند. با این حال، [ 3 ، 4 ،24 ] از روش شاخه و کران (BBS) برای محاسبه نتایج خط آسمان از ابتدا استفاده کرد. مراجع [ 25 ، 26 ] از مکانیزم ذخیره سازی برای سرعت بخشیدن به پردازش پرس و جو خط افق پویا/محدودیت استفاده کردند. با این حال، برای پرس و جوهای خط افق پیوسته، آنها بر اساس پرس و جوهای گذشته هستند که به طور کامل از نتایج جستجوی لحظه آخری استفاده نمی کنند. علاوه بر این، روش های ساچاریدیس و همکاران. [ 25 ] به دلیل کاستی های مکانیسم های کدگذاری بیت مپ عملی نیستند.

3. مقدمات

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

3.1. تعریف مشکل

با توجه به n نقطه داده در مجموعه داده

D

، هر نقطه دارای ویژگی های غیر فضایی d بعدی است که به آن ویژگی های استاتیک نیز می گویند. هر نقطه

p_{i}

به عنوان ذخیره می شود

(p (p_{i}), p_{i, 1}, p_{i, 2}, . . ., p_{i, d})

، و

p (p_{i})

p_{i, j}

محل قرار دارند

p_{i}

و j صفت استاتیک بعدی از

p_{i}

، به ترتیب. بدین ترتیب،

p_{i}

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

p_{i} = (p_{i, 1}, p_{i, 2}, . . ., p_{i, d}, p_{i, d + 1})

، جایی که

p_{i, d + 1}

فاصله نقطه پرس و جو q و نقطه داده است

p_{i}

تعریف 1.

(Static Dominance) برای دو نقطه داده

p_{i}, p_{j}

و تمام صفات

p_{i}

به جز ویژگی فاصله،

\forall k, k = (1, 2, . . ., d)

p_{i, k} \leq p_{j, k}

و حداقل یک < برقرار است، ما آن را می گوییم

p_{i}

به صورت ایستا تسلط دارد

p_{j}

، به عنوان نشان داده شده است

p_{i} ≺_{s t a} p_{j}

تعریف 2.

(تسلط کامل) برای دو نقطه داده

p_{i}, p_{j}

\forall k, k = (1, 2, . . ., d + 1)

p_{i, k} \leq p_{j, k}

و حداقل یک < برقرار است، ما آن را می گوییم

p_{i}

کاملا مسلط است

p_{j}

، نشان داده شده است

p_{i} ≺ p_{j}

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

S_{s t a}

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

S

، و تفاوت این دو مجموعه

S - S_{s t a}

، مانند

S_{c h g}

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

S_{c h g}

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

S_{c h g}

شامل دو بخش است: بخش اول

S_{i n}

، که شامل نقاط داده از مجموعه داده غیر آسمانی است

D - S

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

S_{r e m a i n}

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

S

هنگامی که نقطه پرس و جو حرکت می کند.

به جای پرس و جوهای خط افق فوری مانند روش I/O بهینه BBS، کوئری های خط افق پیوسته را به صورت زیر تعریف می کنیم.

تعریف 3.

(پرس و جوهای مستمر خط افق) با توجه به نتایج خط افق

S_{0}

در زمان

t_{0}

، نتیجه خط افق

S_{1}

در دفعه بعد

t_{1}

بر اساس

S_{0}

و فقط دو مجموعه متنوع را در نظر می گیرد:

S_{0} - S_{1}

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

t_{0}

، و

S_{1} - S_{0}

، داده ها از

D - S_{0}

تبدیل به نقاط افق

از منابع [ 1 ، 5 ، 20 ، 21 ]، می دانیم که نتیجه خط آسمان

S_{0}

در مقایسه با

D

. با این حال، مجموعه داده

D - S_{0}

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

D - S_{0}

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

3.2. مدل حرکت افزایشی

مدل حرکت افزایشی اولین بار توسط Mount و همکاران ارائه شد. [ 18 ]. بعدها، چو و همکاران. [ 19 ] از این مدل برای حفظ ساختارهای درختی شبکه و شبکه تحت یک مدل حرکت افزایشی استفاده کرد. ما به معرفی مختصری از این مدل با اصلاحات تطبیقی برای مشکل خود می پردازیم.

3.2.1. موقعیت نقطه پرس و جو

بگذارید q یک نقطه پرس و جو باشد. موقعیت q در فضای اقلیدسی در زمان t به صورت نشان داده می شود

q (t)

. حرکت نقطه q

M

، دنباله ای محدود از موقعیت های نقطه ای است که در نمونه های زمانی گسسته نمونه برداری شده اند:

M = < q (t_{0}), q (t_{1}), . . ., q (t_{N}) >

، جایی که

t_{i - 1} < t_{i}

. فاصله بین دو نمونه متوالی یک مرحله زمانی است:

s = [t_{i - 1}, t_{i}]

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

s v

، و جابجایی واقعی آن توسط بردار داده می شود

u = q (t_{i}) - q (t_{i - 1})

. اجازه دهید

| u |

طول بردار اقلیدسی را نشان می دهد

u

. ما از drift این نقطه در زمان استفاده می کنیم

t_{i}

برای نشان دادن خطای نسبی بین جابجایی های واقعی و تخمینی:

ه د r i f تی = | u - s v | | s v |

(1)

اجازه دهید δ کران رانش باشد. می گوییم که حرکت

M

این تخمین حرکت را برآورده می کند اگر برای تمام مراحل زمانی رانش از

M

نسبت به برآورد سرعت v حداکثر δ است . با توجه به تخمین سرعت v و با توجه به هر زمان t ، مکان تخمین زده شده نقطه پس از زمان سپری شده s به صورت

\hat{q} (t, s) = q (t) + s v

. به عنوان مثال، محل تخمینی از

q (t_{i - 1})

بعد از مرحله s است

\hat{q} (t_{i - 1}, s)

( شکل 3 الف را ببینید). اجازه دهید

B (q, r)

گوی اقلیدسی را با شعاع r که در نقطه q مرکز است نشان دهید . از تعاریف بالا داریم

q (تی من) \in B (q^(تی من - 1, s), s δ | v |)

(2)

فرض کنید T یک بازه زمانی از زمان شروع شده در زمان t باشد ، $T = [t, t + s]$ . اگر یک حرکت $M$ یک تخمین حرکت داده شده را برآورده می کند، سپس برای هر نمونه زمانی $t + s^{'} \in T$ ، $0 \leq s^{'} \leq s$ ، نقطه پرس و جو $q (t + s^{'})$ درون یک توپ اقلیدسی قرار دارد که در مرکز آن قرار دارد $\hat{q} (t, s^{'})$ و مرز $M$ توسط یک سری از توپ های ذکر شده در بالا تعیین می شود ( شکل 3 ب را ببینید). معادله زیر محدودیت های موقعیت خود را در هر زمان مشخص می کند:

مگابایت (M) = ⋃ 1 \leq س “ \leq s ب (q^(ت ، س “) ، δ س “ | v |)

(3)

3.2.2. تابع فاصله پارامتری زمان

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

v = q ( تی من ) - q ( تی من - 1 ) تی من - تی من - 1

(4)

برای سادگی، فرض می کنیم که نقطه پرس و جو q در فضای 2 d حرکت می کند،

v = (v_{x}, v_{y})

، و موقعیت q در زمان

t_{i}

است

q (t_{i}) = (x_{i}, y_{i})

. ما استفاده می کنیم

q_{s}

برای نشان دادن مرکز توپ اقلیدسی. در زمان

t_{i}

q_{s} = (x_{i}, y_{i})

. پس از مدتی سپری شده از

s = [t_{i}, t_{i + 1}]

، مرکز مدل حرکت افزایشی

q_{s}

تغییرات

(x_{i + 1}, y_{i + 1})

و برابر است با

(x_{i} + s v_{x}, y_{i} + s v_{y})

. سپس، برای یک نقطه داده p واقع در

(x_{p}, y_{p})

، در زمان

t_{i + 1}

، فاصله تخمینی بین

q_{s}

و p را می توان به صورت زیر بیان کرد:

D^(ص ، q س) = (ایکس من + s v ایکس - ایکس پ) 2 + (y من + s v y - y پ) 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - \sqrt

(5)

با معادله ( 3 )، محل تخمینی نقطه پرس و جو است $q (t_{i + 1}) \in B (\hat{q} (t_{i}, s), s δ | v |)$ . از آنجایی که مکان تخمین زده شده یک نقطه پرس و جو پس از زمان سپری شده s در یک توپ اقلیدسی است، فاصله واقعی بین $q (t_{i + 1})$ و p در محدوده معینی محدود شده است ( شکل 3 ب را ببینید). ما استفاده می کنیم $I (p, q (t_{i + 1}))$ برای نشان دادن فاصله بین p و $q (t_{i + 1})$ :

من (p, q (تی من + 1)) = [D^(ص ، q س) - s δ | v | ، D^(ص ، q س) + s δ | v |]

(6)

بعلاوه، $d i s t (p, q (t_{i + 1}))$ برای نشان دادن فاصله واقعی بین p و استفاده می شود $q (t_{i + 1})$ ، که در محدوده $I (p, q (t_{i + 1}))$ با معادله ( 6 ) نشان داده می شود.

3.3. رابطه تسلط فاصله

همانطور که نقطه پرس و جو دائما حرکت می کند، فاصله بین نقطه متحرک و هر نقطه داده تغییر می کند، که نادرست است زیرا نمی توانیم موقعیت واقعی نقطه پرس و جو را دقیقاً پیش بینی کنیم. با این حال، ما مطمئن هستیم که فاصله در یک محدوده مشخص است:

I (p_{i}, q_{s})

. علاوه بر این، اگر

d i s t (p_{i}, q_{s}) < d i s t (p_{j}, q_{s})

p_{i}

به نقطه پرس و جو نزدیک تر از

p_{j}

. رابطه سلطه بین

d i s t (p_{i}, q_{s})

d i s t (p_{j}, q_{s})

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

p_{i}

از … بهتر است

p_{j}

در فاصله

فرض کنید پس از گذشت زمان s ، موقعیت یک نقطه پرس و جو در شکل 4 نشان داده شده است ، شعاع مدل حرکت افزایشی برابر است با

s δ | v |

، و L نشان دهنده عمود بر عمود بر

p_{i} p_{j}

که توپ را به دو ناحیه تقسیم می کند:

D_{i}

D_{j}

. سپس از A و B برای نشان دادن دو تقاطع L و توپ استفاده می کنیم. زمانی که نقطه پرس و جو q در منطقه باشد

D_{i}

d i s t (p_{i}, q_{s}) < d i s t (p_{j}, q_{s})

لم 1.

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

p_{i} p_{j}

و کران مدل حرکت افزایشی است

2 θ

، سپس این احتمال وجود دارد که

p_{i}

از … بهتر است

p_{j}

در فاصله، نشان داده شده با

P r (p_{i} <_{d i s t} p_{j})

، قابل محاسبه است

پ r (پ من < د من تی_پ j) = θ - sin θ cos θ π 2

(7)

اثبات

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

D_{i}

p_{i}

به نقطه پرس و جو نزدیکتر از

p_{j}

; در نتیجه، این احتمال وجود دارد که

p_{i}

از … بهتر است

p_{j}

در فاصله برابر با احتمال قرار گرفتن نقطه پرس و جو در منطقه است

D_{i}

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

D_{i}

به کل توپ

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

p_{i} p_{j}

است

2 θ

، بنابراین مساحت AqB فن شکل:

اس (⦡ A q ب) = 2 θ 2 π π آر 2 = θ آر 2

(8)

جایی که R نشان دهنده شعاع توپ است.

علاوه بر این، مساحت مثلث ABq برابر است با:

اس (△ A B q) = 1 2 | A B | \times | q سی | = 1 2 2 R sin θ R cos θ = 1 2 آر 2 گناه (2 θ)

(9)

بنابراین، منطقه از $D_{i}$ را می توان به صورت زیر بیان کرد:

اس (D من) = S (⦡ A q ب) - S (△ A B q) = ( 2 θ - sin ( 2 θ ) آر 2 2 π = ( θ - sin θ cos θ ) آر 2 π

(10)

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

پ r (پ من < د من تی_پ j) = اس ( D من ) π آر 2 = θ - sin θ cos θ π 2

(11)

☐

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

p_{i}

از … بهتر است

p_{j}

در فاصله

تعریف 4.

(غلبه در فاصله) اگر احتمال آن

p_{i}

از … بهتر است

p_{j}

در فاصله بیشتر از یک آستانه از پیش تعریف شده است – یعنی

P r (p_{i} <_{d i s t} p_{j}) > τ

– ما این را می گوییم

p_{i}

مسلط است

p_{j}

در فاصله (یعنی

p_{i} ≺_{d i s t} p_{j}

تعریف 5.

(خط آسمان بر اساس آستانه ها) اگر

1 - τ \leq P r (p_{i} <_{d i s t} p_{j}) \leq τ

یا

1 - τ \leq P r (p_{j} <_{d i s t} p_{i}) \leq τ

p_{i}

p_{j}

نمی توانند در فاصله بر یکدیگر تسلط داشته باشند و اگر هیچ نقطه داده دیگری نمی تواند بر یکدیگر تسلط داشته باشد

p_{i}

یا

p_{j}

، هر دو متعلق به خطوط آسمان هستند.

در اینجا احتمال با نسبت دو ناحیه تعریف می شود ( شکل 4 و معادله ( 11 ) را ببینید). پرس و جوهای خط افق مانند Pei و همکاران، جستارهای احتمالی خط افق نیستند. [ 27 ] که در آن احتمالات وقوع احتمالی هر جهان ممکن را از فضای PWS (معناشناسی جهان ممکن) که توسط اشیاء داده نامشخص تشکیل شده است نشان می دهد.

4. ارزیابی تغییرات خط افق تحت حرکت افزایشی

4.1. هرس با استفاده از خواص هندسی

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

p_{i}

نمی تواند تسلط یابد

p_{j}

در ابعاد استاتیک،

p_{i}

نمی تواند تسلط یابد

p_{j}

پس از در نظر گرفتن بعد فاصله به این معنا که،

p_{i}

می تواند تسلط یابد

p_{j}

فقط اگر

p_{i}

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

p_{j}

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

لم 2.

برای نقطه پرس و جو q در زمان t، if

s p_{f}

دورترین نقطه در

S_{s t a}

به نقطه پرس و جو q، سپس هر نقطه

p_{t}

که نمی تواند تسلط یابد

s p_{f}

در فاصله در نیست

S

اثبات

به طور مشخص،

p_{t} \notin S_{s t a}

، بدین ترتیب

\exists s p \in S_{s t a}

، و

s p

مسلط است

p_{t}

در ابعاد استاتیک از آنجا که

s p_{f}

دورترین نقطه در

S_{s t a}

به نقطه پرس و جو q

s p

مسلط است

s p_{f}

در فاصله و

s p_{f}

مسلط است

p_{t}

در فاصله؛ بدین ترتیب،

p_{t}

تحت سلطه است

s p

هنگام در نظر گرفتن فاصله و ابعاد استاتیک،

p_{t} \notin S

. ☐

لم 2 هنگام پردازش پرس و جوهای خط افق، یک کران جستجو را نشان می دهد. ما می توانیم قبل از پردازش پرس و جو بخشی از نقاط داده غیرمجاز را هرس کنیم: نقاطی که از نظر فاصله توسط همه نقاط در غالب هستند.

S_{s t a}

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

v

داده می شود، دامنه توپ در مدل حرکت افزایشی تعیین می شود.

لم 3.

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

L_{1}

L_{2}

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

H_{1} H_{1}^{'}

H_{2} H_{2}^{'}

عمودی به

L_{1}

L_{2}

، به ترتیب. همه این خطوط کل فضای منطقه را به سه قسمت تقسیم می کنند: منطقه A، منطقه B، و منطقه باقی مانده. سپس، برای هر نقطه داده p در منطقه B، اگر یک نقطه داده وجود داشته باشد

s k

در منطقه A و برآورده می کند

s k ≺ p

در حالی که نقطه پرس و جو در منطقه قرار دارد

L_{1} q L_{2}

، p نمی تواند در افق نهایی باشد.

اثبات

در ابتدا p تحت سلطه است

s k

، بنابراین

s k

در تمام ابعاد استاتیک بر p غالب است (یا برابر است) .

d i s t (s k, q) \leq d i s t (p, q)

. ممکن است دو موقعیت در آینده وجود داشته باشد:

$s k$ همیشه در خط افق است
$s k$ در یک مرحله زمانی خط افق را ترک می کند.

برای وضعیت 1، حالت شدید را در نظر بگیرید:

s k

در مرز منطقه A قرار دارد (

q H_{1}^{'}

یا

q H_{2}^{'}

، سپس q را به عنوان مرکز و

d i s t (s k_{0}, q)

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

s k

در ابتدا، همچنان تحت سلطه خواهد بود

s k

در آینده.

p_{0}

یکی از موارد شدید است: از طریق نقطه q یک خط عمودی به رسم می کنیم

p_{0} s k_{0}

(یعنی خط

L_{1}

، زیرا کل ناحیه تخمینی q در سمت راست خط قرار دارد، بنابراین

s k_{0}

به نقطه پرس و جو نزدیکتر از

p_{0}

در آینده و

s k_{0}

هنوز هم مسلط است

p_{0}

برای وضعیت 2، اگر

s k

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

s k^{'} ≺ s k

; در این مورد،

s k^{'}

مسلط است (یا برابر است با)

s k

در تمام ابعاد استاتیک و

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

. با اشاره به وضعیت 1،

s k ≺ p

همچنان پابرجاست، پس

s k^{'} ≺ p

و p را می توان با خیال راحت هرس کرد. ☐

ما از Lemma 3 برای تقسیم یک مجموعه داده به چندین منطقه استفاده می کنیم و هر نقطه داده را بر اساس منطقه ای که به آن تعلق دارد تأیید می کنیم، سپس نقاطی را که پتانسیل ورود به خط آسمان را ندارند هرس می کنیم.

S

در آینده.

لم 4.

بر اساس Lemma 3، محدودیت زیر را اضافه می کنیم: زاویه مدل حرکت افزایشی

α \leq 60^{\circ}

همانطور که در شکل 6 الف نشان داده شده است. L خط امتداد معکوس نیمساز زاویه ای است

∠ L_{1} q L_{2}

H_{2} H_{2}^{'}

و L کل فضای منطقه را به چند قسمت تقسیم می کند که با رنگ خاکستری تیره و خاکستری روشن مشخص می شود. زمانی که نقطه پرس و جو q همچنان در منطقه تخمینی قرار دارد و یکی از دو حالت زیر برآورده می شود، نقطه داده p نمی تواند در خط آسمان نهایی باشد:

1 .: p در منطقه قرار دارد $D_{1}$ و نقطه دیگری بر آن غالب است $S$ که در $C_{1}$ .
2 .: p در منطقه قرار دارد $D_{2}$ و نقطه دیگری بر آن غالب است $S$ که در $C_{2}$ .

توجه داشته باشید که $D_{1}$ ، $D_{2}$ ، $C_{1}$ ، و $C_{2}$ مناطق ذوزنقه ای در شکل 6 هستند .

اثبات

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

D_{1}

ما فقط باید این را ثابت کنیم

s k

همچنان p در فاصله غالب است. مشابه اثبات لمای 3، وقتی

α \leq 60^{\circ}

، عمود بر p و را رسم می کنیم

s k

، منطقه تخمینی q بر روی است

s k

ضلع عمود بر عمود بر شکل 6 یک وضعیت شدید را نشان داده است. زیرا

H_{1} H_{1}^{'}

H_{2} H_{2}

عمود بر عمود بر هستند

L_{1}

L_{2}

، به ترتیب،

α + β = β + γ

، سپس

α = γ

. به طور مشخص،

γ + 2 θ = 180^{\circ}

. چه زمانی

γ = 60^{\circ}

p_{0} s k_{0} ∥ H_{2} H_{2}^{'}

، پس عمود بر عمود بر

p_{0} s k_{0}

خط است

L_{2}

، به عنوان منطقه تخمینی q بر روی است

s k_{0}

طرف از

L_{2}

s k_{0}

هنوز هم مسلط است

p_{0}

در آینده. وقتی p متعلق به منطقه باشد

D_{2} = a r e a (L q H_{2})

متقارن به

D_{1}

، مشابه وضعیت 1، p غالب است همانطور که در شکل 6 ب نشان داده شده است. ☐

لم 5.

همانطور که در شکل 7 نشان داده شده است ، اجازه دهید α زاویه مدل حرکت افزایشی باشد، سپس زاویه اضافی α را به بیرون اضافه می کنیم.

L_{1}

L_{2}

، و دو خط کمکی بکشید

L_{1}^{'}

L_{2}^{'}

. پس از گذشت زمان s، فرض کنید که موقعیت تخمینی نقطه پرس و جو است

q^{'}

. اگر در ابتدا هر نقطه داده p در منطقه P تحت سلطه یک نقطه باشد

s k

در منطقه S، p در زمان سپری شده s نمی تواند در خط افق باشد.

اثبات

مشابه اثبات لمای 3، ابتدا عمود بر عمود p و را رسم می کنیم.

s k

و چیزی که باید ثابت کنیم این است که ناحیه تخمینی q روی است

s k

ضلع عمود بر عمود بر شکل 7 حالت شدید را نشان می دهد: عمود بر عمود را رسم کنید

s k_{0}

p_{0}

s k_{0}

مسلط است

p_{0}

در ابتدا، در این وضعیت، نیمساز عمود از موقعیت شروع q می گذرد . علاوه بر این،

∠ L_{1}^{'} q L_{1} = ∠ L_{1} q L_{2} = α

، بنابراین عمود بر عمود بر آن است

L_{1}

. منطقه تخمینی q بر روی است

s k_{0}

طرف از

L_{1}

s k_{0}

هنوز هم مسلط است

p_{0}

در زمان سپری شده از s . ☐

4.2. تغییر خط افق در زیر زمینه های متحرک

وقتی نقطه پرس و جو حرکت می کند، تسلط نقاط داده ممکن است تغییر کند. همانطور که در شکل 8 نشان داده شده است ، در زمان

t_{1}

P r (p_{j} <_{d i s t} p_{i}) = 1

p_{j} ≺_{d i s t} p_{i}

، و در زمان

t_{5}

P r (p_{i} <_{d i s t} p_{j}) = 1

p_{i} ≺_{d i s t} p_{j}

. فواصل تا نقطه پرس و جو q از

p_{i}

p_{j}

همپوشانی در زمان

t_{2}

t_{3}

، و

t_{4}

. اگرچه رابطه تسلط فاصله در این لحظات نامشخص است، ما هنوز هم می‌توانیم احتمال تسلط را در فاصله محاسبه کنیم.

در لحظه

t_{3}

، عمود بر عمود بر

p_{i} p_{j}

از مرکز می گذرد،

P r (p_{j} <_{d i s t} p_{i}) = 0.5

، با توجه به تنظیم آستانه

0.5 \leq τ \leq 1

، رابطه غالب در فاصله احتمالاً تغییر می کند. در لحظه

t_{3}

، رابطه با τ تعیین می شود . به طور شهودی، ما تنظیم کردیم

τ = 0.5

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

t_{2}

s_{i}

باید تحت سلطه یک نقطه افق باشد

s_{j}

. آن نقاطی که قبلاً بر نقطه غالب بودند

t_{2}

تسلط بر آن را متوقف خواهد کرد. اگر

τ > 0.5

، به دلیل تغییر رابطه سلطه در فاصله، زمانی که

p_{j}

خط افق را ترک می کند دیرتر از

t_{2}

. به طور مشابه، زمانی که

p_{i}

وارد خط افق می شود زودتر از

t_{2}

. یعنی هر دو

p_{j}

p_{i}

تا زمانی که نتوانند در فاصله دور بر یکدیگر مسلط شوند، در خط افق باقی خواهند ماند. اگر تقاطع وجود نداشته باشد، رابطه تسلط فاصله بدون تغییر باقی می ماند. اینکه یک تقاطع بر خط افق تأثیر می گذارد یا نه، بستگی به مجموعه ای دارد

p_{i}

p_{j}

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

ما قضایای زیر را داریم تا این احتمالات را به تفصیل شرح دهیم.

قضیه 1.

اگر یکی از شرایط زیر قبل از t برقرار باشد، تقاطع تأثیری بر خط افق ندارد:

1 .: در همه شرایط، $p_{i} \in S_{s t a}$ ، $p_{j} \in S$ ;
2 .: در همه شرایط، $p_{i} \notin S$ ;
3 .: در شرایط C، $p_{i} \in S$ ، $p_{j} \notin S$ ;
4 .: در شرایط B، $p_{i} \in S_{c h g}$ ، $p_{j} \in S$ .

توجه داشته باشید که شرایط A، B، C در جدول 2 نشان داده شده است .

اثبات

اگر $p_{i} \in S_{s t a}$ ، بدیهی است که $p_{i}$ خط افق را ترک نمی کند مانند $p_{j} \in S$ ، دو حالت وجود دارد. ابتدا فرض می کنیم که $p_{j} \in S_{s t a}$ . بدین ترتیب، $p_{j}$ هنوز در خط افق است و خط افق بدون تغییر باقی می ماند. دوم، ما این را فرض می کنیم $p_{j} \in S_{c h g}$ . از آنجا که $p_{j} \in S$ ، هیچ نقطه p وجود ندارد که غالب باشد $p_{j}$ . قبل از زمان t ، نقاطی که پتانسیل تسلط دارند $p_{j}$ با $p_{j}$ . بنابراین، $p_{j}$ هنوز در است $S_{c h g}$ و هیچ تغییری در خط افق ایجاد نمی کند.
از آنجا که $p_{i} \notin S$ قبل از زمان t باید حداقل یک نقطه وجود داشته باشد $s k \in S$ در خط افق که بر آن مسلط است. تقاطع هیچ تاثیری روی $s k ≺_{d i s t} p_{i}$ اگر $p_{j} \in S_{s t a}$ و $p_{j}$ خط افق را ترک نخواهد کرد علاوه بر این، اگر $p_{j} \in S_{c h g}$ ، به همان دلیلی که در مورد (1) وجود دارد، $p_{j}$ در خط افق خواهد ماند اگر $p_{j} \notin S$ مانند مورد (1).
از آنجا که $p_{i} \in S$ ، دو حالت وجود دارد: $p_{i} \in S_{s t a}$ و $p_{i} \in S_{c h g}$ . ابتدا فرض می کنیم $p_{i} \in S_{s t a}$ . سپس، $p_{i}$ بعد از تقاطع هنوز در خط افق است. سپس، ما فرض می کنیم $p_{i} \in S_{c h g}$ . از یک طرف، زیرا $p_{j} \notin S$ ، $p_{j}$ نمی تواند تسلط یابد $p_{i}$ در تمام ابعاد استاتیک و $p_{i}$ هنوز یک نقطه خط افق بعد از تقاطع است. از سوی دیگر، $p_{j} \notin S$ و $p_{i}$ و $p_{j}$ نمی توانند از راه دور بر یکدیگر مسلط شوند، بنابراین $p_{j}$ قادر به تسلط نیست $p_{i}$ ، باید نکته ای وجود داشته باشد $p \in S$ که غالب است $p_{j}$ . بنابراین هیچ تلاقی بین p و وجود ندارد $p_{j}$ ، $p ≺ p_{j}$ و $p_{j} \notin S$ .
به همان دلیلی که در مورد (1) $p_{j}$ بعد از تقاطع هنوز در خط افق است. $p_{i} \in S_{c h g}$ ، فرض کن که $p_{j}$ مسلط است $p_{i}$ در تمام ابعاد استاتیک بعد از تقاطع، $p_{j}$ و $p_{i}$ نمی توانند از راه دور بر یکدیگر مسلط شوند، بنابراین $p_{j}$ نمی تواند تسلط یابد $p_{i}$ . بدین ترتیب، $p_{i} \in S_{c h g}$ .

☐

قضیه 2.

اگر یکی از شرایط زیر قبل از t برقرار باشد، یک تقاطع ممکن است روی خط افق تأثیر بگذارد:

1 .: در شرایط A یا B، $p_{i} \in S$ ، $p_{j} \notin S$ ;
2 .: در شرایط A یا C، $p_{i} \in S_{c h g}$ ، $p_{j} \in S$ .

توجه داشته باشید که شرایط A، B و C در جدول 2 نشان داده شده است

اثبات

اولاً این را فرض کنید $p_{i} \in S_{s t a}$ . بنابراین، $p_{i}$ بعد از تقاطع هنوز در خط افق است. از آنجا که $p_{j} \notin S$ ، باید حداقل یک نقطه افق در آن وجود داشته باشد $S$ تسلط بر آن اگر $p_{i}$ مسلط است $p_{j}$ قبل از t و سپس بعد از t ممکن است یکی از شرایط زیر وجود داشته باشد: $p_{j} ≺_{d i s t} p_{i}$ یا $p_{i}$ و $p_{j}$ نمی توانند از راه دور بر یکدیگر مسلط شوند. در نتیجه، $p_{j}$ در هر دو موقعیت بعد از t وارد آسمان می شود .
به طور مشخص، $p_{j}$ بعد از t از خط افق خارج نخواهد شد . $p_{i} \in S_{c h g}$ ، $p_{j} \in S$ ، اگر $p_{j}$ مسلط است $p_{i}$ در تمام ابعاد استاتیک، بعد از t $p_{i}$ از آن زمان خط افق را ترک خواهد کرد $p_{j} ≺_{d i s t} p_{i}$ .

☐

طبق قضیه 2، ما فقط باید دو مورد زیر را در نظر بگیریم که در آنها ممکن است خط افق تغییر کند:

در ابتدا، $s_{i} \in S$ ، $s_{n} \notin S$ ، و $s_{i} ≺ s_{n}$ . بعد از یک تقاطع، $s_{i}$ دیگر نمی تواند تسلط یابد $s_{n}$ ، سپس $s_{n}$ می تواند وارد خط افق شود و بستگی به این دارد که آیا $s_{i}$ نقطه افق منحصر به فردی است که بر آن مسلط است.
در ابتدا، $s_{i} \in S_{c h g}$ ، $s_{j}$ مسلط است $s_{i}$ در تمام ابعاد استاتیک بعد از یک تقاطع، $s_{i}$ می تواند تحت سلطه باشد $s_{j}$ و خط افق را ترک کنید.

5. محاسبه خط آسمان

5.1. پردازش مستمر پرس و جو Skyline

ما اکنون تکنیک های پردازش پرس و جو پیوسته خط افق را مطابق با تجزیه و تحلیل بالا بررسی می کنیم. یک راه ساده این است که الگوریتم های موجود را فراخوانی کنیم تا پرس و جوهای خط آسمان را در هر مرحله زمانی پردازش کنیم تا نتایج پرس و جو مستمر را بدست آوریم. از آنجایی که ما موقعیت تخمین زده شده نقطه پرس و جو و پارامترهای مدل حرکت افزایشی مرتبط را می دانیم، نتایج معتبر هستند. با این حال، پردازش پرس‌و‌جوهای خط آسمان پیوسته به این روش نیاز به پیمایش مکرر کل مجموعه داده دارد که به ناچار زمان اجرا و ورودی/خروجی را افزایش می‌دهد. در عمل، سرعت یک نقطه پرس و جو خیلی سریع نیست. بنابراین، خط افق اغلب تغییر نخواهد کرد. به عنوان مثال، همانطور که در بخش 1 ذکر شد، کاربر به دنبال رستوران است. سرعت حرکت او قابل توجه است نه خیلی سریع. بنابراین، نتایج خط آسمان در آخرین لحظه می تواند برای پردازش پرس و جوهای خط آسمان لحظه بعدی استفاده شود. در غیر این صورت، اگر سرعت خیلی سریع باشد یا فاصله زمانی آنقدر زیاد باشد که نتایج خط آسمان در آخرین مرحله زمانی همه در لحظه بعد تغییر کند، ما ترجیح می‌دهیم از پرس‌وجوهای افق تصویر فوری برای این موقعیت استفاده کنیم. برای مثال‌های انگیزشی، اینها اتفاق نمی‌افتد. بنابراین، در این مقاله، ما فرض می‌کنیم که نقاط پرس و جو خیلی سریع حرکت نمی‌کنند و نتایج خط آسمان در آخرین لحظه می‌توانند برای پردازش پرس و جو مرحله بعدی استفاده شوند. برای مشکل، می‌توانیم از استراتژی‌های ذکر شده در بخش‌های قبلی برای محاسبه تقاطع‌هایی که ممکن است بر خط آسمان تأثیر بگذارند و نتایج خط آسمان را به صورت تدریجی حفظ کنیم، استفاده کنیم.

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

نتیجه 1.

فرض کنید که فواصل نقاط افق

s_{i}

s_{j}

، و

s_{k}

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

s_{i}

s_{k}

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

s_{i}

s_{j}

، و

s_{k}

اثبات

فرض کن که

s_{i}

s_{j}

در زمان قطع می شوند

t_{x}

s_{j}

s_{k}

، و

s_{i}

s_{k}

در زمان قطع می شوند

t_{y}

t_{z}

، به ترتیب. قبل از تقاطع، ما این را می دانیم

s_{i} <_{d i s t} s_{j} <_{d i s t} s_{k}

و ما فقط باید این را ثابت کنیم

t_{z}

باید دیرتر از

t_{x}

t_{y}

. حالا فرض کنید که

t_{z}

زودتر از

t_{x}

یا

t_{y}

. بنابراین، پس از زمان

t_{z}

s_{k} <_{d i s t} s_{i}

. علاوه بر این،

s_{i} <_{d i s t} s_{j}

هنوز معتبر است زیرا هیچ تقاطعی بین هر دو نقطه مجاور اتفاق نمی افتد، که در تضاد است

s_{k} <_{d i s t} s_{i}

. از این رو،

t_{z}

باید دیرتر از

t_{x}

t_{y}

. ☐

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

5.2. ساختار و شرایط داده

ما از یک لیست پیوندی دو طرفه استفاده می کنیم (سایر ساختارهای داده مشابه، مانند پشته و آرایه نیز خوب هستند، زیرا این ساختارها را پردازش می کنیم نه “آنلاین”؛ در عوض، آنها می توانند در بازه زمانی دو مرحله زمانی پردازش شوند) به نام

L L

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

s_{i}

که در

L L

به عنوان مشخص می شود

(f l a g, d i s t, t_{v a l i d}, t_{s k i p})

f l a g

نشان می دهد که آیا

s_{i}

متعلق به

S_{s t a}

d i s t

فاصله بین است

s_{i}

و نقطه پرس و جو q

t_{v a l i d}

زمان اعتبار است

s_{i}

، که فقط برای هر نقطه افق در حال تغییر و ضبط زمان در دسترس است

s_{i}

تحت سلطه است و

t_{s k i p}

زمان است

s_{i}

موقعیت خود را با جانشین خود در

L L

(برای جزئیات بیشتر به الگوریتم های زیر مراجعه کنید).

با قضیه 2، دو موقعیت وجود دارد که ممکن است باعث تغییر خط آسمان شود. زمان تقاطع را فرض کنید

t_{i n s e c}

(

τ = 0.5

قبل از زمان $t_{i n s e c}$ ، $s_{i}$ یک نقطه افق در حال تغییر است. $s_{j}$ از نقطه پرس و جو دورتر از q است $s_{i}$ ، و $s_{j}$ مسلط است $s_{i}$ در تمام ابعاد استاتیک پس از $t_{i n s e c}$ ، $s_{i}$ تحت سلطه خواهد بود $s_{j}$ و خط افق را ترک کنید.
قبل از زمان $t_{i n s e c}$ ، $s_{i}$ نقطه افق است، و $s_{n}$ یک نقطه غیر افق است. پس از $t_{i n s e c}$ ، $s_{n}$ بسته به اینکه آیا می تواند وارد خط افق شود $s_{i}$ نقطه افق منحصر به فردی است که بر آن مسلط است.

برای خلاصه کردن تحلیل فوق، فقط باید مواردی را در نظر بگیریم که ممکن است باعث تغییر خط افق شود. برای سادگی، این مقاله دو فرض را در آستانه τ ایجاد کرده است :

عمود بر عمود بر $p_{i} p_{j}$ در مدل حرکت افزایشی از مرکز توپ عبور می کند، بنابراین $θ = 90^{\circ}$ ، می توانیم از لمای 1 نتیجه بگیریم که:

$پ r (پ من < د من تی_پ j) = 2 θ - sin ( 2 θ ) 2 π = 0.5$

برای $τ = 0.5$ ، قبل از زمان $t_{2}$ ، $p_{j} ≺_{d i s t} p_{i}$ ، و بعد از آن $p_{i} ≺_{d i s t} p_{j}$ (همانطور که در شکل 8 نشان داده شده است ).
فرض کنید که عمود بر عمود بر $p_{i} p_{j}$ از نقطه C عبور می کند که 1/4 قطر است ( شکل 4 را ببینید ). یعنی $| q C | = 1 / 2 | q A |$ . از این رو، $\cos θ = 0.5$ ، و $θ = 60^{\circ}$ ; می توانیم از لم 1 بدست آوریم که:

$پ r (پ من < د من تی_پ j) = 2 θ - sin ( 2 θ ) 2 π = 1 3 - 3 - \sqrt 4 π$

برای راحتی محاسبه، ما تنظیم می کنیم $P r (p_{i} <_{d i s t} p_{j}) = τ$ .

قضیه 3.

همانطور که در شکل 8 نشان داده شده است ، فرض کنید که مختصات موقعیت

p_{1}

p_{2}

هستند

(x_{1}, y_{1})

(x_{2}, y_{2})

. نقطه پرس و جو از شروع می شود

(x_{q}, y_{q})

با سرعت

v (v_{x}, v_{y})

، سپس زمان تقاطع را می توان به صورت زیر ارائه کرد:

1 .: $τ = 0.5$ ، $t = \frac{y_{q} - k x_{q} - C}{k v_{x} - v_{y}}$
2 .: $τ = \frac{1}{3} - \frac{\sqrt{3}}{4 π}$ ، زمان تقاطع هستند $t_{2}$ و $t_{4}$ ، $t_{2}$ و $t_{4}$ را می توان به صورت زیر ارائه کرد: $t_{2} = \frac{k x_{q} - y_{q} + C}{δ | v | \sqrt{k^{2} + 1} - k v_{x} + v_{y}}$ ، $t_{4} = - \frac{k x q - y q + C}{δ | v | \sqrt{k^{2} + 1} + k v_{x} - v_{y}}$ جایی که $k = \frac{x_{1} - x_{2}}{y_{2} - y_{1}}$ ، $C = \frac{y_{1} + y_{2}}{2} - k \frac{x_{1} + x_{2}}{2}$ .

اثبات

مختصات از

p_{1}

p_{2}

هستند

(x_{1}, y_{1})

(x_{2}, y_{2})

، عمود بر عمود بر

p_{1} p_{2}

که با L نشان داده می شود را می توان به صورت زیر نوشت:

y - \frac{y_{1} + y_{2}}{2} = \frac{x_{1} - x_{2}}{y_{2} - y_{1}} (x - \frac{x_{1} + x_{2}}{2})

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

\frac{x_{1} - x_{2}}{y_{2} - y_{1}} x - y + (\frac{y_{1} + y_{2}}{2} - \frac{x_{1} - x_{2}}{y_{2} - y_{1}} \frac{x_{1} + x_{2}}{2}) = 0

. اجازه دهید

k = \frac{x_{1} - x_{2}}{y_{2} - y_{1}}

C = \frac{y_{1} + y_{2}}{2} - k \frac{x_{1} + x_{2}}{2}

اگر $τ = 0.5$ ، ما فقط باید محاسبه کنیم که نقطه پرس و جو با عمود بر عمود بر چه زمانی ملاقات می کند $p_{1} p_{2}$ ; یعنی لحظه $p_{1}$ و $p_{2}$ برابر است با فاصله تا نقطه پرس و جو: ${(x_{q} + t v_{x} - x_{1})}^{2} + {(y_{q} + t v_{y} - y_{1})}^{2} = {(x_{q} + t v_{x} - x_{2})}^{2} + {(y_{q} + t v_{y} - y_{2})}^{2}$ ، سپس $t = \frac{y_{q} - k x_{q} - C}{k v_{x} - v_{y}}$
اگر $τ = \frac{1}{3} - \frac{\sqrt{3}}{4 π}$ ، در زمان $t_{2}$ و $t_{4}$ ، نقطه پرس و جو شرط 1/4 قطر را برآورده می کند ( شکل 4 را ببینید ) ، زمان $t_{1}$ و $t_{5}$ گشتاورهای مماسی عمود بر عمود و کران توپ در مدل حرکت افزایشی هستند. ما زمان را استخراج می کنیم $t_{4}$ از طريق $t_{3}$ و $t_{5}$ ; $t_{2}$ مشابه است. سرعت عمودی عمود بر عمود نشان داده می شود $v_{⊥}$ . در زمان $t_{5}$ ، فاصله از نقطه پرس و جو تا L برابر است با شعاع فعلی توپ در مدل حرکت، بنابراین ما داریم $\frac{| k (x_{q} + v_{x} t_{5}) - (y_{q} + v_{y} t_{5}) + C |}{\sqrt{k^{2} + 1}} = δ | v | t_{5}$ . طبق (1) $t_{3} = \frac{y_{q} - k x_{q} - C}{k v_{x} - v_{y}}$ ، سپس $v_{⊥}$ را می توان به دست آورد $v_{⊥} = \frac{δ | v | t_{5}}{t_{5} - t_{3}}$ . بنابراین، از $t_{3}$ به $t_{4}$ ، فاصله در جهت تغییر می کند $v_{⊥}$ برابر با نصف شعاع است. بنابراین، $v_{⊥} (t_{4} - t_{3}) = \frac{1}{2} δ | v | t_{4}$ .

بر اساس معادلات فوق به عنوان نتیجه گیری $t_{4} = - \frac{k x_{q} - y_{q} + C}{δ | v | \sqrt{k^{2} + 1} + k v_{x} - v_{y}}$ . به همین ترتیب، $t_{2} = \frac{k x_{q} - y_{q} + C}{δ | v | \sqrt{k^{2} + 1} - k v_{x} + v_{y}}$ . ☐

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

رویداد $e x i t$ . این زمانی اتفاق می‌افتد که هر نقطه افق خط افق را ترک کند، که فقط برای یک خط افق فرار اتفاق می‌افتد. فرض کن که $s_{i} \in S_{c h g}$ ، و نقطه افق دیگری وجود دارد $s_{j}$ با پتانسیل تسلط $s_{i}$ ، سپس اگر $s_{i}$ تلاقی می کند با $s_{j}$ در فاصله و $P r (s_{j} <_{d i s t} s_{i}) > τ$ ، $s_{i}$ خط افق را ترک خواهد کرد. یعنی یک $e x i t$ رویداد اتفاق می افتد
رویداد $i n$ . این زمانی اتفاق می افتد که هر نقطه غیر افقی وارد خط افق شود. برای یک نقطه غیر افق $s_{n}$ و تمام آن نقاط خط افق که در حال حاضر بر آن مسلط هستند، اگر $s_{n}$ به نقطه پرس و جو q نزدیکتر می شود تا نقطه افق $s_{i}$ ، $s_{i}$ دیگر نمی تواند بر آن مسلط شود. یعنی یک $i n$ رویداد اتفاق می افتد با این حال، اینکه آیا آن را به خط افق وارد خواهد شد بستگی به این دارد $s_{i}$ تنها کسی است که بر آن تسلط دارد. هنگامی که رویدادی از این نوع در حال پردازش است، این مورد بررسی می شود.
رویداد $c h g_{o r d}$ . این زمانی اتفاق می‌افتد که چند نقطه افق به داخل می‌رسند $L L$ یک تغییر متوالی ایجاد کنید برای نقطه افق $s_{i}$ ، اگر با جانشین خود تلاقی داشته باشد $s_{j}$ و $s_{j}$ نمی توان بر آن مسلط شد، $s_{i}$ و $s_{j}$ تبادل موقعیت در $L L$ ; یعنی الف $c h g_{o r d}$ رویداد اتفاق می افتد توجه کنید که $s_{j}$ پتانسیل تسلط را ندارد $s_{i}$ ; در غیر این صورت، یک $e x i t$ رویداد به جای آن اتفاق خواهد افتاد.

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

{s k_{1}, s k_{2}, s k_{3}, s k_{4}}

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

P r (s k_{3} <_{d i s t} s k_{2}) > τ

s k_{3}

مسلط است

s k_{2}

در تمام ابعاد استاتیک سپس، یک

e x i t

رویداد رخ خواهد داد زیرا

s k_{2}

تحت سلطه خواهد بود و خط افق را ترک می کند ( شکل 9 ب را ببینید). اگر

s_{n}

نقطه افق تحت سلطه است

s k_{3}

منحصر به فرد، در زمان t ، اگر

d i s t (q, s k_{3}) > d i s t (q, s_{n})

، سپس یک

i n

رویداد رخ خواهد داد زیرا

s_{n}

وارد خط افق خواهد شد ( شکل 9 ج را ببینید). علاوه بر این، در زمان t ، اگر

s k_{3}

به نقطه پرس و جو q نزدیکتر می شود

s k_{2}

s k_{3}

پتانسیلی برای تسلط ندارد

s k_{2}

، سپس یک

c h g_{o r d}

رویداد رخ خواهد داد زیرا

s k_{2}

s k_{3}

موقعیت های خود را در لیست مبادله خواهند کرد ( شکل 9 د را ببینید).

یک صف سراسری برای حفظ همه رویدادها برای نمایش تغییرات خط افق آینده استفاده می شود. هر رویداد به شکل

(t i m e, t y p e, s e l f, r e l)

هنگامی که رویداد در زمان اتفاق می افتد

t i m e

، و

t y p e

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

s e l f

r e l

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

e x i t

یا

c h g_{o r d}

رویداد،

s e l f

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

s_{i}

، در حالی که

p e e r

جانشین آن است

s_{j}

. در یک

i n

رویداد،

s e l f

نشان دهنده نقطه افق در حالی است

p e e r

مخفف نقطه غیر افقی مربوطه است

s_{n}

در ابتدا،

L L

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

L L

شامل تمام نقاط خط افق صحیح با توجه به موقعیت فعلی نقطه پرس و جو q است.

5.3. مکانیسم های رویداد محور برای پردازش پرس و جو مستمر

در روش ما برای مجموعه داده های ایستا، از یک فهرست فایل شبکه ای دوبعدی ساده استفاده می کنیم که فضای داده را به

h \times v

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

d_{f a r e s t}

به عنوان یک جستجو محدود، و سلول های فراتر از آن

d_{f a r e s t}

برای کاهش ورودی/خروجی ها هرس می شوند ( شکل 10 را ببینید ).

همانطور که در الگوریتم 1 نشان داده شده است، در ابتدا، تمام نقاط خط افق دائمی در داخل هستند

S_{s t a}

درج می شوند

L L

بر اساس فاصله آنها تا موقعیت شروع نقطه پرس و جو q . ابتدا مجموعه داده را با استفاده از ویژگی های هندسی هرس می کنیم. سپس، با شروع از سلولی که موقعیت اولیه q در آن قرار دارد، تمام سلول‌های شبکه به صورت مارپیچی جستجو می‌شوند به طوری که آنهایی که در یک دایره اطراف درونی قرار دارند قبل از سلول‌های روی یک دایره بیرونی جستجو می‌شوند، همانطور که در شکل 10 نشان داده شده است . سپس مجموعه داده ها را بر اساس لم 3، 4، 5 با ساختار پشته سازماندهی می کنیم. پشته H برای ذخیره سلول ها یا نقاط داده ای استفاده می شود که امکان ورود به خط آسمان وجود دارد، که بالای آن سلول یا نقطه داده ای است که نزدیک ترین نقطه به موقعیت تخمینی q است . نقاط یا سلول ها در پشته به ترتیب با نقاط خط افق فعلی در مقایسه می شوند

L L

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

L L

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

i n

رویدادها برای نقاط دورتر از آن.

الگوریتم 1: مقداردهی اولیه

الگوریتم 2 روند CreateEvents را با جزئیات نشان داده است. برای یک نقطه افق مشخص

s_{i}

، الگوریتم ابتدا زمان t را محاسبه می کند

s_{i}

و نقطه افق بعدی

s_{j}

که در

L L

موقعیت های خود را در لیستی که

s_{j}

مسلط خواهد شد

s_{i}

در فاصله اگر t دیرتر از

s_{j}

زمان مبادله یا

s_{i}

زمان اعتبار، نادیده گرفته می شود. در غیر این صورت، به معنای یک

e x i t

رویداد بسته به

s_{j}

زمان اعتبار اگر

s_{i} \in S_{c h g}

، یا ساده است

c h g_{o r d}

رویداد. سپس محاسبه کنید

i n

رویدادها برای هر نقطه غیر افقی

s_{n}

که فاصله تا موقعیت تخمینی q در مقایسه با

s_{i}

s_{j}

فاصله ها

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

L L

خط افق صحیح نقطه زمانی فعلی هستند.

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

s_{i}

از لیست افق حذف می شود

L L

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

i n

رویداد، نقطه غیر افق

s_{n}

بررسی خواهد شد تا ببینیم که آیا منحصر به فرد است یا خیر

s_{i}

. اگر بله،

s_{n}

در لیست افق درج خواهد شد

L L

و رویدادهای جدید برای نقاط مرتبط محاسبه می شوند. در غیر این صورت، احتمال جدید است

i n

رویداد محاسبه و در صف قرار می گیرد. برای یک

c h g_{o r d}

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

s_{i}

s_{j}

. به همین ترتیب، رویدادهای مرتبط برای آنها و پیشینیان در صورت وجود ایجاد و در صف قرار می گیرند.

الگوریتم 2: CreateEvents

الگوریتم 3: رویداد ناشی از فرآیند

6. استراتژی های هرس برای الگوهای حرکتی خاص

استراتژی های هرس هندسی را می توان به راحتی در مسیرهای متحرک شناخته شده ادغام کرد تا تعداد نقاط داده را کاهش دهد. در این بخش، ما استراتژی‌های هرس هندسی را تحت مدل حرکت افزایشی برای سه کلاس مختلف از مسیرها ارائه می‌کنیم: محصور، محدود، و نامحدود. در صورتی که حرکت یا بخشی از مرز محدوده متحرک یک نقطه پرس و جو مشخص باشد، اگر موقعیت نقطه اکنون واجد شرایط ایجاد یک مدل حرکت افزایشی نباشد، فرض می کنیم که یک “نقطه پرس و جو مجازی” در جایی وجود دارد. گذشته، و توانست در مدل افزایشی اعمال شود. علاوه بر این، حرکت نقطه پرس و جو واقعی – اگرچه با مدل حرکت افزایشی سازگار نیست – در منطقه تخمینی مدل حرکت افزایشی تنظیم شده توسط نقطه پرس و جو مجازی باقی می ماند.

الگوهای حرکت محصور شده اگر حرکت نقطه پرس و جو q یک منحنی محصور باشد، نقطه پرس و جو در ناحیه محصور شده توسط منحنی باقی می ماند. شکل 11 a-c سه الگوی حرکت محصور معمولی است: دایره ، بیضی و سهمی . در این صورت با وجود قبا سرعت حرکت، نقطه در امتداد منحنی حرکت می کند و به طور مکرر بر خط افق تأثیر می گذارد. با در نظر گرفتن ویژگی های منحنی های محصور، می توان کران های بالایی و پایینی دقیق را در تمام جهات یک نقطه پرس و جو به دست آورد. بر اساس تمام منحنی‌های بالا، می‌توانیم مدل‌های حرکت افزایشی را در جهات مختلف ایجاد کنیم تا یک سری نقاط پرس و جو مجازی به دست آوریم. پس از آن، الگوریتم هرس هندسی به صورت مکرر اجرا می شود و بسیاری از نقاط اضافی را که هیچ تأثیری بر خط افق ندارند فیلتر می کند.

الگوهای حرکتی با کران اگر حرکت یک نقطه پرس و جو q منحنی با کران باشد، به این معنی است که می توانیم کران های بالایی و پایینی آن را در یک یا چند جهت بدست آوریم، در حالی که بقیه هیچ مرزی ندارند یا قابل پیش بینی نیستند ( Sinusoid and Spiral دو مورد از این نوع الگوی حرکتی، همانطور که در شکل 11 نشان داده شده استد، ه). با توجه به ویژگی این منحنی‌ها، ما همچنان می‌توانیم از موقعیت شروع نقطه پرس و جو و جهت‌هایی که کرانه‌ها را می‌توان برای ایجاد یک مدل حرکت افزایشی، به‌دست آوردن یک نقطه مجازی و اعمال استراتژی‌های هرس هندسی استفاده کرد. اساساً، اگرچه اثر فیلتر کردن به اندازه وضعیت الگوهای محصور کارآمد نیست، اما در مقایسه با پرس‌وجوهای خط افق عکس فوری ارزش اجرا دارد.

الگوهای حرکتی بدون کران اگر حرکت نقطه پرس و جو q منحنی بدون کران باشد، در هر جهت نمی توان حدی به دست آورد و استفاده از استراتژی های هرس هندسی بر اساس مدل حرکت افزایشی غیرممکن است (نمونه هایی از این نوع الگوی حرکتی هلو و مارپیچ ارشمیدسی در شکل 11 f , g).

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

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

(آ)

یک کران بالا یا پایین در برخی جهت ها وجود دارد.

(ب)

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

(ج)

زاویه بین جفت خطوط مماس خواسته های چارچوب هرس هندسی را برآورده می کند.
هیچ مرزی در همه جهات وجود ندارد یا نمی تواند یک جفت خط مماس واجد شرایط را در (1) به دست آورد. در این مورد، نمی‌توانیم استراتژی‌های هرس هندسی را مستقیماً اتخاذ کنیم. سپس، باید ویژگی‌های منحنی‌ها را در نظر بگیریم و با افزودن محدودیت‌های اضافی، آن را با چارچوب تطبیق دهیم.

7. آزمایشات

A n

\ddot{a}

رویکرد اصلی برای نظارت بر خطوط آسمان متحرک، فراخوانی الگوریتم‌های موجود مانند I/O BBS بهینه [ 3 ، 4 ] برای محاسبه مجدد خط افق هر زمان که نتایج نیاز به به‌روزرسانی دارند، است. در این بخش n را با هم مقایسه می کنیم

\ddot{a}

الگوریتم‌های ive به روش‌های پیشنهادی در برابر عوامل مختلفی که ممکن است عملکرد الگوریتم‌ها را تحت تأثیر قرار دهند. همه الگوریتم ها در C++ استاندارد با پشتیبانی از کتابخانه STL پیاده سازی شده و با GNU GCC 4.9.3 کامپایل شده اند. آزمایش‌ها روی رایانه شخصی با پردازنده دوگانه Intel Core i3-3240 3.40GHz و حافظه 4G با Ubuntu Linux 14.04 LTS اجرا شد. اندازه صفحه دیسک به 4096 بایت ثابت شد.

برای تولید مجموعه داده‌ها برای آزمایش‌ها، ابتدا نکات جالب کالیفرنیا را از وب‌سایت [ 28 ] دریافت کردیم ( شکل 12 را ببینید)، سپس مکان‌های واقعی را با ابعاد غیرمکانی به دنبال توزیع‌های مختلف ترکیب کردیم: مستقل، همبسته، ضد همبسته، و Zipf. اندازه داده‌های مکان‌های واقعی کالیفرنیا حدود 100 K است و ما ابعاد غیرمکانی مانند آن را در مرجع [ 1 ] تولید می‌کنیم. مقدار مشخصه یک نقطه داده از 1 تا 1000 متغیر بود. زمان CPU و شمارش ورودی/خروجی برای اندازه‌گیری کارایی الگوریتم‌ها در زیر 100 اجرای پرس‌وجوهای خط آسمان استفاده شد. پارامترهای مورد استفاده در آزمایشات در جدول 3 فهرست شده است. به طور خاص، الگوریتم های زیر مورد ارزیابی قرار گرفتند:

پرس و جو خط افق پیوسته (CSQ): روش افق پیوسته مبتنی بر مدل افزایشی که الگوریتم ردیابی تغییر خط افق را در مرجع [ 5 ] مستقیماً بدون استفاده از استراتژی‌های هرس هندسی انجام می‌دهد.
GP-CSQ: روشی که الگوریتم ردیابی تغییر خط آسمان را با استراتژی‌های هرس هندسی تنها با استفاده از Lemma 3 (Lmma 4، پسوند آن) انجام می‌دهد.
GP2-CSQ: نمونه‌ای از روشی که الگوریتم ردیابی تغییر خط افق را انجام می‌دهد همراه با استراتژی‌های هرس هندسی با استفاده از لم 3 (لم 4) و 5.

از آنجایی که الگوریتم BBS کارآمدترین روش برای محاسبه خط آسمان در تنظیمات استاتیک است (هم نقاط داده و هم نقطه پرس و جو ایستا هستند)، ما آن را برای مقایسه در آزمایش‌ها اتخاذ کردیم. هنگامی که مکان نقطه پرس و جو تغییر کرد، ما فقط ” ذهن شناس ” را برای تطبیق الگوریتم اصلی BBS تغییر دادیم (به [ 4 ] مراجعه کنید). علاوه بر این، ما همچنین از روشی که در [ 5 ] “ex-BBS” نامیده می‌شود، برای تضاد با روش‌های پیشنهادی خود استفاده کردیم.

تأثیر کاردینالیته. برای تولید مجموعه‌های داده با اندازه‌های مختلف، بخشی از مکان‌های واقعی را به‌طور تصادفی انتخاب کردیم و سپس با دو بعد غیرفضایی مصنوعی ترکیب کردیم. بنابراین، ما اندازه مجموعه داده‌ها را از 10 K به 100 K تبدیل کردیم. سپس، 100 (10 برای ضد همبستگی) پرس‌وجوهای خط آسمان پیوسته را روی مجموعه داده‌ها اجرا کردیم. برای هر پرس و جو، ما موقعیت شروع نقطه پرس و جو را به صورت (37

^{\circ}

N، -120

^{\circ}

W). سرعت پیش‌فرض نقطه پرس و جو (1، -1) بود، در حالی که جهت حرکت همان بردار (1، -1) بود. آستانه 0.5 ثابت شد.

در شکل 13 ، هزینه CPU الگوریتم CSQ اصلی در برخی موارد بیشتر از الگوریتم های BBS است، زیرا CSQ نه تنها اشیاء غیر خط آسمان را پردازش می کند، بلکه رویدادهای اولیه را برای حفظ خط آسمان در آینده محاسبه می کند. GP-CSQ و GP2-CSQ به طور کلی سریع‌تر بودند، زیرا سیاست‌های هرس هندسی می‌توانند تعداد زیادی از نقاط داده غیرمجاز را فیلتر کنند و هزینه پردازش رویداد را کاهش دهند. توجه داشته باشید که در شکل 13 d، CSQ زمان زیادی می برد و اندازه نتایج خط آسمان بزرگ است زیرا مجموعه داده های ضد همبستگی رخدادهای بیشتری را متحمل می شوند. شکل 14نشان می دهد که با افزایش کاردینالیته، I/Oهای CSQ، GP-CSQ، و GP2-CSQ تقریباً 10٪ کمتر از BBS است، در حالی که GP-CSQ و GP2-CSQ کمی بهتر از الگوریتم CSQ هستند.

اثر ابعاد غیر فضایی. ما از یک مجموعه داده شبکه جاده‌ای 100 K واقعی همراه با ابعاد غیرمکانی از دو تا پنج برای ارزیابی تأثیر ابعاد غیرمکانی بر روش‌های خود استفاده کردیم. مقادیر این ابعاد غیرمکانی از 1 تا 1000 متغیر است. مجموعه پارامترهای دیگر همان است که در جدول 3 نشان داده شده است .

همانطور که در شکل 15 نشان داده شده است ، استراتژی های هرس می توانند در زمان اجرا تا حد معینی صرفه جویی کنند در حالی که از ابعاد غیر مکانی بالاتر پشتیبانی می کنند. در شکل 16 ، الگوریتم‌های CSQ دارای مزیت آشکاری در ورودی/خروجی هستند، زیرا آنها بر روی ویژگی‌های پویا تمرکز می‌کنند در حالی که ویژگی‌های غیرمکانی فقط در بررسی تسلط در نظر گرفته می‌شوند. توجه داشته باشید که کارایی استراتژی‌های هرس هندسی اندکی تحت‌تاثیر قرار گرفته است زیرا تسلط بر یک نقطه داده در ابعاد غیرمکانی بالاتر سخت‌تر است و هرس نقاط داده‌ای بیشتر را تقریبا غیرممکن می‌کند.

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

^{\circ}

N، -125

^{\circ}

W)، (39.5

^{\circ}

N، -122.5

^{\circ}

W)، (37

^{\circ}

N، -120

^{\circ}

W)، (34.5

^{\circ}

N، -117.5

^{\circ}

W)؛ سایر پارامترهای پرس و جو به همان روشی که در آزمایش های قبلی انجام شد، انتخاب شدند. ما عمدتاً با انتخاب چهار موقعیت نماینده بالا برای ارزیابی، تأثیر موقعیت مربوط به کارایی استراتژی‌های هرس را بررسی کردیم. علاوه بر این، ما قصد داشتیم عملکرد کلی استراتژی‌های هرس هندسی را به دست آوریم.

همانطور که در شکل 17 و شکل 18 نشان داده شده است، هزینه ها کاملاً متمایز هستند زیرا کارایی عملیات هرس به وضوح تحت تأثیر موقعیت های نقطه پرس و جو قرار می گیرد. عملیات هرس BBS سابق تقریباً غیرفعال شده بود زیرا یک خط افق دائمی دور از موقعیت پرس و جو وجود دارد. اگر نقطه پرس و جو به مرکز منطقه مکانی نزدیک شود، عملیات هرس BBS سابق به احتمال زیاد خراب می شود. استراتژی‌های هرس هندسی معمولاً در دسترس هستند، مگر در شرایط شدید که در آن نقطه پرس و جو از لبه مکان مکانی شروع می‌شود. علاوه بر این، روش‌های پیشنهادی GP-CSQ و GP2-CSQ می‌توانند بسیاری از نقاط داده غیرمجاز را در برخی موارد خاص که در آن منطقه‌ای که قرار است هرس شود گسترده است (مثلاً در موقعیت (34.5) فیلتر کند.

^{\circ}

N، -117.5

^{\circ}

W)، باعث صرفه جویی در حدود 60٪ – 80٪ در زمان CPU و I/Oها می شود. توجه داشته باشید که در شکل 17 د، هزینه CPU الگوریتم CSQ بسیار بالاتر است زیرا تعداد زیادی رویداد وجود دارد که باید محاسبه شوند و GP-CSQ و GP2-CSQ به دلیل بهینه سازی استراتژی های هرس هندسی به BBS نزدیک می شوند. .

اثر سرعت حرکت در این بخش، آزمایش هایی را اجرا می کنیم که در آن سرعت نقطه پرس و جو از (1،-1) تا (8،-8) متغیر است. ما هنوز از مجموعه داده واقعی 100 K ترکیب شده با دو ویژگی غیرمکانی همبسته، مستقل، ضد همبستگی و zipf استفاده می کنیم.

در شکل 19 و شکل 20 ، بدیهی است که هزینه CSQ با سرعت پرس و جو افزایش می یابد، زیرا فاصله نقاط داده به طور مکرر تلاقی می کند، که به این معنی است که تعداد بیشتری از رویدادها رخ می دهد و نیاز به دفع دارند، بنابراین I/Oهای بیشتری مصرف می شود. و زمان CPU بهینه‌سازی شده توسط استراتژی‌های هرس هندسی پیشنهادی، هزینه ورودی/خروجی GP-CSQ و GP2-CSQ خیلی حساس نیست. با این حال، زمانی که نقطه پرس و جو بسیار سریع حرکت می کند، زمان CPU برای ایجاد و مدیریت رویدادها هنوز خیلی زیاد است. می‌توانیم ببینیم که الگوریتم‌های CSQ، GP-CSQ، و GP2-CSQ در زمینه سرعت حرکت پایین‌تر مناسب‌تر هستند. اگر نقطه پرس و جو با سرعت بالا حرکت می کند، ترجیح می دهیم خط آسمان را از ابتدا محاسبه کنیم. به عنوان مثال، الگوریتم BBS را برای هر مرحله زمانی فراخوانی کنید.

اثر کران خطا. در این بخش، تنظیمات آستانه را از 0.2 به 0.65 در حال اجرا در مجموعه داده شبکه جاده ای کالیفرنیا تغییر می دهیم. آستانه بالاتر به این معنی است که نقاط داده بیشتری می توانند زودتر در خط آسمان قرار بگیرند یا دیرتر از آن خارج شوند. در شکل 21 و شکل 22 ، با گسترده تر شدن آستانه ها، هزینه های CSQ اندکی افزایش می یابد زیرا نقاط بیشتری در خط افق باقی می مانند و رویدادهای بیشتری ایجاد می کنند. به طور کلی، تغییر آستانه تأثیر برجسته ای بر هزینه های روش های GP-CSQ و GP2-CSQ ایجاد نمی کند. به ویژه در شکل 22ج، عملیات هرس بار دوم با استفاده از Lemma 5 به وضوح توسط آستانه گسترده‌تر ضعیف شد، زیرا ناحیه موجود نقاط داده برای هرس بسیار کوچک شد و توزیع باعث شد که نقاط داده غیرمجاز را فیلتر نکند. هزینه CPU زمانی که آستانه برابر با 0.5 بود کمتر بود زیرا فرآیند محاسبه احتمال بررسی تسلط برای سرعت بخشیدن به پردازش ساده شده است.

ارزیابی کارایی چارچوب هرس هندسی. در این بخش، ما اثر چارچوب هرس هندسی را تحت انواع مختلف الگوهای حرکتی (مثلاً، محصور، با کرانه‌ها و بدون کران) مقایسه می‌کنیم تا بررسی کنیم که آیا به اندازه کافی کارآمد و همه‌کاره است یا خیر. برای سادگی، بیضی ، سینوسی و سهمی را به عنوان نماینده سه الگوی حرکت ذکر شده در بالا در نظر می گیریم .

شکل 23 نشان می دهد که با افزایش کاردینالیته هر مجموعه داده، چارچوب هرس هندسی به طور موثر کار می کند. به طور خاص، برای بیضی ، اثر هرس بسیار قوی است زیرا ما می‌توانیم بیشتر نقاط داده را با چند بار فراخوانی الگوریتم هرس هندسی برای یک الگوی حرکت محصور حذف کنیم. به طور خاص، برای بقیه الگوهای حرکت، حدود 60 درصد از نامزدهای اولیه حذف شدند، که هنوز هم می تواند زمان اجرای پرس و جو را به طور چشمگیری کاهش دهد.

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

8. نتیجه گیری

در این مقاله، به پرس و جوهای خط افق پیوسته در نقاط پرس و جو متحرک تحت مدل حرکت افزایشی می پردازیم. از ویژگی های هندسی به طور کامل برای هرس کردن نقاط داده ای که به نتایج نهایی خط آسمان تعلق ندارند، استفاده می شود، بنابراین کارایی پردازش پرس و جو خط افق را بهبود می بخشد. علاوه بر این، مکانیسم‌های مبتنی بر رویداد و یک خط‌مشی هرس مبتنی بر فهرست فایل شبکه‌ای برای حفظ نتایج پیوسته خط آسمان به جای محاسبه نتایج خط افق از ابتدا پیشنهاد شده‌اند. دو الگوریتم کارآمد (GP-CSQ و GP2-CSQ) بر اساس ویژگی‌های هندسی پیشنهاد شده‌اند، و آزمایش‌های گسترده ما نشان داده‌اند که دو الگوریتم مبتنی بر ویژگی هندسی مؤثرتر و کارآمدتر از روش‌های موجود هستند.

مسیرهای آینده امیدوارکننده زیادی وجود دارد. اولاً، الگوهای حرکتی مناسب برای کاربردهای خاص را می‌توان یافت، و می‌توانیم نحوه تغییر استراتژی‌های هرس را بر اساس ویژگی‌های هندسی متناظر برای تطبیق الگوی حرکت جدید تحت چارچوب خود مطالعه کنیم. ثانیاً، از آنجایی که فرض می‌کنیم فقط نقاط پرس و جو و ویژگی‌های نقطه پویا هستند، اگر پایگاه‌های اطلاعاتی تغییر کنند (یعنی نقاط داده متفاوت باشند-درج، به‌روزرسانی یا حذف شوند)، می‌توانیم نحوه توسعه الگوریتم‌های کارآمد برای پاسخگویی به پرس‌وجوهای خط افق مداوم کاربر را مطالعه کنیم. ثالثاً، کار آینده را می توان به بررسی امکان استفاده از استراتژی های هرس هندسی پیشنهادی برای پشتیبانی از انواع دیگر پرس و جوهای خط افق، مانند پرس و جوهای خط آسمان رزرو [24]، مکعب های خط آسمان [ 29 ]، پرس و جوهای خط افق فضایی [29] اختصاص داد.16 ]، خطوط آسمان احتمالی [ 27 ] و غیره. در حالی که نتایج به‌دست‌آمده از آزمایش‌های جامع نشان‌دهنده برتری رویکردهای ما بر اساس استراتژی‌های هرس هندسی نسبت به کارهای موجود است، ما معتقدیم که این ویژگی‌های هندسی کاوش‌شده و چارچوب پیشنهادی برای دیگر انواع پرس‌وجوی خط افق که در این مقاله بررسی نشده‌اند، مفید هستند. مشکل جالب دیگر گسترش استراتژی‌های هرس هندسی به سایر کاربردهای واقعی است (به عنوان مثال، سیستم‌های توصیه [ 30 ]، شبکه‌های حسگر سیار [ 31 ، 32 ]، و سیستم‌های نظارت [ 33]]) به این صورت که هر زمان که یک نقطه پرس و جو قرار گیرد، پس از انجام یک پرس و جو فوری، با استفاده از استراتژی های هرس هندسی پیشنهادی یا سایر گسترش ها، می توانیم بخش کوچکی از نامزدها را که ممکن است در آینده نزدیک بر نتیجه پرس و جو تأثیر بگذارند، بدون تأیید همه به دست آوریم. نقاط داده در سیستم به طوری که نتایج پرس و جو را می توان به طور موثر با توجه به مجموعه داده های نامزد در مقیاس کوچک حفظ کرد.

اختصارات

در این نسخه از اختصارات زیر استفاده شده است:

BNL	حلقه تودرتو را مسدود کنید
SFC	مرتب سازی خط افق فیلتر
NN	نزدیکترین همسایه
نماینده مجلس	پردازنده حرکتی
من هستم	حرکت افزایشی
PWS	ایمان شناسی احتمالی جهان
LBS	خدمات مبتنی بر مکان
KDS	ساختار داده های جنبشی
BBS	خط افق شاخه ای و محدود
CSQ	پرس و جو مستمر خط افق
GP	هرس هندسی

منابع

برزسونی، اس. کوسمن، دی. Stocker، K. اپراتور Skyline. در دسترس آنلاین: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.2504 (در 21 مارس 2017 قابل دسترسی است).
چامیکی، جی. سیاکیا، پی. منگتی، پرس و جوهای N. Skyline، جلو و عقب. SIGMOD Rec. 2013 ، 42 ، 6-18. [ Google Scholar ] [ CrossRef ]
پاپادیاس، دی. تائو، ی. فو، جی. Seeger, B. یک الگوریتم بهینه و پیشرو برای پرس و جوهای خط آسمان. در مجموعه مقالات SIGMOD 2003، سن دیگو، کالیفرنیا، ایالات متحده آمریکا، 9 تا 12 ژوئن 2003.
پاپادیاس، دی. تائو، ی. فو، جی. محاسبات خط افق پیشرونده در سیستم های پایگاه داده. TODS 2005 ، 30 ، 41-82. [ Google Scholar ] [ CrossRef ]
هوانگ، ز. لو، اچ. Ooi، BC; Tung, AKH Queries Continuous Skyline for Moving Objects. TKDE 2006 ، 18 ، 1645-1658. [ Google Scholar ]
لین، ایکس. خو، جی. Hu, H. جستجوهای خط افق مبتنی بر محدوده در محیط های موبایل. ICDE 2013 ، 25 ، 835-849. [ Google Scholar ] [ CrossRef ]
گوا، ایکس. ژنگ، بی. ایشیکاوا، ی. Gao, Y. جستجوهای فراگیر مبتنی بر جهت برای توصیه های موبایل. VLDB J. 2011 ، 20 ، 743-766. [ Google Scholar ] [ CrossRef ]
کیائو، ز. گو، ج. لین، ایکس. Chen, J. Privacy-Preserving Skyline Queries در LBS. در مجموعه مقالات کنفرانس بین المللی 2010 در مورد بینایی ماشین و رابط انسان و ماشین، کایفنگ، چین، 24-25 آوریل 2010.
باش، جی. Guibas، LJ; هرشبرگر، جی. ساختارهای داده برای داده های تلفن همراه. در مجموعه مقالات SODA ’97، نیواورلئان، لس آنجلس، ایالات متحده آمریکا، 5-7 ژانویه 1997.
باش، جی. Guibas، LJ; هرشبرگر، جی. ساختارهای داده برای داده های تلفن همراه. J. Algorithms 1999 ، 31 ، 1-28. [ Google Scholar ] [ CrossRef ]
قهوهای مایل به زرد، KL; Eng, PK; Beng، محاسبه خط افق پیشرونده کارآمد CO. در دسترس آنلاین: http://www.vldb.org/conf/2001/P301.pdf (در 21 مارس 2017 قابل دسترسی است).
چامیکی، جی. گادفری، پی. Gryz، J. Skyline با Presorting. در دسترس آنلاین: http://ieeexplore.ieee.org/document/1260846/ (در 21 مارس 2017 قابل دسترسی است).
گادفری، پی. شیپلی، آر. گرایز، جی. محاسبات برداری حداکثر در مجموعه داده های بزرگ. در مجموعه مقالات سی و یکمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تروندهایم، نروژ، 30 اوت تا 2 سپتامبر 2005.
کوسمن، دی. رامسک، ف. Rost, S. Shooting Stars in the Sky: یک الگوریتم آنلاین برای پرس و جوهای خط افق. در مجموعه مقالات VLDB ’02، هنگ کنگ، چین، 20-23 اوت 2002.
شیلنگ، K. Vlachou، A. بررسی پردازش خط افق در محیط های بسیار پراکنده. VLDB J. 2012 ، 21 ، 359-384. [ Google Scholar ] [ CrossRef ]
شریف زاده، م. شهابی، ج. پرسش های خط آسمان فضایی. در مجموعه مقالات VLDB ’06، سئول، کره، 12 تا 15 سپتامبر 2006.
دنگ، ک. ژو، ایکس. شن، HT چند منبع پردازش پرس و جو خط آسمان در شبکه های جاده ای. در مجموعه مقالات ICDE ’07، استانبول، ترکیه، 15-20 آوریل 2007.
کوه، DM; نتانیاهو، NS; پیاتکو، سی دی; سیلورمن، آر. وو، AY یک چارچوب محاسباتی برای حرکت افزایشی. در مجموعه مقالات SCG ’04، بروکلین، نیویورک، ایالات متحده آمریکا، 8 تا 11 ژوئن 2004.
چو، م. کوه، دی. پارک، E. نگهداری شبکه ها و درختان شبکه تحت حرکت افزایشی. در الگوریتم ها و محاسبات ; Springer: برلین، آلمان، 2009; صص 1134-1143. [ Google Scholar ]
لی، مگاوات؛ Hwang، SW Continuous Skylining on Volatile Moving Data. در مجموعه مقالات ICDE ’09، شانگهای، چین، 29 مارس تا 2 آوریل 2009.
هسوه، ی. Hascoet, T. Caching پشتیبانی برای پردازش پرس و جوی Skyline با دامنه های جزئی مرتب شده. TKDE 2014 ، 26 ، 2649–2661. [ Google Scholar ] [ CrossRef ]
Cheema، MA; لین، ایکس. ژانگ، دبلیو. ژانگ، ی. یک رویکرد مبتنی بر منطقه امن برای نظارت بر پرس و جوهای خط افق متحرک. در مجموعه مقالات EDBT 2013، بروکسل، بلژیک، 23 تا 27 مارس 2013.
وو، ک. ژنگ، R. الگوریتم های کارآمد برای پرس و جو خط افق فضایی با عدم قطعیت. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، اورلاندو، فلوریدا، ایالات متحده آمریکا، 5 تا 8 نوامبر 2013.
دلیس، ای. سیگر، ب. محاسبه کارآمد پرس و جوهای خط آسمان معکوس. در مجموعه مقالات سی و سومین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، وین، اتریش، 23 تا 28 سپتامبر 2007.
ساچاریدیس، دی. بوروس، پ. سلیس، T. ذخیره پرس و جوهای خط افق پویا. در مجموعه مقالات بیستمین کنفرانس بین المللی مدیریت پایگاه داده های علمی و آماری، هنگ کنگ، چین، 9 تا 11 ژوئیه 2008.
مورتنسن، ام‌ال. چستر، اس. موافقت، I.; Magnani، M. ذخیره کارآمد برای پرس و جوهای خط افق محدود. در مجموعه مقالات EDBT ’15، بروکسل، بلژیک، 23 تا 27 مارس 2015.
پی، جی. جیانگ، بی. لین، ایکس. یوان، Y. خطوط آسمان احتمالی در داده های نامشخص. در مجموعه مقالات سی و سومین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، وین، اتریش، 23 تا 28 سپتامبر 2007.
فیفی، ل. مجموعه داده های فضایی. در دسترس آنلاین: https://www.cs.utah.edu/lifeifei/SpatialDataset.html (در 21 مارس 2017 قابل دسترسی است).
یوان، ی. لین، ایکس. لیو، کیو. وانگ، دبلیو. یو، JX; ژانگ، Q. محاسبه کارآمد مکعب خط آسمان. در مجموعه مقالات سی و یکمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تروندهایم، نروژ، 30 اوت تا 2 سپتامبر 2005.
Pazzani, MJ; Billsus, D. سیستم های توصیه مبتنی بر محتوا. در وب تطبیقی: روش ها و استراتژی های شخصی سازی وب . Brusilovsky, P., Kobsa, A., Nejdl, W., Eds.; Springer: برلین، آلمان، 2007; صص 325-341. [ Google Scholar ]
سیونزو، دی. بوونانو، آ. D’Urso, M. طبقه بندی توزیع شده اهداف متحرک چندگانه با شبکه های حسگر بی سیم باینری. در مجموعه مقالات FUSION ’11، شیکاگو، IL، ایالات متحده آمریکا، 5-8 ژوئیه 2011.
بوونانو، آ. D’Urso، M. Prisco، G. شبکه های حسگر موبایل مبتنی بر سیستم عامل های مستقل برای امنیت داخلی. در مجموعه مقالات پیشرفت در رادار و سنجش از دور (TyWRRS)، ناپل، ایتالیا، 12-14 سپتامبر 2012.
تسیلیکاریدیس، تی. Sadler، BM; Hero، AO در تخمین غیرمتمرکز با جستارهای فعال. IEEE Trans. فرآیند سیگنال 2015 ، 63 ، 2610-2622. [ Google Scholar ] [ CrossRef ]

شکل 1. مسیرهایی برای یافتن رستوران در حین حرکت.

شکل 2. پردازنده افق پیوسته.

شکل 3. مدل حرکت افزایشی (IM). ( الف ) مرزهای خطا. ( ب ) تخمین مکان.

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

شکل 5. هرس تحت مدل IM.

شکل 6. هرس پیچیده. ( الف )

D_{1}

تحت سلطه است؛ ( ب )

D_{2}

تحت سلطه است.

شکل 7. هرس با پیش بینی.

شکل 8. تغییر تسلط فاصله برای دو نقطه داده.

شکل 9. پردازش برای سه رویداد. ( الف ) توالی رویداد اصلی؛ ( ب ) رویداد خروج ؛ ج ) در صورت وقوع ؛ ( د ) تغییر رویداد.

شکل 10. هرس با فهرست فایل شبکه.

شکل 11. الگوهای حرکت: ( الف – ج ) محصور شده. ( d , e ) محدود شده; ( f , g ) نامحدود.

شکل 12. نقاط مورد علاقه کالیفرنیا (نقاط دایره و ستاره نشان دهنده موقعیت های شروع هستند).

شکل 13. اثر کاردینالیته (زمان CPU). BBS: خط افق شاخه و محدود. CSQ: پرس و جو خط افق پیوسته. GP-CSQ: CSQ با هرس هندسی. GP2-CSQ: CSQ با استفاده از هرس هندسی از Lemmas 3، 4، 5. ( a ) Independent; ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 14. اثر کاردینالیته (I/O). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 15. اثر ابعاد غیر مکانی (زمان CPU). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 16. اثر ابعاد غیر فضایی (I/O). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 17. اثر موقعیت شروع (زمان CPU). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 18. اثر موقعیت شروع (I/O). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 19. اثر سرعت حرکت (زمان CPU). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 20. اثر سرعت حرکت (I/O). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 21. اثر کران خطا (زمان CPU). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 22. اثر کران خطا (I/O). ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 23. اثر کاردینالیته. ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

شکل 24. اثر ابعاد غیر فضایی. ( الف ) مستقل؛ ( ب ) همبسته؛ ( ج ) ضد همبستگی; ( د ) Zipf.

جدول 1. خلاصه نمادها.

جدول 2. امکان تقاطع دو نقطه داده.

جدول 3. پارامتر و محدوده (مقدار پیش فرض

^{*}

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

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

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

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

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

3. مقدمات

3.1. تعریف مشکل

3.2. مدل حرکت افزایشی

3.2.1. موقعیت نقطه پرس و جو

3.2.2. تابع فاصله پارامتری زمان

3.3. رابطه تسلط فاصله

4. ارزیابی تغییرات خط افق تحت حرکت افزایشی

4.1. هرس با استفاده از خواص هندسی

4.2. تغییر خط افق در زیر زمینه های متحرک

5. محاسبه خط آسمان

5.1. پردازش مستمر پرس و جو Skyline

5.2. ساختار و شرایط داده

5.3. مکانیسم های رویداد محور برای پردازش پرس و جو مستمر

6. استراتژی های هرس برای الگوهای حرکتی خاص

7. آزمایشات

8. نتیجه گیری

اختصارات

منابع

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

بعدیبرآورد مدل‌های سه بعدی داخلی با انتشار محدودیت و استدلال تصادفی در غیاب اندازه‌گیری‌های داخلی

بدون نظر

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