Метод та засоби прискорення хеш-пошуку в постійних інформаційних структурах
| dc.contributor.advisor | Марковський, Олександр Петрович | |
| dc.contributor.author | Гарасимович, Галина Володимирівна | |
| dc.date.accessioned | 2020-01-15T08:27:01Z | |
| dc.date.available | 2020-01-15T08:27:01Z | |
| dc.date.issued | 2019 | |
| dc.description.abstractuk | Актуальність теми. Динамічний розвиток комп’ютерних технологій та поглиблення інформаційної інтеграції визначають необхідність адекватного вдосконалення такого важливого компоненти організації обробки інформації як пошук даних в пам’яті. В останні роки розвиток хмарних технологій надає принципово нові можливості для вирішення задач, реалізація яких раніше була обмежена наявними обчислювальними потужностями. Хмарні технології надають доступ до практично необмежених обчислювальних ресурсів, розкиданих по всьому світу. Високі темпи росту об’ємів баз даних та баз знань, підвищення вимог щодо оперативності доступу до них, розширення використання систем реального часу з високою питомою вагою операцій пошуку (системи розпізнавання зорових та мовних образів, лінгвістичні процесори) потребують підвищення швидкості пошуку даних за ключем. Найбільшу продуктивність операцій пошуку забезпечує використання хеш-адресації. Хеш-адресація – потенційно найбільш продуктивний способ пошуку інформації за ключем, що є базовою операцією для широкого кола систем комп’ютерної обробки даних. Показано, що для багатьох практично важливих застосувань, зокрема таких як баз даних, що працюють в реальному часі, систем компіляції, машинного перекладу, лінгвістичних процесорів та систем розпізнавання образів, продуктивність реалізації операцій пошуку за ключем є визначаль¬ним фактором ефективності. Аналіз показує, що значна частина часу пошуку при використанні хеш-адресації втрачається на вирішення колізій – явища за яким два чи більша кількість ключів мають однакові хеш-адресу. Разом з тим, існує достатньо широкий клас практичних задач, для яких множина ключів є практично незмінною. Для таких задач можна віднайти хеш-перетворення, які не утворюють колізій при заданій конкретній множині ключів. Такі хеш-перетворення отримали назву perfect хеш-перетворень. Вузлова проблема побудови хеш-перетворень, що не утворюють колізій для заданого масиву пошукових ключів полягає в тому, що це потребує значних обчислювальних ресурсів. Відповідно, існуючі методи формування таких хеш-перетворень були орієнтовані на відносно невелику кількість ключів, що обмежувало суттєвим чином практичне використання хеш-адресації без колізій. В останні роки, в зв’язку з широким розповсюдженням хмарних технологій з'явилися можливості для залучення значних за обсягом обчислю-вальних ресурсів. Відповідно, виникла необхідність в розробці нових підходів до формування хеш-перетворень без колізій з урахуванням нових можливостей. Таким чином, задача підвищення ефективності одержання хеш-перетворень, що не породжують колізій для заданого наперед масиву пошукових ключів шляхом розробки нових методів її вирішення в сучасних умовах є актуальною ї такою, що має суттєве практичне значення. Мета досліджень полягає в підвищенні ефективності формування хеш-перетворень, що не утворюють колізій для заданого масиву пошукових ключів шляхом зменшення потрібного для цього часу, а також гарантування віднаходження зазначеного хеш-перетворення для будь-якої заданої множини різних пошукових ключів. Задачі дослідження у відповідності до поставленої мети полягають у наступному: 1. Аналіз сучасного стану проблеми швидкого інформаційного пошуку за ключем для визначення вимог до хеш-перетворень, що не утворюють колізій і, забезпечують, тим самим потенційно найбільшу швидкість пошуку при одному зверненні до накопичувача. З позицій цих вимог здійснено аналітичних огляд, з позицій зазначених вимог, існуючих технологій хеш-пошуку в постійних масивах без колізій. Визначення напрямків досліджень, направлених на підвищення ефективності хеш-адресації постійних масивів ключів. 2. Розробка математичної моделі хеш-адресації без колізій у вигляді аналітичних залежностей часу формування хеш-перетворення, що не утворює колізій для наперед заданого масиву ключів від їх кількості та коефіцієнта завантаженості об’єму хеш-пам’яті при заданих обмеженнях часу віднаходження шуканого хеш-перетворення. 3. Розробка методу побудови хеш-перетворення, що не породжує колізій для заданого наперед масиву ключів, яке відрізняється тим, що воно використовує систему булевих функцій, визначену на множині розрядів ключа, кожна з яких ділить множину самих ключів навпіл, за рахунок чого досягається прискорення процесу підбору відповідних функцій при фіксованому значенні коефіцієнта завантаження хеш-пам’яті. 4. Теоретичне та експериментальне дослідження ефективності хеш-перетво¬рення, що не утворює колізій, у вигляді розділяючи булевих функцій. 5. Розробка та дослідження методу одержання хеш-функцій, що не призводять до колізій у сталих масивах ключів, якій відрізняється від відомих тим, що в якості хеш-перетворювача застосовується генератор псевдовипадкових функцій, побудованих на основі шифроблоків, за рахунок чого досягається підвищення швидкості підбору хеш-перетворення, що не утворює колізій. 6. Розробка ієрархічної багаторівневої структури хеш-адресації, вико¬рис-тан¬ня якої дозволяє дозволяє зменшити витрати часу на формування perfect хеш-алгоритму та визначені її характеристики, які забезпечують оптимізацію завантаження хеш-пам’яті; 7. Розробка програмних продуктів, які забезпечують віднаходження хеш-перетворення, що не породжує колізій для сталого масиву ключів довільної довжини при заданих обмеженнях на витрати часу та коефіцієнт використання хеш-пам’яті. Об'єктом дослідження є процеси формування хеш-перетворень, які не утворюють колізій для заданої наперед множини пошукових ключів і забезпечують, тим самим потенційно найвищу швидкість пошуку за ключем, оскільки при цього для пошуку використовується лише одне звернення до пам'яті. Предметом досліджень є методи побудови хеш-перетворень, які не утворюють колізій для заданої наперед множини пошукових ключів, методи стиснення розрядності цих ключів, підходи та способи зменшення часу формування хеш-перетворень, що не утворюють колізій. Методи дослідження базуються на теорії імовірності та математичної статистики, теорії булевих функцій та комбінаторики, теорії організації обчислювальних процесів, а також на використанні методів моделювання. Наукова новизна одержаних результатів полягає в наступному: 1. Побудована математична модель хеш-адресації, яка дозволила теоретично отримати аналітичні залежності часу формування хеш-перетворення, що не утворює колізій для наперед заданого масиву ключів від їх кількості та коефіцієнта завантаженості об’єму хеш-пам’яті при заданих обмеженнях часу віднаходження шуканого хеш-перетворення. 2. Досліджені можливості використання для безколізійної хеш-адресації сталих масивів ключів генераторів псевдовипадкових функцій, одержані оцінки ефективності та розроблено відповідні рекомендації щодо їх практичного використання. 3. Запропоновано метод побудови хеш-перетворення, що не породжує колізій для заданого наперед масиву ключів, яке відрізняється тим, що воно використовує систему булевих функцій, визначену на множині розрядів ключа, кожна з яких ділить множину самих ключів навпіл, за рахунок чого досягається прискорення процесу підбору відповідних функцій при фіксованому значенні коефіцієнта завантаження хеш-пам’яті. 4. Запропоновано новий метод одержання хеш-функцій, що не призводять до колізій у сталих масивах ключів, якій відрізняється від відомих тим, що в якості хеш-перетворювача застосовується генератор псевдовипадкових функцій, побудованих на основі шифроблоків, за рахунок чого досягається підвищення швидкості підбору хеш-перетворення, що не утворює колізій. 5. Запропонована ієрархічна багаторівнева структура хеш-адресації, вико¬рис¬тан¬ня якої дозволяє дозволяє зменшити витрати часу на формування perfect хеш-алгоритму та визначені її характеристики, які забезпечують оптимізацію завантаження хеш-пам’яті; Практичне значення одержаних результатів роботи визначається можливістю прискорення формування хеш-перетворення, що не утворює колізій для заданої множини пошукових ключів і, цим самим, забезпечує потенційно найбільшу швидкість пошуку за ключем. Результати роботи можуть бути застосовані для підвищення швидкості пошуку систем, що працюють в реальному часі: для швидкого розпізнавання образів та ситуацій в системах комп’ютерного управління об’єктами та процесами, в швидкісних базах даних колективного доступу, в лінгвістичних процесорах. Апробація результатів магістерської дисертації. Основні результати магістерської дисертації допо¬ві¬дались, обговорювались та отримали позитивну оцінку на Міжнародної конференції Security, Fault Tolerance, Intelligence. ICSFTI-2018, Київ, 10-12 травня, 2018 р. Публікації. Результатами виконаних в рамках магістерської дисертації досліджень відображені в 4-х наукових публікаціях: 1. Русанова О.В. Застосування технології Монтгомері для прискорення експоненціювання на полях Галуа / О.В.Русанова, О.П. Марковський, Г.В. Гарасимович // Альманах науки.- 2019.- № 5 (26).- С.26-30. 2. Марковский А.П. , Искаков Эмиль Русланович, Гарасимович Г.В. Комбинаторный анализ булевых функций, специальных классов для систем криптографической защиты информации. Матеріали міжнародної конференції Security, Fault Tolerance, Intelligence. ICSFTI-2018, Київ, травень 10-12, 2018. -С. 89-95 3. Марковський О. П., Ван Хуаі, Гарасимович Галина. Організація захищеного обчислення модулярної експоненти з використанням адитивного маскування / О.П.Марковський, Ван Хуаі, Г.В. Гарасимович // Матеріали міжнародної конференції Security, Fault Tolerance, Intelligence. ICSFTI-2018, Київ, травень 10-12, 2018. - С.188-194. 4. Гарасимович Г.В. Метод захисту операндів модулярного експоненціювання від їх реконструкції аналізом динаміки споживання потуж¬ості / Г.В. Гарасимович, В.Ю. Куц. // Матеріали міжнародної конференції Security, Fault Tolerance, Intelligence. ICSFTI-2018, Київ, травень 10-12, 2018. - С. 195-203. | uk |
| dc.format.page | 122 с. | uk |
| dc.identifier.citation | Гарасимович, Г. В. Метод та засоби прискорення хеш-пошуку в постійних інформаційних структурах : магістерська дис. : 123 Комп’ютерна інженерія / Гарасимович Галина Володимирівна. – Київ, 2019. – 122 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/30823 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | пошук за ключем | uk |
| dc.subject | хеш-адресація | uk |
| dc.subject | хеш-пошук | uk |
| dc.subject | хеш-адресація без колізій | uk |
| dc.subject.udc | 004.67 | uk |
| dc.title | Метод та засоби прискорення хеш-пошуку в постійних інформаційних структурах | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Ескіз недоступний
- Назва:
- Garasimovich_magistr.doc
- Розмір:
- 364.6 KB
- Формат:
- Microsoft Word
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.06 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: