کشف بهترین الگوریتم جریان داده‌ها برای دیتابیس‌های بزرگ

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

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

برنامه‌های کامپیوتری انجام دهنده‌ی این محاسبات را «الگوریتم‌های جریان» (streaming algorithms) می‌نامند. از آنجایی که دادها در چنین حجم بزرگی به سمت این نرم‌افزارها سرازیر می‌شوند، این ماشین‌ها سعی میکنند عصاره‌ای از این چیزی که می‌بینند را ثبت کنند و اصولا از نظر تکنیکی مابقی را فراموش می‌کنند. بیشتر از ۳۰ سال است که دانشمندان علوم کامپیوتر در تلاش برای ساخت یک الگوریتم جریان بهتر هستند. پاییز گذشته محققان موردی ابداع کردند که تقریبا بی عیب و نقص است.

جلانی نلسون، استاد کامپیوتر دانشگاه هاروارد و نویسنده‌ی کتابی در این رابطه (همراه با کاسپر گرین لارسن از دانشگاه آرهوس در دانمارک و هوی وین از دانشگاه شمال شرقی و میکل تروپاز از دانشگاه کپنهاگن) می‌گوید:«ما الگوریتم جدیدی را توسعه داده‌ایم که تقریبا در نوع خود بهترین است».

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

در دیتابیس‌هایی که بطور مداوم در حال به روز رسانی هستند و شما نظاره‌گر آن هستید، الگوریتم جریان داده ها بسیار مفید عمل می‌کنند. برای مثال می‌توانیم به AT&T اشاره کنیم که بطور مکرر تب‌ها را بر بسته‌های داده حفظ می‌کند یا گوگل که همیشه در حال دسته‌بندی کردن جریان مدخل‌های بی پایان ورودی جستجو است. در این جورمواقع، داشتن متدی برای پاسخ‌دهی به سوالات آنی درباره داده، بدون بررسی مجدد و حتی بدون نیاز به یادآوری آن داده‌ها، کاری مفید و حتی ضروری است.

یک مثال ساده: فرض کنید جریان مداومی از اعداد در اختیار دارید و می‌خواهید جمع تمامی ارقامی که تا بحال مشاده کرده‌اید را حساب کنید. در این مورد روشن است که به جای به خاطر آوردن تمامی اعداد، تنها نیاز است یک رقم را به خاطر بیاورد: جمع تجمعی (running sum).

این چالش زمانی سخت‌تر می‌شود که سوالات پرسیده شده‌ی شما درباره داده پیچیده‌تر شود. فرض کنید به جای محاسبه کردن جمع ارقام، تمایل دارید که امکان پاسخ به سوال مقابل را داشته باشید: چه ارقامی بیشتر تکرار شدند؟ چندان مشخص نیست که شما می‌خواهید با استفاده از چه میانبری در لحظه به جواب دست پیدا کنید.

این پازل بخصوص به عنوان معضل «آیتم‌های تکرار شونده» یا «مشت‌زنان سنگین‌وزن» شناخته می‌شود. اولین الگوریتم ایجاد شده برای حل این معضل موردی بود که در دهه ۸۰ توسط دیوید گریس از دانشگاه کرنا و جایتدو میسرا از دانشگاه تگزاس ابداع شد. برنامه آنها از جهاتی موثر عمل کرد، اما نتوانست چیزی که آن را «تشخیص تغییر» می‌نامند را حل کند. این الگوریتم، واژه‌هایی که بیشتر از همه جستجو شده بودند را به شما می‌گفت، اما نمی‌توانست تشخیص دهد چه واژه‌هایی در حال ترند شدن هستند. در قضیه گوگل، این الگوریم «ویکی پدیا» را به عنوان محبوب‌ترین واژه جستجو شده شناسایی می‌کرد، اما نمی‌توانست خیزش واژه‌های جستجو شده در مواقع خاص، همچون واژه‌هایی که به همراه اخبار طوفان ایرما توییت می‌شدند، را شناسایی کند.

این یک مشکل در برنامه‌نویسی است. شما سعی می‌کنید اطلاعات را تا سطحی خلاصه و اطلاعاتی را استخراج کنید که به شما در شناسایی اولین واژه‌های جستجو شده کمک کند. این را گراهام کومود، یکی از محققان علوم کامپیوتر در دانشگاه وارویک توضیح داد.

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

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

اما با وجود این، باز هم نقاط ضعفی وجود دارد. برای مثال، زمان زیادی طول می‌کشد تا این الگوریتم در میان صدها هزار واژه در زبان انگلیسی به جستجو بپردازد.

