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

با رشد روز افزون شبکه ها نیاز به پشتیبانی پرس و جوی موثر و روش های معنایی در گراف های ساختماری در مقیاس بزرگ هستیم به شدت افزایش یافته اند. هسته بسیاری از عملیات شبکه های پیشرفته، اول از یک گراف پرس و جوی متداول شروع می شود: چطور ساختارهای گراف موثری را با یک شبکه بزرگ جست و جو کنیم؟ بدبختانه، به علت ماهیت NP – کامل تناظر زیر گراف ها، جستجوی کامل دشوار است و هنگامی که شبکه آزمایشی بزرگ و واگرا نیز باشد بسیار چالش برانگیز می شود. در این مقاله ما یک روش عالی با مکانیسم شاخص دهی گراف SPath را برای از بین بردن مشکل جستجوی گراف بر روی شبکه های بزرگ را بررسی کرده ایم. SPath کوتاهترین مسیر را در اطراف همسایگی راس را به عنوان واحدهای اساسی شاخص بندی در نظر می گیرد و از این طریق روش راس – در – یک – زمان به روش مسیر – در – یک – زمان تبدیل شده است: اول راس به یک دسته از کوتاهترین مسیرها تفکیک می شود و با یک بهینه گر جستجوی نقشه، از بین آنها یک زیر مجموعه از کاندیدهای با حساسیت خوب انتخاب می شود و سپس مسیرهای کاندید به هم متصمل می شوند تا به پوشش دهی و جستجوی گراف کمک کنند و پروسه جستجوی گراف به پایان برسد. ما SPath را با گراف QL، بر روی دسته های داده واقعی و ساختگی ارزیابی می کنیم. مطالعات تجربی ما نشان می دهد که SPath بر روی شبکه های بزرگ بیشتر عملی است.

کلیدواژه ها:

بهینه سازی پرش و جو ، گراف ، شبکه های بزرگ ، SPath