کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952469 | 1442038 | 2016 | 29 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An efficient method to evaluate intersections on big data sets
ترجمه فارسی عنوان
یک روش کارآمد برای ارزیابی تقاطعات بر روی مجموعه داده های بزرگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تقاطع را تنظیم کنید فایل های معکوس، توالی های فاصله، موتورهای جستجو، اطلاعات بزرگ،
ترجمه چکیده
تقاطع ها در علوم کامپیوتر مهم هستند. به ویژه، تقاطع لیست های معکوس عملیات اساسی در بازیابی اطلاعات برای پایگاه داده های متنی و موتورهای جستجوی وب است. در این مقاله، ما در مورد یک روش کارآمد و موثر برای اجرای این عملیات در زمینه مجموعه داده های بسیار بزرگ بحث می کنیم. ایده اصلی آن این است که جستجو باینری را بر توالی های مرتب شده ای که هر کدام به یک لیست معکوس مربوط می شوند انجام دهند و با ایجاد یک ترفند بر توالی شناسه های مجموعه و همچنین یک نوع کد گذاری درخت ساخته می شود که هر گره در فاصله زمانی مشخص شده است. در بسیاری از موارد، توالی بازه بسیار کوتاه تر از فهرست معکوس آن است. به طور خاص، کمترین اجداد مشترک از فواصل در یک تری، می تواند برای کنترل یک جستجو باینری برای از بین بردن چک کردن محدودیت های بی فایده استفاده شود، که ما را قادر می سازد تا برای انجام این کار به الگوریتم آفلاین خطی دست یابیم و از لحاظ نظری بهتر از هر روش های سنتی در خط (در هزینه فضای بیشتر). آزمایش ها انجام شده است، نشان می دهد که تجارت فضا برای زمان ارزشمند است.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Set intersections are important in computer science. Especially, intersection of inverted lists is a fundamental operation in information retrieval for text databases and Web search engines. In this paper, we discuss an efficient and effective way to implement this operation in the context of very big data sets. The main idea behind it is to do a binary search over sorted interval sequences, each of which corresponds to an inverted list and is constructed by establishing a trie over the sequences of set identifiers as well as a kind of tree encoding, by which each node in the trie is assigned an interval. In many cases, an interval sequence is much shorter than its corresponding inverted list. In particular, the lowest common ancestors of intervals in a trie can be utilized to control a binary search to skip over useless interval containment checks, which enables us to reach an optimal off-line algorithm to do the task, and is theoretically better than any traditional on-line methods (at cost of more space). Experiments have been conducted, showing that the trade-off of space for time is worthwhile.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 1-21
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 1-21
نویسندگان
Yangjun Chen, Weixin Shen,