zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



ОЦІНКА ЕФЕКТИВНОСТІ ПРОЕКТУВАННЯ МУЛЬТИБАЗОВИХ СХОВИЩ ДАНИХ ЗА ДОПОМОГОЮ ДВОФАЗНОГО АЛГОРИТМУ

 

Яцишин А.Ю.

Україна, м. Київ,

Національний технічний університет України

«Київський політехнічний інститут»

 

Abstract. In previous work, two-phased algorithm of building of multibase data warehouses considering data sources has been introduced. In this article, this algorithm is estimated for both its speed and performance of built warehouse depending on parameter values.

 

У роботах [1] та [2] розглядається задача проектування і оптимізації мультибазових сховищ даних з врахуванням структурованості даних, у роботі [3] проводиться подальше теоретичне дослідження алгоритму, зокрема формальний опис процесу розподілу даних відповідно до їх структурованості.

Метою цілісного дослідження є розробка двофазного алгоритму проектування мультибазових сховищ даних. Даний алгоритм здійснює проектування мультибазового сховища в дві фази:

1)      Власне проектування, під час якого аналізуються джерела даних та відбувається інтеграція даних джерел відповідно до їх структурованості у носії сховища. На цій фазі відбувається побудова:

·       концептуальної моделі, що передбачає визначення таблиці сховища даних з даних джерел, що імпортуються;

·       логічної моделі, тобто визначення області сховища даних як зв'язок таблиць;

·       фізичної моделі, а саме визначення елементів носіїв даних.

2)      Оптимізація даних, яка полягає у застосуванні оптимізаційних методик (перерозташування структурованих та слабкоструктурованих даних, індексація, матеріалізація, горизонтальна та вертикальна фрагментація, злиття). Задача оптимізації формулюється наступним чином:

Нехай K1,…,Kn- класи запитів до сховища даних, що надійшли до сховища даних за звітний період.

Класифікація запитів виконується на основі операцій, які присутні у запиті, а також виразів параметрів операцій. Це дозволяє розділити запити на класи, при чому виконання запитів одного класу відбувається у схожий спосіб, що дозволяє говорити про подібний вплив змінних стану до запитів одного класу.

- доля всіх запитів вибору даних класу  по відношенню до всіх запитів вибору у сховищі за звітний період,

- розмір даних для еталонних запитів, визначається як кількість даних, отриманих у результаті виконання запитів, або, якщо запит не повертає даних, сумарну загальну площу таблиць, що беруть участь у запиті.

-час виконання еталонного запиту вибірки даних.

Необхідно оптимізувати сховище даних, тобто знайти такий стан сховища S, що наступна функція приймає максимальне значення

,                                                             (1)

У даній роботі пропонуються експериментальні результати проведеного дослідження.

Для оцінки ефективності виконання запитів до вихідних баз даних виконаємо серію запитів до них. Всього було виконано 3200 запитів, які належать до 166 класів запитів. Використовувалися СКБД Microsoft SQL Server Database Services (реляційна) та Analysis Services (багатовимірна), BaseX (XML), MongoDB (NoSQL).

Результати, описані нижче, отримані при наступних параметрах генетичного алгоритму:

·       Імовірність (частота) мутації : 0,05

·       Імовірність (частота) схрещування 0,8

·       Селекція за методом колеса рулетки.

·       Одноточкове схрещування.

·       Адаптивність за генами – залежить від довжини хромосоми.

У таблиці 1 показана швидкодія запитів (1) до інтеграції даних, після неї, та після оптимізації сховиша.

 

Таблиця 1.

Показники інтегральної швидкодії виконання запитів

 

Мінімальна швидкодія (1)

Середня швидкодія

Максимальна швидкодія

До інтеграції даних

413.0272

502.6794

587.2584

Після інтеграції даних

421.874

517.0587

608.1161

Після оптимізації

464.9081

560.4368

668.3728

 

У результаті проектування приріст швидкодії складає до 5%, у результаті оптимізації приріст швидкодії складає до 10%. Даний результат може бути досягнутий як з використанням адаптивності, так і без неї, однак з її використанням алгоритму потрібно до 50% менше часу. Загальний час без використання адаптивності 109720.3 с, без адаптивності - 53058.47 с.

Проведемо порівння розробленого алгоритму (2) з стандартним ГА (1) та відомими методами – гілок і границь (3) та повного перебору (4), що відображено в таблиці 2.

 

Таблиця 2.

Порівняння алгоритму з існуючими аналогами

А

Результат

Час

N=10

N=20

N=30

N=60

N=10

N=20

N=30

N=60

1

1510

1201

798

468

5094311

3480447

6413090

123343212

2

1514

1201

806

478

2049749

1778678

1119716

83159767

3

1518

1201

810

 

27285594

30294614

268806546

-

4

1528

-

-

-

379662336

-

-

-

 

 

 

 

 

 

 

 

 

Для великих N методи гілок і границь та повного перебору вимагають набагато більше часу, тому вони не виконувалися.

 