اما چه اتفاقی می‌افتد اگر تنها صد کلمه در دیکشنری داشته باشیم؟ نلسون می‌گوید :«گشتن در میان لغات این دیکشنری زمان چندانی نمی‌خواهد».

ازینرو، تعداد کلمات موجود در دیکشنری همانی هستند که وجود دارند. مگر اینکه، همانطور که نویسندگان الگوریتم جدید کشف کرده‌اند، شما دیکشنری بزرگ را به دیکشنزی‌های کوچکتری تقسیم کنید و راه خلاقانه‌ای برای سر هم کردن دوباره آنها پیدا کنید.
داده‌های کوچک

ثبت و ردیابی اعداد کوچکتر، به نسبت اعدا بزرگتر، کار ساده‌تری است.

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

بر فرض شما شماره ۱۲,۳۴۵,۶۷۸ را می بینید. یک شیوه موثر برای بخاطر آوردن این شماره تقسیم کردن آن به چهار بلوک دو رقمی است: ۱۲, ۳۴, ۵۶, ۷۸٫ سپس می‌توانید هر بلوک را به یک الگوریتم تابع ارسال کنید که فرکانس آیتم‌ها را محاسبه می‌کند: ۱۲ یک الگوریتم را کپی می کند، ۳۴ دو الگوریتم را کپی می‌کند، ۵۶ سه الگوریتم را کپی می‌کند و ۷۸ چهار الگوریتم.

هر الگوریتم تابع، مدخل خود از چیزی که دیده است را حفظ می‌کند، اما از آنجایی که هر نسخه هیچوقت چیزی بیشتر از یک عدد دو رقمی را نمی‌بیند، هر مدخل تنها مابین عددهای صفر تا ۹۹ در نوسان هستند.

یک ویژگی مهم از تقسیم کردن اعداد بزرگ این است که، اگر این عدد بزرگ، ۱۲۳۴۵۷۸، در جریان کلی داده‌ی شما بطور مکرر ظاهر شود، اجزای دو رقمی آن نیز ظاهر می‌شوند. زمانی که شما از هر الگوریتم تابع می‌خواهید که ارقامی که بیشتر دیده اند را شناسایی کنند، کپی اول ۱۲ را به ما می‌دهد، کپی دوم ۳۴ را به ما می‌دهد و به همین ترتیب. شما قادر خواهید بود بیشترین اعداد تکرار شده در هر گروه را تنها با نگاه کردن به آیتم‌های تکرار شده در هر لیست پیدا کنید.

نلسون می‌گوید :«به جای صرف کردن ۵۰ میلیون واحد زمانی برای چرخش دور کل کهکشان، شما تنها از چهار الگوریتم برخوردارید که ۱۰۰ واحد از زمان را صرف می‌کنند».

مشکل اصلی استراتژی تقسیم کردن این است که، با وجود ساده بودن قطعه کردن اعداد بزرگ به اعداد کوچک، سر هم کردن دوباره آن به یک عدد بزرگ کار ساده‌ای نیست. نمی‌توان با در کنار هم قرار دادن این اعداد کوچک عدد بزرگ را به دست آورد.

برای مثال، فرض کنید جریان داده شما بطور مکرر شامل اعدادی می‌شود که در میان آنها عدد مشترک وجود دارد: ۱۲۳۴۵۶۷۸ و ۱۲۹۹۹۹۹۹٫ هر دو با ۱۲ شروع می‌شوند. الگوریتم شما هر عدد را به چهار عدد کوچکتر تبدیل می ، سپس هر کدام را به یک الگوریتم تابع ارسال می‌کند. سپس، شما از هر الگوریتم تابع درخواست می کنید که :«چه اعدادی را دیده‌اید که بیشتر تکرار شده‌اند؟». کپی اول می‌گوید :«تعداد زیادی از ۱۲ دیده‌ام». الگوریتمی که تلاش می‌کند بفهمد کدام اعداد هشت رقمی دیده شده، بیشتر تکرار شده اند، نمی تواند بگوید آیا تمامی این ۱۲ ها به یک گروه هشت رقمی مربوط است و یا متعلق به دو گروه متفاوت است.

نلسون می‌گوید: «چالش، فهمیدن این مورد است که کدام بلوک دو رقمی باید بر کدام بلوک دو رقمی دیگر متمرکز شود».

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

برای مشاهده کردن رویکرد ساده‌ای از شیوه ی تگ گذاری، با عدد ۱۲۳۴۵۶۷۸ شروع و آن را به بلوک‌های دو رقمی تقسیم کنید. قبل از اینکه هر بلوک را به الگوریتم تابع مرتبط‌اش ارسال کنید، بلوک را با یک جفت عدد شناسایی منحصربفرد، که می توان از آن برای جمع کردن ارقام در کنار هم استفاده کرد، بسته بندی کنید. اولین تگ به عنوان نام بلوک عمل می‌کند و دومی به عنوان یک لینک. به این شیوه، ۱۲۳۴۵۶۷۸ به مورد زیر تبدیل می شود:

