An efficient method to evaluate intersections on big data sets

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