Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації великих баз даних - Автореферат

Національний університет “Львівська політехніка”Робота виконана у Львівському національному університеті імені Івана Франка Міністерства освіти і науки України Науковий керівник: Доктор фізико-математичних наук, професор Цегелик Григорій Григорович, завідувач кафедри обчислювальної математики Львівського національного університету імені Івана Франка Офіційні опоненти: Доктор технічних наук, старший науковий співробітник Яцимірський Михайло Миколайович, доцент кафедри ЕОМ національного університету «Львівська політехніка». Доктор технічних наук, доцент Сеньківський Всеволод Миколайович, завідувач кафедри прикладної математики та компютерних інформаційних систем Української академії друкарства (м. Захист відбудеться 29 червня 2001 р. о 14 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у національному університеті “Львівська політехніка” (79646, Львів-13, вул.В ній розглядається побудова та аналіз математичних моделей оптимальної організації та пошуку інформації в послідовних, одно-та багаторівневих індексно-послідовних файлах в залежності від вибраного варіанту пошуку записів та розподілу ймовірностей звертання до них. Для досягнення цієї мети необхідно розвязати такі задачі: побудова математичних моделей організації та пошуку інформації в послідовних на індексно-послідовних файлах для рівномірних та нерівномірних законів розподілу ймовірностей звертання до записів та різних методів пошуку записів в файлі та індексі; Досліджено ефективність методів послідовного перегляду, однорівневого та дворівневого блочного пошуку записів у файлах для таких законів розподілу ймовірностей звертання до записів, як рівномірний і “бінарний”, закон Зіпфа, розподіл, який наближено задовольняє правило “80-20”, та ін. Розроблено метод розвязання задачі вибору оптимального числа рівнів індекса в індексно-послідовній організації файлів для рівномірного та різних законів нерівномірного розподілу ймовірностей звертання до записів За критерій оптимальності прийнято математичне сподівання загального часу, необхідного для пошуку запису. В публікаціях, що написані у співавторстві, дисертантові належать: [2] - вивід аналітичних співвідношень для випадку нерівномірних законів розподілу, проведення експериментальних розрахунків; [3] - дослідження ефективності методу блочного пошуку для нерівномірних законів розподілу ймовірностей звертання до записів; [4]: - обчислення похибок наближень та побудова таблиць значень функції ; [5] - вивід основних аналітичних співвідношень для моделювання процесу пошуку інформації в послідовних файлах, визначення оптимальних значень математичного сподівання та параметрів організації та пошуку інформації; [6] - дослідження поведінки функції E/d0 в околі точки мінімуму математичного сподівання; [8] - встановлення оптимальних значень параметрів організації та пошуку інформації в послідовних файлах при яких математичне сподівання загального часу, необхідного для пошуку запису в файлі, буде мінімальним; [9] - вивід основних аналітичних співвідношень для моделювання процесу пошуку інформації в одно-та багаторівневих індексно-послідовних файлах, встановлення оптимальних значень параметрів організації та пошуку інформації, визначення проміжків зміни оптимальних значень параметрів пошуку, в яких математичне сподівання відхиляється від свого оптимального значення не більше ніж на задану величину, дослідження поведінки функції E/d в околі точки мінімуму; [10] - встановлення картини залежності математичного сподівання загального часу, необхідного для пошуку запису в файлі, від зміни закону розподілу ймовірностей та числа рівнів індекса файлу; [11] - розвязання задачі вибору оптимального числа рівнів індекса в індексно-послідовній організації файлів для різних законів розподілу ймовірностей звертання до записів; [12] - апроксимація часткових сум та неперервними функціями та обчислення відносної похибки цих наближень; [13] - розробка рекомендації щодо вибору параметрів організації послідовного файла та методу доступу до інформації на основі результатів експерименту; [14] - розробка рекомендації щодо вибору параметрів організації однорівневого індексно-послідовного файла та методу доступу до інформації на основі результатів експерименту;Використовуються такі варіанти пошуку: послідовне читання блоків записів в основну память і їх послідовний перегляд; послідовний перегляд записів блоку, який попередньо локалізований шляхом читання блоків записів в основну память і перегляду їх останніх записів; читання і послідовний перегляд записів блоку, який попередньо локалізований шляхом перегляду в зовнішній памяті останніх записів блоків. Нехай a=b dm - час читання блоку записів в основну память, де b, d - деякі константи; t i t1 - час перегляду запису відповідно в основній i зовнішній памяті (t1=t b d); pi-ймовірність звертання до i-го запису файла; E - математичне сподівання загального часу, необхідного для пошуку запису в файлі. Нехай N - число записів файла, ni (i=1,2,...