۱۲, ۰, ۱ / ۳۴, ۱, ۲ / ۵۶, ۲, ۳ / ۷۸, ۳, ۴

اینجا عدد ۱۲ اسم ۰ را بر خورد دارد و به عددی با اسم ۱ لینک می شود. عدد ۳۴ اسم ۱ را بر خورد دارد و به عددی با اسم ۲ متصل می شود. و به همین ترتیب.

اکنون، زمانی که الگوریتم‌های تابع به بلوک‌هایی که بیشترین تکرار را داشته‌اند برمی‌گردند، ۱۲ به دنبال عددی با تگ ۱ می‌گردد و ۳۴ را پیدا می‌کند، سپس ۳۴ به دنبال عددی با تگ ۲ می‌گردد و ۵۶ را پیدا می‌کند، و ۵۶ به دنبال عددی با تگ ۳ می‌گردد و ۷۸ را پیدا می‌کند.

به این شیوه، شما می‌توانید بلوک‌های دو رقمی را به عنوان لینک‌هایی زنجیره‌ای ببینید که در آن، لینک‌ها توسط این اعداد تگ‌گذاری شده اضافی کنار هم جمع می‌شوند.

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

پایه و اساس

هیچ الگوریتمی در زمان عملکرد بی عیب و نقص نیست. حتی بهترین الگوریتم‌ها نیز بعضی اوقات تیرشان به خطا می‌رود. در مثالی که از آن استفاده کردیم، مورد اشتباهی می‌تواند بلوک دو رقمی ثانوی، ۳۴، باشد که تگ اشتباهی را به آن چسپانده‌اند و به عنوان نتیجه، زمانی که به دنبال بلوکی می‌گردد که باید به آن ملحق شود، اطلاعات مورد نیاز برای پیدا کردن ۵۶ را در اختیار ندارد. و زمانی که این زنجیره لینکی پاره شود، کل تلاش ما بر باد می‌رود.

برای جلوگیری از پیش آمدن این مشکل، محققان از چیزی که آن را «گراف بسط دهنده» (expander graph) می‌نامند استفاده می‌کنند. در یک گراف بسط دهنده، هر بلوک دو رقمی یک نقطه را تشکیل می‌دهد. نقاط توسط خط به هم متصل می‌شوند (بر طبق فرآیند تگ ‌گذاری شرح داده شده در بالا) تا یک خوشه را تشکیل دهند. ویژگی مهم یک گراف بسط دهنده این است که به جای اتصال صرف هر نقطه با بلوک مرتبط با آن، شما هر بلوک دو رقمی را با دیگر بلوک‌های چندگانه متصل می‌کنید. برای مثال، با ۱۲۳۴۵۶۷۸، شما ۱۲ را هم با ۳۴ و هم با ۵۶ متصل می‌کنید، پس می‌توانید بگویید که ۱۲ و ۵۶ به یک شماره تعلق دارند حتی با وجود اینکه لینک مابین ۱۲ و ۳۴ شکست می‌خورد.

یک گراف بسط دهنده همیشه عالی عمل نمی‌کند. بعضی اوقات در لینک کردن دو بلوکی که باید لینک شوند با شکست مواجه می‌شود. یا دو بلوکی را به هم لینک می‌کند که به یکدیگر تعلق ندارند. برای جلوگیری از این رویداد، محققان قدم نهایی الگوریتم خود را توسعه دادند: یک الگوریتم «نگهدارنده خوشه» که می‌تواند یک گراف بسط دهنده را طی کند و بطور دقیق تشخیص دهد کدام نقاط باید با همدیگر خوشه شوند و کدام نقاط نه. حتی با وجود اینکه بعضی از خطوط تشکیل نشده‌اند و خطوط اشتباهی جایگزین آنان شده اند.

ثروپ می‌گوید :«این تضمین می‌دهد من می‌توانم چیزی که شبیه به خوشه‌های اصلی است را بازیابی کنم».

و از آنجایی که توییتر قرار نیست فردا طرح بسط دهنده را اجرایی کند، تکنیک‌های اساس آن به رنج گسترده‌تری از معضلات علوم کامپیوتر بسط پیدا می‌کنند.

این الگوریتم همچنین ثابت می‌کند که مواردی از فداکاریهایی که قبلا به نظر برای پاسخ به آیتم‌های مکرر لازم بودند، اصلا نیازی نیست که انجام یابند.

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