ابشاره سازی جزءبه جزء

آبشاره سازی جزءبه جزء. در علوم رایانه، آبشاره سازی جزءبه جزء (Fractional cascading) روشی است که با آن می توان، دنبال های از جستجوهای دودویی را انجام داد و یک مقدار مشخص را از میان دنباله ای از ساختار داده های مرتبط به هم، با سرعت بالایی جستجوی دودویی کرد.
یک نگاشت از اجزای لیست مربوط به یک گره، به اعداد صحیح کوچک؛ بنابراین برای بررسی ترتیب قرار گیری عناصر یک لیست، کافیست این اعداد صحیح نسبت داده شده به آن ها را با هم مقایسه کرد و با انجام عملیات بر عکس این نگاشت می توان از اعداد صحیح به اجزای اصلی لیست، دست یافت. روشی که Dietz در سال ۱۹۸۲ به آن دست یافت، راهکاری می دهد تا این نگاشت به صورت کارایی ذخیره شود؛ بنابراین هر گره، این نگاشت را ذخیره می کند و تنها با داشتن همین نگاشت می توان از اعضای لیست به لیستی از اعداد صحیح کوچک تر و برعکس دست یافت.
داده ساختاری برای جستجوی اعداد صحیح (داده ساختاری مانند van Emde Boas tree). با استفاده از این داده ساختار، می توان در میان اعداد صحیح نسبت داده شده به اعضای لیست، که طبق نگاشت گفته شده حاصل می شوند، به جستجوی عدد مورد نظر پرداخت.
برای هر گره همسایه در گراف کاتالوگ، یک داده ساختار جستجوگر اعداد صحیح مشابه برای زیر مجموعه ای از اعداد به دست آمده از آن گره در نظر گرفته می شود. به وسیلهٔ این داده ساختار و نگاشت اعضای لیست به اعداد صحیح، به صورت مؤثر می توان هر عضو x لیست آن گره را در تعداد مراحل ثابت پیدا کرد.
اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می شود، اما جستجوهای بعدی سریعتر خواهند بود. روش آبشاره سازی جزءبه جزء نخستین بار در سال ۱۹۸۶ توسط Chazelle Guibas , طی دو مقاله م(Chazelle & Guibas 1986a(Chazelle & Guibas ۱۹۸۶ ارائه شد. این روش، برگرفته از دو ایده بود: یکی ایدهٔ آبشاره سازی که از الگوریتم "جستجوی دامنه ای داده در داده ساختارهاً از لوکر (۱۹۷۸) و ویلارد (۱۹۷۸) برگرفته شده بود. دیگری ایده نمونه برداری جزء به جزء از (Chazelle (۱۹۸۳. بعد از آن افراد دیگری شکل های پیچیده تری از روش آبشاره سازی جزءبه جزء ارائه کردند. در این الگوریتم ها، داده ساختار، وقتی دنباله ای از عملیات حذف و درج روی آن انجام شود و داده ها تغییر کنند، همچنان معتبر است و امکان جستجوی سریع در آن وجود دارد.
در فناوری اطلاعات، اصطلاحاً به ترتیب دادن یک سلسله فعالیت های پیوسته در پردازش داده ها که در آن انجام هر مرحله وابسته به وقوع مرحلهٔ قبل است آبشاره سازی می گویند.
به عنوان یک مثال ساده از آبشاره سازی جزءبه جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده است. مجموع تعداد اعضای این لیست ها روی هم n است. یعنی اگر هر لیست را با Li نشان دهیم، Σ|Li|=n. می خواهیم این لیست ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷: