Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних

Abstract

A new approximated method of information search in database files is proposed. It is based on the use of the least-squares method. Approximation functions for records search are built. These functions are linear combinations of Chebyshew systems functions on proper intervals. By choosing different systems of Chebyshew functions, we obtain the different approximations. For such approach the approximated methods counts for distribution value of the key only and does not consider probability distribution of requests to the records. The efficiency of proposed approach is investigated by comparison with the linear search method, block search method with the optimum size of blocks and binary search method. The mathematical expectation of number of comparisons was used as an efficiency criterion.

С использованием метода наименьших квадратов предложен новый подход к построению приближенных методов поиска информации в файлах баз данных. Для поиска записей в файлах строятся аппроксимирующие функции, которые являются линейной комбинацией систем функций Чебышева на соответствующих промежутках. Выбором разных систем функций Чебышева получаем разные аппроксимации. При таком подходе приближенные методы учитывают только распределение значений ключа и не учитывают распределение вероятностей обращения к записям. Эффективность данного подхода исследуется на реальных файлах и сравнивается с методами последовательного пересмотра, блочного с оптимальным размером блоков и двоичного поисков. Критерием эффективности является среднее количество сравнений, необходимое для поиска записи в файле.

Запропоновано новий підхід до побудови наближених методів пошуку інформації у файлах баз даних, який ґрунтується на використанні методу найменших квадратів. Для пошуку записів у файлах будуються апроксимуючі функції, які є лінійними комбінаціями систем функцій Чебишева на відповідних проміжках. Вибираючи різним чином системи функцій Чебишева, отримуємо різні апроксимації. За такого підходу наближені методи враховують тільки розподіл значень ключа та не враховують розподіл ймовірностей звертання до записів. Ефективність даного підходу досліджується на реальних файлах і порівнюється з методами послідовного перегляду, блочного з оптимальним розміром блоків і двійкового пошуків. За критерій ефективності прийнято середню кількість порівнянь, необхідних для пошуку запису у файлі.