په ډیټا کې د فعال انحصار موندنه د ډیټا تحلیل په بیلابیلو برخو کې کارول کیږي: د ډیټابیس مدیریت ، د معلوماتو پاکول ، ډیټابیس ریورس انجینري او د ډیټا سپړنه. موږ دمخه پخپله د انحصارونو په اړه خپاره کړي دي انستاسیا بیریلو او نیکیتا بوبروف. دا ځل د کمپيوټر ساينس له مرکز څخه سږ کال فارغه شوې انستاسيا د دغه کار د پرمختګ خبره د څېړنيزو کارونو د يوې برخې په توګه شريکوي چې په دې مرکز کې يې دفاع کوله.
د دندې انتخاب
په CS مرکز کې د زده کړې پرمهال، ما د ډیټابیسونو په ژوره توګه مطالعه پیل کړه، د بیلګې په توګه، د فعالیت او توپیر انحصارونو لټون. دا موضوع په پوهنتون کې زما د کورس د کار له موضوع سره تړاو درلود، نو د کورس په کار کې د کار کولو په وخت کې ما په ډیټابیس کې د مختلفو انحصارونو په اړه مقالې لوستل پیل کړل. ما د دې سیمې بیاکتنه لیکلې - زما یو له لومړیو څخه په انګلیسي کې او د SEIM-2017 کنفرانس ته یې سپارلی. زه ډیر خوشحاله وم کله چې ما وموندله چې هغه په هرڅه کې ومنل شوه، او پریکړه یې وکړه چې موضوع ته ژوره کتنه وکړي. مفهوم پخپله نوی ندی - دا په 90s کې بیرته کارول پیل شو، مګر حتی اوس دا په ډیرو برخو کې کارول کیږي.
په مرکز کې زما د دویم سمستر په جریان کې، ما د څیړنې پروژه پیل کړه ترڅو د فعال انحصارونو موندلو لپاره الګوریتم ښه کړي. هغې په JetBrains ریسرچ کې د سینټ پیټرزبرګ دولتي پوهنتون فارغ شوي زده کونکي نیکیتا بوبروف سره یوځای کار کړی.
د فعال انحصارونو لټون کولو کمپیوټري پیچلتیا
اصلي ستونزه د کمپیوټري پیچلتیا ده. د ممکنه لږترلږه او غیر معمولي انحصارونو شمیر د ارزښت له مخې پورته محدود دی چیرته - د جدول د ځانګړتیاو شمیر. د الګوریتم عملیاتي وخت نه یوازې د ځانګړتیاوو په شمیر پورې اړه لري، بلکې د قطارونو په شمیر پورې اړه لري. په 90s کې ، په منظم ډیسټاپ کمپیوټر کې د فدرالي قانون لټون الګوریتم کولی شي د ډیټا سیټونه پروسس کړي چې تر 20 پورې ځانګړتیاوې لري او په څو ساعتونو کې په لسګونو زره قطارونه. عصري الګوریتمونه چې په ملټي کور پروسیسرونو کې روان دي د ډیټا سیټونو لپاره انحصار کشف کوي چې په سلګونو ځانګړتیاوې لري (تر 200 پورې) او په ورته وخت کې په سلګونو زره قطارونه. په هرصورت، دا کافي ندي: دا ډول وخت د ډیری ریښتینې نړۍ غوښتنلیکونو لپاره د منلو وړ نه دی. له همدې امله، موږ د موجوده الګوریتمونو د چټکولو لپاره طریقې رامینځته کړې.
د ویشلو تقاطع لپاره د کیشینګ سکیمونه
د کار په لومړۍ برخه کې، موږ د الګوریتم ټولګي لپاره د کیچ کولو سکیمونه رامینځته کړل چې د پارشن انټرسیکشن میتود کاروي. د ځانګړتیا لپاره برخه د لیستونو مجموعه ده، چیرې چې هر لیست د ورکړل شوي خاصیت لپاره ورته ارزښتونو سره د کرښې شمیرې لري. هر دا ډول لیست د کلستر په نوم یادیږي. ډیری عصري الګوریتمونه پارشنونه کاروي ترڅو معلومه کړي چې انحصار ساتل کیږي یا نه، د بیلګې په توګه، دوی لیما ته غاړه ایږدي: انحصار ترسره کیږي که . دلته یوه برخه ډیزاین شوې او د برخې اندازې مفهوم کارول کیږي - په دې کې د کلسترونو شمیر. الګوریتمونه چې پارټیشنونه کاروي ، کله چې انحصار سرغړونه کیږي ، د انحصار ښي اړخ ته اضافي صفات اضافه کوي ، او بیا یې بیا محاسبه کوي ، د برخې د تقاطع عملیات ترسره کوي. دا عملیات په مقالو کې تخصص بلل کیږي. مګر موږ ولیدل چې د انحصارونو لپاره برخې چې یوازې د تخصص د څو پړاوونو وروسته ساتل کیږي په فعاله توګه بیا کارول کیدی شي، کوم چې کولی شي د الګوریتم چلولو وخت د پام وړ کم کړي، ځکه چې د تقاطع عملیات ګران دي.
له همدې امله، موږ د شینن انټروپي او ګیني ناڅرګندتیا، او همدارنګه زموږ میټریک، کوم چې موږ د ریورس انټروپي پر بنسټ یو هیوریسټیک وړاندیز وکړ. دا د شینن انټروپي یو څه بدلون دی او د ډیټا سیټ انفرادیت زیاتیدو سره وده کوي. وړاندیز شوی هوریستیک په لاندې ډول دی:
دا - د وروستي محاسبه شوي ویش د انفرادیت کچه او د انفرادي ځانګړتیاو لپاره د انفرادیت درجې منځنی دی. پورته ذکر شوي ټول درې میټریکونه د انفرادیت میټریک په توګه ازمول شوي. تاسو دا هم په پام کې نیولی شئ چې په هیوریسټیک کې دوه بدلون کونکي شتون لري. لومړی دا په ګوته کوي چې اوسنۍ برخه لومړني کیلي ته څومره نږدې ده او تاسو ته اجازه درکوي په لویه کچه هغه برخې ذخیره کړئ چې د احتمالي کیلي څخه لرې دي. دوهم ترمیم کونکی تاسو ته اجازه درکوي د کیچ قبضیت نظارت وکړئ او په دې توګه په کیچ کې د نورو برخو اضافه کولو هڅوي که چیرې وړیا ځای شتون ولري. د دې ستونزې بریالي حل موږ ته اجازه راکړه چې د PYRO الګوریتم 10-40٪ ګړندی کړو، د ډیټاسیټ پورې اړه لري. د یادونې وړ ده چې د PYRO الګوریتم په دې برخه کې تر ټولو بریالی دی.
په لاندې شکل کې تاسو کولی شئ د اساسي سکې فلیپ کیچ کولو طریقې په پرتله د وړاندیز شوي هیوریسټیک پلي کولو پایلې وګورئ. د ایکس محور لوګاریتمیک دی.
د برخې ذخیره کولو لپاره بدیل لاره
بیا موږ د برخې ذخیره کولو لپاره بدیل لاره وړاندیز کړه. پارټیشنونه د کلسترونو یوه ټولګه ده، چې هر یو یې د ځانګړو ځانګړتیاو لپاره د ورته ارزښتونو سره د ټپلونو شمیر ذخیره کوي. دا کلسترونه ممکن د ټپل شمیرو اوږده لړۍ ولري، د بیلګې په توګه که چیرې په جدول کې ډاټا ترتیب شي. له همدې امله، موږ د پارشنونو ذخیره کولو لپاره د کمپریشن سکیم وړاندیز کړی، د بیلګې په توګه د ویشونو په کلسترونو کې د ارزښتونو وقفه ذخیره کول:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{لومړی وقفه}, underbrace{7}, 8}_{دوهمه وقفه}, 10}}\ downarrow{کمپریشن} \ pi(X) = {{ underbrace{$, 1, 5}_{لومړی~interval}, underbrace{7}, 8}_{دویمه~interval}, 10}}$$display$$
دا میتود وتوانید چې د TANE الګوریتم عملیاتو په جریان کې د حافظې مصرف له 1 څخه تر 25٪ پورې کم کړي. د TANE الګوریتم د فدرالي قوانینو لټون کولو لپاره یو کلاسیک الګوریتم دی؛ دا د خپل کار په جریان کې برخې کاروي. د تمرین د یوې برخې په توګه، د TANE الګوریتم غوره شوی و، ځکه چې په دې کې د وقفې ذخیره کولو پلي کول خورا اسانه وو، د بیلګې په توګه، په PYRO کې د دې لپاره چې دا ارزونه وکړي چې ایا وړاندیز شوې طریقه کار کوي. ترلاسه شوي پایلې په لاندې شکل کې وړاندې شوي. د ایکس محور لوګاریتمیک دی.
کنفرانس ADBIS-2019
د څیړنې د پایلو پراساس، د سپتمبر په 2019 کې ما یوه مقاله خپره کړه د ډیټابیس او معلوماتو سیسټمونو (ADBIS-23) کې د پرمختګ په اړه 2019م اروپایي کنفرانس کې. د پریزنټشن په جریان کې، کار د ډیټابیس په برخه کې د پام وړ شخص، برنارډ تلهیم لخوا یادونه وشوه. د څیړنې پایلې د سینټ پیټرزبورګ دولتي پوهنتون کې د ریاضیاتو او میخانیکونو په برخه کې د ماسټرۍ په دور کې زما د مقالې اساس جوړ کړ، چې په ترڅ کې دواړه وړاندیز شوي طریقې (کیچنګ او کمپریشن) په دواړو الګوریتمونو کې پلي شوي: TANE او PYRO. سربیره پردې، پایلو ښودلې چې وړاندیز شوي طریقې نړیوال دي، ځکه چې په دواړو الګوریتمونو کې، د دواړو طریقو سره، د حافظې په مصرف کې د پام وړ کمښت لیدل شوی، او همدارنګه د الګوریتم په عملیاتي وخت کې د پام وړ کمښت لیدل شوی.
سرچینه: www.habr.com