Skip Navigation Linksلیست مقالات ترجمه شده / مقالات ترجمه شده مهندسی كامپيوتر /

عنوان ترجمه شده مقاله: فشرده‌سازی گراف وب محکم و ساده برای فوروارد و پرس و جوهای همسایه معکوس

تعدادی از الگوریتم‌های مربوط به تکنیک‌های فشرده‌سازی برای نشان دادن گراف‌های وب فشرده، اما با ارائه دسترسی تصادفی، ارائه شده‌اند.
 Abstract

Analyzing Web graphs has applications in determining page ranks, fighting Web spam, detecting communities and mirror sites, and more. This study is however hampered by the necessity of storing a major part of huge graphs in the external memory which prevents efficient random access to edge (hyperlink) lists. A number of algorithms involving compression techniques have thus been presented, to represent Web graphs succinctly, but also providing random access. Those techniques are usually based on differential encodings of the adjacency lists, finding repeating nodes or node regions in the successive lists, more general grammar-based transformations or 2-dimensional representations of the binary matrix of the graph. In this paper we present three Web graph compression algorithms. The first can be seen as engineering of the Boldi and Vigna (2004) method. We extend the notion of similarity between link lists and use a more compact encoding of residuals. The algorithm works on blocks of varying size (in the number of input lists) and sacrifices access time for better compression ratio, achieving more succinct graph representation than other algorithms reported in the literature. The second algorithm works on blocks of the same size in the number of input lists. Its key mechanism is merging the block into a single ordered list. This method achieves much more attractive space–time tradeoffs. Finally, we present an algorithm for bidirectional neighbor query support, which offers compression ratios better than those known from the literature

چکیده

تجزیه و تحلیل گراف‌های وب، برنامه‌های کاربردی در تعیین رتبه صفحه، مبارزه با هرزنامه وب، تشخیص جوامع و سایت‌های آینه، و بیشتر را دارند. این مطالعه مانع ضرورت ذخیره‌سازی بخش عمده‌ای از گراف‌های بزرگ در حافظه خارجی می شود و از دسترسی تصادفی کارآمد به لیست‌های لبه (لینک) جلوگیری می‌کند. تعدادی از الگوریتم‌های مربوط به تکنیک‌های فشرده‌سازی برای نشان دادن گراف‌های وب فشرده، اما با ارائه دسترسی تصادفی، ارائه شده‌اند. این تکنیک‌ها معمولاً بر اساس کدگذاری دیفرانسیلی از لیست‌های مجاورت، یافتن گره‌های تکراری یا مناطق گره در لیست‌های متوالی، به طور کلی‌تر گرامر مبتنی بر تبدیلات یا بازنمایی 2 بعدی از ماتریس دودویی گراف هستند. در این مقاله سه الگوریتم فشرده سازی گراف وب ارائه می‌شود. اولی می‌تواند به عنوان مهندسی روش‌های Boldi و Vigna (2004) دیده شود. مفهوم شباهت بین لیست‌های لینک را توسعه می‌دهیم و از رمزگذاری فشرده‌تر باقیمانده‌ها استفاده می‌کنیم. الگوریتم بر روی بلوک‌هایی با اندازه‌های مختلف (در تعداد لیست ورودی) و فدا کردن زمان دسترسی برای نسبت تراکم بهتر، دستیابی به بازنمایی گراف فشرده‌تر از الگوریتم‌های دیگر گزارش شده در متون کار می‌کند. الگوریتم دوم بر روی بلوک‌هایی از همان اندازه در تعداد لیست‌های ورودی کار می‌کند. مکانیسم کلیدی آن ادغام بلوک به یک لیست مرتب واحد است. این روش به مصالحه فضا-زمان بسیار جذاب‌تر دست می‌یابد. در نهایت، یک الگوریتم برای حمایت پرس و جوی همسایه دو طرفه ارائه می‌شود که نسبت فشرده سازی بهتری از الگوریتم‌های شناخته شده از متون را ارائه می‌دهد.

1-مقدمه

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


موسسه ترجمه البرز اقدام به ترجمه مقاله " مهندسی كامپيوتر " با موضوع " فشرده‌سازی گراف وب محکم و ساده برای فوروارد و پرس و جوهای همسایه معکوس " نموده است که شما کاربر عزیز می توانید پس از دانلود رایگان مقاله انگلیسی و مطالعه ترجمه چکیده و بخشی از مقدمه مقاله، ترجمه کامل مقاله را خریداری نمایید.
عنوان ترجمه فارسی
فشرده‌سازی گراف وب محکم و ساده برای فوروارد و پرس و جوهای همسایه معکوس
نویسنده/ناشر/نام مجله :
Discrete Applied Mathematics
سال انتشار
2014
کد محصول
1005446
تعداد صفحات انگليسی
9
تعداد صفحات فارسی
20
قیمت بر حسب ریال
710,000
نوع فایل های ضمیمه
Pdf+Word
حجم فایل
1 مگا بایت
تصویر پیش فرض


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


این مقاله ترجمه شده مهندسی كامپيوتر در زمینه کلمات کلیدی زیر است:





Graph compression
Random access
Bidirectional neighbor queries

تاریخ انتشار در سایت: 2015-08-27
جستجوی پیشرفته مقالات ترجمه شده

خدمات ترجمه تخصصی و ویرایش مقاله مهندسی كامپيوتر در موسسه البرز

نظرتان در مورد این مقاله ترجمه شده چیست؟

ثبت سفارش جدید