کاستی های الگوریتمی در موتورهای جستجوی وب سایت

کاستی های الگوریتمی در موتورهای جستجوی وب سایت

ما در این مقاله شش مسأله الگوریتمیحل نشده یا بخشی حل شده را که در موتورهای جست و جوی وب رخ میدهد شرح میدهیم : (1) نمونه گیری یکنواخت صفحات وب (2) مدل کردن گراف وب (3) یافتن میزبانهای دوگان (4) یافتن تارک داران و تارک بازان (5) یافتن گرافهای بزرگ دوبخشی چگال ، و درک چگونگی إفراز وب توسط بردارهای ویژه .
1 . مقدمه
موتور جست و جوی وب از سه بخش تشکیل میشود : (1) یک دنبالگرد crawler که صفحات وب را پیدا میکند تا داخل مجموعه صفحات وب آن موتور قرار گیرد، (2) یک شاخص گذار indexer که شاخص معکوس inverted index ( نیز موسوم به شاخصindex ) را که ساختمان اصلی دادههای مورد استفاده ی آن موتور جست وجواست و صفحات وب دنبال گشته crawled را ارائه میکند ، (3) یک پاسخ دهنده که پرس و جو های کاربررا با استفاده از شاخصها پاسخ میدهد .
در حد مقصود ما بگوییم، دنبالگرد، وب را به مثابه ی یک گراف مینگرد : هر صفحه وبیک گره است و هر ابرپیوند یک کمان است . پرسش اساسی ای که دنبالگرد با آنرودررو است این است که کدام صفحه ها را پیدا کند تا ‹‹ مناسب ترین››صفحات را در مجموعه ی خود داشت باشد .
برخی مسائل باز که ذیلا عنوان شده است، میتواند دنبالگردهابهبود بخشد.
-درک بهتر از ساختار گراف (بخش 3 ) ممکن است به راه کارآمدتری برای دنبالگردی در وب منجر شود .
- درک بهتر خصوصیت های مختلف وب (بخش 2) میتواند مشخص کند کدام جمعیت از صفحه ها در دنبالگردی تا بدینجا کمترارائه شده هستند .
- راه مؤثری برای یافتن میزبانهای دوگان Duplicate hosts میتواند به دنبالگرد کمک کند تا از دنبالگردی در دوگان‏‏ میزبانیکه قبلا دنبالگردی کرده است ، پرهیز نماید .
به فرض این که مجموعه ای از پرس وجوها به موتور جست و جوعرضه شدهباشد ، مساله ی اصلی این است که کدام پرس وجوها بیشتر بوده است.البته برایکشف تأثیرات موقت ، جستن « تارک داران» top gainers و « تارک بازان» top losers نیز جالب است . این مسأله در بخش 5 مطرح شده است.در پایان ، دو مسأله را که در ارتباطبا خوشه ای شدن موضوع-وابسته ی وبیا یک زیرگراف آن است مطرح میکنیم: بخش 6 از مسأله ی یافتن زیر گرافهایدوبخشی جهت دار چگال بحث میکند . بخش 7 پرسش چگونگی اشتقاق بردارهای ویژه یماتریسهای مختلف را از گراف وب عرضه میدارد . ما هر یک از این مسائل باز را ترسیم کرده ، ارجاعاتی نیز به کارهای پیشین در این زمینه میدهیم .
2- نمونه گیری صفحات وب
درک وب و خصوصیت های آن ، از آغاز وب ، یک موضوع مهم تحقیقاتی است . چند صفحه در وبوجود دارد؟چند تا از آنها توسط موتور جست و جویی شاخص گذاری شده است؟ چندصفحه به یک زبان خاص یا در یک حوزه ی معین وجود دارد ؟ متوسط اندازه ی یکصفحه ی وب چقدر است ؟ چه درصدی از صحات وب صفحه ی اصلی هستند ؟ و این خصوصیت ها در زمان چگونه تغییر میکند ؟ موتور های جست وجومیکوشند تا آنجا که ممکن باشد، اطلاعاتوب را ثبت کنند . به علاوه نسبت انواع مختلف صفحه ها ، نظیر صفحه های به زبانهای مختلف باید تقریبا متناسب با انواع موجود در وب باشد .
رد گیری این خصوصیات در دنبالگردی بدیهی است . بنابر این اگر این آمار برای وب معلوم باشد ، دنبالگرد میتواند تعیین کند که چه انواعی از صفحات وب تا بدینجا خیلی کمتر ارائه شده هستندو بکوشد بیشتر از آنها دنبالگردی کند .
برا ی نمونه گیری یکنواخت صفحات وب میشد از یکفناستفاده کرد ، تا همه ی چنین سؤالاتی را به جز سؤال نخست پاسخ داد .متأسفانه چنین فنی شناخته نشده است اگرچه تحقیقات دامنهداری در این خصوصصورت گرفته است . لارنس و جایلز[Lawrence and giles 99 ] از رهیافتهای مبتنی بر آزمون تصادفی نشانی های ip  بهره گرفتند : آنها یک نشانی تصادفی ip   را انتخاب کردند و بررسی کردند که آیا آن میزبان host یک وبگاهاست یا نه . در صورت بودن ،آنها میکوشند صفحه های وب دسترس پذیر این وبگاهرا نمونه گیری کنند . البته اگر از صفحات وب یک وبگاهفهرست جامعی نداشته باشیم این که چگونه از این صفحه های وب نمونه گیری کنیم ، همچنان یک مسأله ی باز باقی خواهد ماند . هنتسینگر و همکارانش [henzinger et al . 00] تشکیل یک راه تصادفی خاص را بر گراف (جهت دار ) وب و آنگاه نمونه گیری ازصفحاتعبور شده را به طور معکوس متناسب با توزیع ثابت راه تصادفی مطرح نمودند . این رهیافت مشکلاتی چند دارد . یک مسأله این که، واضح نیست که چند مرحله باید انجام داد تا توزیع متوازن راتقریب زد.

منبع : شبکه فناوری اطلاعات ایران