Модифікація алгоритму хешування з метою підвищення швидкодії операцій у нереляційних базах даних

Автор(и)

  • В. Нікітін КПІ ім. Ігоря Сікорського, Україна
  • Є. Крилов КПІ ім. Ігоря Сікорського, Україна
  • Я. Корнага КПІ ім. Ігоря Сікорського, Україна
  • В. Анікін

DOI:

https://doi.org/10.20535/1560-8956.39.2021.247395

Ключові слова:

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

Анотація

Об’єктом дослідження є методи індексування у нереляційних базах даних. У статті був зроблений огляд найбільш поширених алгоритмів хешування та запропонованого алгоритму хешування на основі простих чисел та двійкової системи числення. Ця робота грунтується на основній теоремі арифметики, яка стверджує про можливість факторизації будь-якого натурального числа унікальним набором простих чисел. Даний підхід дає можливість використовувати математичний апарат для обгрунтування властивостей алгоритму. Алгоритми, що розглянуті у статті, базуються на
виконанні послідовності бітових операцій і тим самим, не можуть бути стійкими до колізій. Саме ця характеристика є найважливішою для використання розширеного хешування замість збалансованого бінарного дерева при індексації у нереляційних базах даних. Це дасть можливість не тільки підвищити швидкодію запитів, а ще дозволить
використовувати апаратні засоби максимально ефективно. Оскільки головною метою роботи є адаптація комбінованого алгоритму для нереляційних баз даних, то для досягнення цієї мети необхідно мати хеш-функцію, яка
має високу стійкість до колізій. Запропонований алгоритм було реалізовано з використанням мови програмування високого рівня С++, оскільки вона дозволяє створювати абстракції з низькою “вартістю” та мати можливість роботи на низькому рівні з інформацією. У контексті роботи, найбільш корисною можливістю є виконання операцій на
бітовому рівні. В якості практичної частини було проведено два експерименти, метою яких було виявлення різних вхідних масивів даних, які на виході давали би однакові хеші. Основною ідею експериментів була генерація випадкових даних та отримання хешів, використовуючи запропонований алгоритм. Результатом тестування є відсутність таких вхідних масивів даних. Результати досліду показали доцільним продовжувати досліджувати запропонований алгоритм з використанням математичного апарату для аналізу його властивостей.

Бібл. 4, табл. 1.

Посилання

Anton Yudhana, Abdul Fadlil, Eko Prianto. Performance Analysis of Hashing Methods on the Employment of App URL: https://www.researchgate.net/publication/ 328020140_Performance_Analysis_of_Hashing_Methods_on_the_Employment_of_App.

Michael L. Rupley, Jr.. Introduction to Query Processing and Optimization. URL: https://clas.iusb.edu/computer-science-informatics/research/reports/TR-20080105-1.pdf

V. Nikitin. Combined indexing method in nosql databases / V. Nikitin, E. Krуlov, Y.Kornaga, V. Anikin. - Adaptive Systems of Automatic Control Interdepartmental scientific and technical collection. – 2021. – №1(38) – DOI: https://doi.org/10.20535/1560-8956.38.2021.232948;

Sandeep Kumar, Er Piyush Gupta. A Comparative Analysis of SHA and MD5 Algorithm URL: https://www.researchgate.net/publication/263656830_A_Comparative_ Analysis_of_SHA_and_MD5_Algorithm

##submission.downloads##

Опубліковано

2021-12-15