Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних
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 s...
Saved in:
| Published in: | Фізико-математичне моделювання та інформаційні технології |
|---|---|
| Date: | 2007 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/21101 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних / А. Мельничин, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 116-122. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-21101 |
|---|---|
| record_format |
dspace |
| spelling |
Мельничин, А. Цегелик, Г. 2011-06-15T07:57:24Z 2011-06-15T07:57:24Z 2007 Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних / А. Мельничин, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 116-122. — Бібліогр.: 7 назв. — укр. 1816-1545 https://nasplib.isofts.kiev.ua/handle/123456789/21101 519.68 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. С использованием метода наименьших квадратов предложен новый подход к построению приближенных методов поиска информации в файлах баз данных. Для поиска записей в файлах строятся аппроксимирующие функции, которые являются линейной комбинацией систем функций Чебышева на соответствующих промежутках. Выбором разных систем функций Чебышева получаем разные аппроксимации. При таком подходе приближенные методы учитывают только распределение значений ключа и не учитывают распределение вероятностей обращения к записям. Эффективность данного подхода исследуется на реальных файлах и сравнивается с методами последовательного пересмотра, блочного с оптимальным размером блоков и двоичного поисков. Критерием эффективности является среднее количество сравнений, необходимое для поиска записи в файле. Запропоновано новий підхід до побудови наближених методів пошуку інформації у файлах баз даних, який ґрунтується на використанні методу найменших квадратів. Для пошуку записів у файлах будуються апроксимуючі функції, які є лінійними комбінаціями систем функцій Чебишева на відповідних проміжках. Вибираючи різним чином системи функцій Чебишева, отримуємо різні апроксимації. За такого підходу наближені методи враховують тільки розподіл значень ключа та не враховують розподіл ймовірностей звертання до записів. Ефективність даного підходу досліджується на реальних файлах і порівнюється з методами послідовного перегляду, блочного з оптимальним розміром блоків і двійкового пошуків. За критерій ефективності прийнято середню кількість порівнянь, необхідних для пошуку запису у файлі. uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України Фізико-математичне моделювання та інформаційні технології Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних Using of least-squares method for creation of approximation methods to information search in database files Использование метода наименьших квадратов для построения приближенных методов поиска информации в файлах баз данных Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| spellingShingle |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних Мельничин, А. Цегелик, Г. |
| title_short |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| title_full |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| title_fullStr |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| title_full_unstemmed |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| title_sort |
використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних |
| author |
Мельничин, А. Цегелик, Г. |
| author_facet |
Мельничин, А. Цегелик, Г. |
| publishDate |
2007 |
| language |
Ukrainian |
| container_title |
Фізико-математичне моделювання та інформаційні технології |
| publisher |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| format |
Article |
| title_alt |
Using of least-squares method for creation of approximation methods to information search in database files Использование метода наименьших квадратов для построения приближенных методов поиска информации в файлах баз данных |
| description |
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.
С использованием метода наименьших квадратов предложен новый подход к построению приближенных методов поиска информации в файлах баз данных. Для поиска записей в файлах строятся аппроксимирующие функции, которые являются линейной комбинацией систем функций Чебышева на соответствующих промежутках. Выбором разных систем функций Чебышева получаем разные аппроксимации. При таком подходе приближенные методы учитывают только распределение значений ключа и не учитывают распределение вероятностей обращения к записям. Эффективность данного подхода исследуется на реальных файлах и сравнивается с методами последовательного пересмотра, блочного с оптимальным размером блоков и двоичного поисков. Критерием эффективности является среднее количество сравнений, необходимое для поиска записи в файле.
Запропоновано новий підхід до побудови наближених методів пошуку інформації у файлах баз даних, який ґрунтується на використанні методу найменших квадратів. Для пошуку записів у файлах будуються апроксимуючі функції, які є лінійними комбінаціями систем функцій Чебишева на відповідних проміжках. Вибираючи різним чином системи функцій Чебишева, отримуємо різні апроксимації. За такого підходу наближені методи враховують тільки розподіл значень ключа та не враховують розподіл ймовірностей звертання до записів. Ефективність даного підходу досліджується на реальних файлах і порівнюється з методами послідовного перегляду, блочного з оптимальним розміром блоків і двійкового пошуків. За критерій ефективності прийнято середню кількість порівнянь, необхідних для пошуку запису у файлі.
|
| issn |
1816-1545 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/21101 |
| citation_txt |
Використання методу найменших квадратів для побудови наближених методів пошуку інформації у файлах баз даних / А. Мельничин, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 6. — С. 116-122. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT melʹničina vikoristannâmetodunaimenšihkvadratívdlâpobudovinabliženihmetodívpošukuínformacííufailahbazdanih AT cegelikg vikoristannâmetodunaimenšihkvadratívdlâpobudovinabliženihmetodívpošukuínformacííufailahbazdanih AT melʹničina usingofleastsquaresmethodforcreationofapproximationmethodstoinformationsearchindatabasefiles AT cegelikg usingofleastsquaresmethodforcreationofapproximationmethodstoinformationsearchindatabasefiles AT melʹničina ispolʹzovaniemetodanaimenʹšihkvadratovdlâpostroeniâpribližennyhmetodovpoiskainformaciivfailahbazdannyh AT cegelikg ispolʹzovaniemetodanaimenʹšihkvadratovdlâpostroeniâpribližennyhmetodovpoiskainformaciivfailahbazdannyh |
| first_indexed |
2025-11-26T13:47:17Z |
| last_indexed |
2025-11-26T13:47:17Z |
| _version_ |
1850623627332943872 |
| fulltext |
Використання методу найменших квадратів
для побудови наближених методів пошуку
інформації у файлах баз даних
Андрій Мельничин1, Григорій Цегелик2
1 Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000,
e-mail: andrue_m@mail333.com
2 д. ф.-м. н., професор, Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів,
79000, e-mail: kafmmsep@franko.lviv.ua
Запропоновано новий підхід до побудови наближених методів пошуку інформації у файлах
баз даних, який ґрунтується на використанні методу найменших квадратів. Для пошуку за-
писів у файлах будуються апроксимуючі функції, які є лінійними комбінаціями систем функцій
Чебишева на відповідних проміжках. Вибираючи різним чином системи функцій Чебишева,
отримуємо різні апроксимації. За такого підходу наближені методи враховують тільки
розподіл значень ключа та не враховують розподіл ймовірностей звертання до записів. Ефек-
тивність даного підходу досліджується на реальних файлах і порівнюється з методами по-
слідовного перегляду, блочного з оптимальним розміром блоків і двійкового пошуків. За критерій
ефективності прийнято середню кількість порівнянь, необхідних для пошуку запису у файлі.
Ключові слова: методи пошуку, файли баз даних, метод найменших квад-
ратів, система функцій Чебишева.
Вступ. Основний акцент під час розв’язування різноманітних задач із використан-
ням концепції баз даних переноситься з процедур обробки даних на процедури
організації збереження та пошуку інформації у файлах баз даних. Тому продуктив-
ність обчислювальних систем, орієнтованих на роботу з величезними базами да-
них, значною мірою визначається ефективністю методів пошуку інформації
у файлах баз даних.
Для пошуку записів у файлах баз даних, зазвичай, використовують точні
методи. Найуживанішим серед них є метод послідовного перегляду, однорівне-
вий і багаторівневий блочний та двійковий пошуки [1-6]. Ефективність цих мето-
дів залежить від закону розподілу ймовірностей звертання до записів і не зале-
жить від розподілу значень ключа, яким характеризуються записи файла. Тому
виникає потреба мати такий метод пошуку, який би суттєво враховував розподіл
значень ключа й ефективність якого не залежала б від розподілу ймовірностей
звертання до записів. Саме такий метод і пропонується в даній роботі.
1. Постановка задачі
Розглянемо послідовний упорядкований файл, який містить N записів. Нехай Ki
),1( Ni = — значення ключа, яким характеризується i-й запис файла. Позначимо
УДК 519.68
116
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2007, вип. 6, 116-122
117
xi = i, yi = Ki, а через y = K(x) — функцію дискретного аргументу, визначену
на множині натуральних чисел від 1 до N: K(xi) = yi. Для функції y = K(x) на про-
міжку [1, N ] побудуємо апроксимуючу функцію y = φ(x) таку, щоб величина
[ ]2
1
( )
N
i i
i
y x
=
− ϕ∑ досягала мінімуму. Для забезпечення єдиності розв’язку функцію
φ(x) означимо як лінійну комбінацію функцій Чебишева φ0(x), φ1(x), ..., φm(x) на
проміжку [1, N ], m < N [7]
( )xϕ =
0
( )
m
k k
k
a x
=
ϕ∑ ,
Отже, нам потрібно знайти коефіцієнти a0, a1, ..., am, для яких величина
( ) ( )
2
0 1
1 0
, ,...,
N m
n i k k i
i k
F a a a y a x
= =
= − ϕ
∑ ∑
досягає мінімуму. Для знаходження цих коефіцієнтів одержуємо таку систему лі-
нійних алгебраїчних рівнянь
,0=
∂
∂
ja
F mj ,0= ,
або
( ) ( )
1 0
0,
N m
i k k i j i
i k
y a x x
= =
− ϕ ϕ =
∑ ∑ mj ,0= .
Перепишемо систему в такому вигляді
( ) ( ) ( )
0 1 1
,
m N N
k k i j i i j i
k i i
a x x y x
= = =
ϕ ϕ = ϕ∑ ∑ ∑ mj ,0= .
Якщо ввести позначення
( ) ( )
1
,
N
jk k i j i
i
x x
=
α = ϕ ϕ∑ ( )
1
N
j i j i
i
y x
=
β = ϕ∑ ,
то система рівнянь для знаходження коефіцієнтів ak ( )0,k m= прийме вигляд
0
m
jk k j
k
a
=
α = β∑ , mj ,0= .
Вибираючи різним чином систему функцій Чебишева φ0(x), φ1(x), ..., φm(x),
одержимо різні апроксимуючі функції.
Якщо за систему функцій Чебишева взяти φk(x) = xk, mk ,0= , то апроксимуюча
функція матиме вигляд k
m
k
k xay ∑
=
=
0
. Тоді для знаходження значень параметрів a0,
a1, ..., am одержуємо таку систему рівнянь
Андрій Мельничин, Григорій Цегелик
Використання методу найменших квадратів для побудови наближених методів пошуку...
118
2
0 1 2
1 1 1 1
2 3 1
0 1 2
1 1 1 1 1
2 3 4 2 2
0 1 2
1 1 1 1 1
... ;
... ;
... ;
................................
N N N N
m
i i m i i
i i i i
N N N N N
m
i i i m i i i
i i i i i
N N N N N
m
i i i m i i i
i i i i i
a N a x a x a x y
a x a x a x a x y x
a x a x a x a x y x
= = = =
+
= = = = =
+
= = = = =
+ + + + =
+ + + + =
+ + + + =
∑ ∑ ∑ ∑
∑ ∑ ∑ ∑ ∑
∑ ∑ ∑ ∑ ∑
1 2 2
0 1 2
1 1 1 1 1
........................................................
... .
N N N N N
m m m m m
i i i m i i i
i i i i i
a x a x a x a x y x+ +
= = = = =
+ + + + =
∑ ∑ ∑ ∑ ∑
Зокрема, при m = 1 отримаємо лінійну апроксимацію y = a0 + a1x, а при m = 2 —
квадратичну y = a0 + a1x + a2x2.
Якщо за систему функцій Чебишева прийняти φk(x) = ekx, mk ,0= , то апрок-
симуюча функція матиме вигляд ∑
=
=
m
k
kx
keay
0
. Тоді одержуємо таку систему рівнянь
для визначення параметрів a0, a1, ..., am
2
0 1 2
1 1 1 1
2 3 ( 1)
0 1 2
1 1 1 1 1
2 3 4 ( 2) 2
0 1 2
1 1 1 1 1
... ;
... ;
... ;
...............
i i i
i i i i i
i i i i i
N N N N
x x mx
m i
i i i i
N N N N N
x x x m x x
m i
i i i i i
N N N N N
x x x m x x
m i
i i i i i
a N a e a e a e y
a e a e a e a e y e
a e a e a e a e y e
= = = =
+
= = = = =
+
= = = = =
+ + + + =
+ + + + =
+ + + + =
∑ ∑ ∑ ∑
∑ ∑ ∑ ∑ ∑
∑ ∑ ∑ ∑ ∑
( 1) ( 2) 2
0 1 2
1 1 1 1 1
...............................................................................
... .i i i i i
N N N N N
mx m x m x mx mx
m i
i i i i i
a e a e a e a e y e+ +
= = = = =
+ + + + =
∑ ∑ ∑ ∑ ∑
Зокрема, якщо m = 1, то отримаємо експоненційну апроксимацію y = a0 + a1ex.
Побудовані апроксимуючі функції можуть використовуватися для пошуку
записів за значеннями ключа.
2. Комп’ютерний експеримент
Нами проведено комп’ютерний експеримент із дослідження ефективності запро-
понованого підходу на реальних файлах. У таблиці приведені значення ключа фай-
ла, на основі якого проводився експеримент. Ці значення були згенеровані ви-
падковим чином.
Нами побудовано лінійну, експоненційну та квадратичну апроксимуючі функції.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2007, вип. 6, 116-122
119
Таблиця
Значення ключа файла
X Y X Y X Y X Y X Y
1 1 21 39 41 77 61 114 81 160
2 3 22 40 42 78 62 115 82 161
3 5 23 44 43 79 63 118 83 165
4 7 24 45 44 80 64 123 84 166
5 10 25 47 45 82 65 124 85 168
6 11 26 48 46 83 66 125 86 169
7 12 27 50 47 84 67 129 87 170
8 18 28 51 48 86 68 130 88 172
9 19 29 53 49 87 69 131 89 173
10 20 30 55 50 90 70 132 90 174
11 21 31 58 51 91 71 135 91 176
12 22 32 60 52 93 72 138 92 177
13 23 33 61 53 94 73 141 93 178
14 25 34 65 54 96 74 144 94 180
15 26 35 67 55 99 75 146 95 182
16 28 36 70 56 100 76 150 96 184
17 29 37 71 57 102 77 151 97 185
18 32 38 72 58 103 78 153 98 186
19 33 39 74 59 106 79 156 99 187
20 35 40 75 60 113 80 157 100 189
1,9483 2,7691y x= − , R2 = 0,997;
0,029815,701 xy e= , R2 = 0,7852;
20,0018 1,7667 0,3187y x x= + + , R2 = 0,9972.
Тут R — коефіцієнт кореляції.
Було проведено порівняння ефективності запропонованого підходу з методами
послідовного перегляду, блочного з оптимальним розміром блоків і двійкового
пошуків. За критерій ефективності приймалася середня кількість порівнянь, не-
обхідних для пошуку запису у файлі. У випадку методу послідовного перегляду,
блочного з оптимальним розміром блоків і двійкового пошуків середня кількість
порівнянь, необхідних для пошуку запису у файлі, відповідно становить 50,50;
11,00 і 5,78. Якщо пошук здійснювати з використанням лінійної, експонен-
ціальної або квадратичної апроксимацій, тобто відповідно за формулами
( )2,7691 1,9483x y= + ;
[ ]ln ln(15,701) 0,0298x y= − ;
23,5704 433,185 490,754x y= + − ,
то середня кількість порівнянь, необхідних для пошуку запису у файлі, відповід-
но становить 1,21; 9,51 та 1,08.
Андрій Мельничин, Григорій Цегелик
Використання методу найменших квадратів для побудови наближених методів пошуку...
120
Рис. 3. Розподіл значень ключів та апроксимуюча квадратична функція
40·105
35·105
30·105
25·105
20·105
15·105
10·105
5·105
0
2·105 0 4·105 6·105 8·105 10·105 12·105 14·105 16·105 18·105
Рис. 2. Розподіл значень ключів й апроксимуюча експоненціальна функція
40·105
35·105
30·105
25·105
20·105
15·105
10·105
5·105
0
0 2·103 4·103 6·103 8·103 10·103 12·103 14·103 16·103 18·103
40·105
35·105
30·105
25·105
20·105
15·105
10·105
5·105
0
2·103 0 4·103 6·103 8·103 10·103 12·103 14·103 16·103 18·103
Рис. 1. Розподіл значень ключів та апроксимуюча лінійна функція
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2007, вип. 6, 116-122
121
Нами також проведено обчислювальний експеримент із файлом реальної бази
даних студентів, які навчаються стаціонарно у Львівському національному уні-
верситеті імені Івана Франка. Цей файл містить 16768 записів. На основі файла
значень ключа (номерів залікових книжок) побудовано три апроксимуючі функції:
лінійну, квадратичну й експоненційну, а також проведено порівняння ефектив-
ності пошуку з використанням цих функцій, з ефективністю методів послідовно-
го перегляду, блочного з оптимальним розміром блоків і двійкового пошуків. За
критерій ефективності прийнято середню кількість порівнянь, необхідних для
пошуку запису у файлі.
Лінійна апроксимуюча функція (див. рис. 1) є такою 803196 144,313y x= +
(R2 = 0,922). Для пошуку записів маємо формулу ( )803196 114,313x y= − .
Експоненційна апроксимуюча функція (див. рис. 2) є такою y = exp(13,8572 +
+ 7,1889 · 10 –5x) (R2 = 0,969). Пошук записів здійснюється з використанням фор-
мули x = (ln y – 13,8572) / 7,1889×10–5.
Квадратична апроксимуюча функція (див. рис. 3) є такою y = 0,0085x2 +
+ 1,1578x + 1,2 · 106 (R2 = 0,982), а для пошуку маємо x = 10,86213 1099974y − –
– 758,94.
3. Порівняльна ефективність методу
Проведено порівняння ефективності запропонованого підходу з методами послі-
довного перегляду, блочного з оптимальним розміром блоків і двійкового пошуків.
За критерій ефективності прийнято середню кількість порівнянь, необхідних для
пошуку запису у файлі. У випадку методу послідовного перегляду, блочного та
двійкового пошуків середня кількість порівнянь, необхідних для пошуку запису у
файлі, відповідно становить 8384,50; 130,49 і 13,05. Якщо пошук здійснювати з
використанням лінійної, експоненціальної та квадратичної апроксимацій, то се-
редня кількість порівнянь, необхідних для пошуку запису у файлі, відповідно є
1251,28; 702,82 та 701,09.
Висновки. Запропоновано метод пошуку у файлах баз даних, що враховує розпо-
діл значень ключа, якими характеризуються записи файла. Проведено порівняння
ефективності запропонованого підходу з методами послідовного перегляду, блоч-
ного з оптимальним розміром блоків і двійкового пошуків для реальних файлів.
Результати порівнянь показали, що запропонований підхід є ефективніший, ніж
метод послідовного перегляду, але поступається блочному пошуку з оптималь-
ним розміром блоків і двійковому пошуку.
Література
[1] Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. —
М.: Издательский дом «Вильямс», 2000. — 832 с.
[2] Мартин Дж. Организация баз данных в вычислительных системах. — М.: Мир,
1980. — 644 с.
Андрій Мельничин, Григорій Цегелик
Використання методу найменших квадратів для побудови наближених методів пошуку...
122
[3] Мельничин А., Цегелик Г. Ефективність методу двійкового пошуку інформації у фай-
лах баз даних для різних законів розподілу ймовірностей звертання до записів //
Вісн. Львів. ун-ту. Сер. прикл. матем. та інформ. — 2006. — Вип. 11. — C. 225-229.
[4] Мельничин А. В., Цегелик Г. Г. Аналіз методів пошуку інформації в файлах баз да-
них для різних законів розподілу ймовірностей звертання до записів // Зб. наук.
праць Української академії друкарства «Комп’ютерні технології друкарства». —
2006. — № 15. — С. 95-112.
[5] Цегелик Г. Г., Мельничин А. В. Порівняльний аналіз ефективності методів пошуку
інформації у файлах баз даних // Відбір і обробка інформації. — 2005. — № 23(99). —
С. 135-142.
[6] Цегелик Г. Г. Организация и поиск информации в базах данных. — Львов: Вища шк.,
1987. — 176 с.
[7] Цегелик Г. Г. Чисельні методи: підручник. — Львів: Вид. центр Львівського нац.
ун-ту ім. І. Франка. — 2004. — 408 с.
Использование метода наименьших квадратов
для построения приближенных методов поиска
информации в файлах баз данных
Андрей Мельничин, Григорий Цегелик
С использованием метода наименьших квадратов предложен новый подход к построению
приближенных методов поиска информации в файлах баз данных. Для поиска записей в
файлах строятся аппроксимирующие функции, которые являются линейной комбинацией
систем функций Чебышева на соответствующих промежутках. Выбором разных систем
функций Чебышева получаем разные аппроксимации. При таком подходе приближенные ме-
тоды учитывают только распределение значений ключа и не учитывают распределение
вероятностей обращения к записям. Эффективность данного подхода исследуется на ре-
альных файлах и сравнивается с методами последовательного пересмотра, блочного с оп-
тимальным размером блоков и двоичного поисков. Критерием эффективности является
среднее количество сравнений, необходимое для поиска записи в файле.
Using of least-squares method for creation of approximation
methods to information search in database files
Andriy Melnytchyn, Hryhoriy Tsehelyk
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.
Отримано 01.06.07
|