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