Reconfigurable computing based on FPGA is a promising solution to accelerate applications for web search engines. Due to the challenge of such data-intensive applications, data compression has become much more important. This paper proposes a data compression method for inverted indices, which combines the bit-level compression method - Huffman coding and a coarse-grained compression method, to achieve a balanced performance in compression ratio and decompression speed. Because an inverted index is only compressed once, the compression speed is not the major measurement for a compression method. The proposed method shows good to 21.61% compression ratio on inverted indices from a commercial search engine. This compression ratio is better than results by other existing compression methods. We also develop an efficient FPGA-based hardware decompression module, which could provide up to 996 MBps input bandwidth for the accelerator system

چکیده

محاسبۀ قابل پیکربندی مجدد براساس FPGA راهکاری نویدبخش جهت سرعت بخشیدن به موارد کاربردی برای موتور جستجو های محیط وب می باشد. بدلیل چالش های موجود در این کاربردهای متمرکز برداده، فشرده سازی داده ها دارای اهمیت دوچندانی شده است. این مقاله، یک روش فشرده سازی داده را برای اندکس های وارونه مطرح می کند که روش فشرده سازیِ سطح بیت – کدگذاریِ هافمن و روش فشرده سازی درشت دانه ، را برای دستیابی به عملکرد متعادل در نسبت فشرده سازی و سرعت وافشرده سازی (مترجم: خارج کردن از حالت فشرده) مطرح می کند. بدلیل آنکه اندکس وارونه تنها یکبار فشرده سازی می شود، سرعت فشرده سازی معیار اصلی برای روش فشرده سازی نیست. روش پیشنهادی با نسبت فشردگیِ 21.61% برای اندکس های وارونه حاصل از یکموتور جستجوی تجاری، مناسب جلوه می کند. این نسبت فشردگی بهتر از نتایج حاصل از دیگر روش های فشرده سازی موجود می باشد. همچنین ما یک ماژول کارآمد برای وافشرده سازیِ سخت افزاریِ مبتنی بر FPGA  ایجاد می کنیم که می تواند یک پهنای بندی ورودی تا 996MBps را برای سیستم شتاب دهنده فراهم آورد.

1-مقدمه

سیستم های بازیابی اطلاعات بخشی حیاتی از زیرساخت های اطلاعاتی امروزی و سرویس های آنلاینِ بزرگ هستند. اندکس وارونه معمولاً جهت تامین دسترسیِ موثر به محتوای این سیستم ها در موتور جستجو های مدرن بکار گرفته می شود، و این سرویس بکارگیریِ اندکس نامیده می شود. معمولاً ، موتور جستجو اندکس وارونه را برای فایل های نوشتاریِ حاصل از اینترنت ایجاد می کند. اندکس عبارت (کلمه) ای است که در موتور جستجو مورد پرس و جو قرار می گیرد و محتوا، ID های نوشتار می باشند (DocIDs) که این کلمه در آنها ظاهر می شوند. غالباً، فراوانی و موقعیتِ این عبارت در فایل های نوشتاری نیز ثبت می شود. در این مقاله، ما تنها DocID ها را در فهرست ورودی درنظر می گیریم و فراوانی و موقعیت را درنظر نمی گیریم. دسترسی به اندکس وارونه عمل اساسی برای پردازش یک جستار می باشد. با رشد سریعِ صفحات وب، نیاز به دسترسیِ سریع تر به اندکس وارونه و توان عملیاتیِ بالاتر برای پردازش جستار در موتور های جستجو حس می شود. ازینرو ، تکنیک های مختلفِ فشرده سازی برای کاهش سایز اندکس و افزایش کاراییِ I/O برای کل سیستم توسعه یافته اند…