З отриманих результатів бачимо, що пропонований алгоритм є найбільш ефективним серед вищезазначених і дозволяє отримати кращий результат за меншу кількість часу. Зокрема, він витрачає у 10 раз менше часу, ніж метод гілок і границь, і у 100 раз менше, ніж метод повного перебору для N=10, а на довщих хромосомах ще менше, при тому знаходячи рішення, близьке до оптимуму.

Також було проведено дослідження залежності показника. інтегральної швидкодії, а також часу роботи запропонованого двофазного алгоритму від його характеристик– імовірностей мутації, схрешування, та значення порогу адаптивності за генами, запропонованої автором.

Адаптивність за генами. Результат до 50% зменшення часу оптимізації сховища даних можна досягти при використанні деяких характеристик алгоритму, зокрема порогу адаптивності, який визначає, при якій мінімальній відстані між хромосомами здійснюється фіксація генів. Можливий виграш від використання адаптивності за генами сильно залежить від оптимізаційного потенціалу області, а точніше від віддаленості оптимальних значень від початкових. На малих N доцільно вибирати малі <N/2, на великих – великі >N/2 . Для ілюстрації приведемо діаграму залежності швидкодії сховища з графіомк залежності часу оптимізації для N=28 (рис. 1)

 

Рисунок 1. Показники швидкодії сховища та часу роботи алгоритму при різних значеннях порогу адаптивності (N=28)

 

Мутація. Як випливає з проведених випробувань, імовірність мутації доцільно вибирати невелику, близько 0.15. Це пояснюється тим, що при високих імовірностях мутації збільшується генетична відстань, що приводить до більшого часу алгоритму, однак не забезпечує кращого значення функції швидкодії. В деяких випадках, зокрема при великих значеннях N, доцільно вибирати m>0.8 для швидшого дослідження області допустимих рішень.

Кросинговер. У результаті аналізу проведених досліджень можемо стверджувати, що для малих N доцільно вибирати малу імовірність схрещування (0.35-0..45), при великих N доцільно вибирати велику імовірність схрещування (0.8 – 0.9), хоча в окремих випадках можливе отримання схожих результатів при с=0.45-0.65.

У результаті проведених експериментів бачимо збільшення швидкодії сховища за рахунок використання двофазного алгориму до 15%. Крім того, використання адаптивності за генами дозволяє отримати скорочення часу виконання алгоритму до 50 %. Це пов'язано з змешенням часу на перепроектування сховища даних у тих випадках, коли воно не приводить до покращення цільової функції.

Виходячи з отриманих результатів, можна зробити наступні висновки про підтвердження висунутих гіпотез.

Гіпотеза 1. Розподіл даних по структурованості дозволяє пришвидшити виконанння запитів до цих даних за рахунок використання відповідних носіїв.

За рахунок виконання операцій над слабкоструктурованими даними за допомогою БД XML та MongoDB отримуємо ефективніше виконання операцій над частково-структурованими даними (до 5%).

Гіпотеза 2. Вибір найменш швидкодійного запиту в якості еталонного дозволяє оптимізувати все сховище, тобто оптимізуються всі запити.

Гіпотеза справджується, хоча існує деяка множина запитів з низькою швидкодією, що не мають потенціалу для оптимізації. Водночас, як показали результати експериментів, використовувані методи оптимізації підвищують швидкодію всіх запитів до сховища, що мають такий потенціал, а саме – розмір даних який перевищує деяку величину s (у наведених дослідженнях використовувалося s=100).

Гіпотеза 3. Використання адаптивності за генами дозволяє визначити «хворобливі» гени і відсікти цілі «під області» ОДР, що спрощує задачу і дозволяє скоротити виконання алгоритму.

Гіпотеза підтверджується, оскільки завдяки низькій імовірності мутації і близькості особин у поколіннях ми отримуємо малу відстань між мутованими і немутованими особинами, що дає нам можливість виявити впливи окремих генів і шввидко зменшити розмірність задачі за рахунок фіксації значень. Крім того, використання схрещування для отримання особин з великою відстанню дозволяє нам «відійти» від ділянок з низькими значеннями.

Висновок. У результаті проведених досліджень підтверджено зменшення часу проектування мультибазових сховищ даних до 50% у порівнянні з стандартним генетичним алгоритмом. В той же час, спроектоване сховище має до 15% більшу швидкодію виконання запитів у порівнянні з виконанням запит до джерел даних.

 

Перелік посилань:

1.     Томашевський В.М. Математична модель задачі проектування гібридних сховищ даних з врахуванням структур джерел даних [Текст]. Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. /Томашевський В.М., Яцишин А.Ю. – К.: Век+, – 2011. – № 53. – 211 с.

2.     Яцишин А.Ю. Проектування мультибазових сховищ даних на основі двохфазного алгоритму [Текст]. Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. /Томашевський В.М., Яцишин А.Ю. – К.: Век+, – 2012. – № 55. – 211 с.

3.     Яцишин А.Ю. Проектування гібридних сховищ даних з врахуванням структурованості даних. Управління розвитком складних систем. Випуск 9, 2012 / Томашевський В.М., Яцишин А.Ю. – Київ – 2012. – № 9. – 120 с.

 



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info