Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних
Побудовано оптимальний пошук записів з використанням m-паралельного блочного пошуку в послідовних упорядкованих файлах баз даних, які зберігаються в зовнішній пам'яті багатопроцесорної ЕОМ, для таких законів розподілу ймовірностей звертання до записів, як рівномірний, "бінарний", Зіпф...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Фізико-механічний інститут ім. Г.В. Карпенка НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/16103 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних / В.Я. Лісовець, Г.Г. Цегелик // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 105-111. — Бібліогр.: 9 назв. — укp. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859672693745385472 |
|---|---|
| author | Лісовець, В.Я. Цегелик, Г.Г. |
| author_facet | Лісовець, В.Я. Цегелик, Г.Г. |
| citation_txt | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних / В.Я. Лісовець, Г.Г. Цегелик // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 105-111. — Бібліогр.: 9 назв. — укp. |
| collection | DSpace DC |
| description | Побудовано оптимальний пошук записів з використанням m-паралельного блочного пошуку в послідовних упорядкованих файлах баз даних, які зберігаються в зовнішній пам'яті багатопроцесорної ЕОМ, для таких законів розподілу ймовірностей звертання до записів, як рівномірний, "бінарний", Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило "80 - 20". За критерій оптимальності взято математичне сподівання загального часу, необхідного для пошуку запису у файлі.
The optimal search are built with using of the method of m-parallel block search in ordered files of database for probability distribution of record request frequency as: discrete uniform, binomial, Zipf and generalized the partial occasion of witch is the probability distribution approximately satisfying the rule "80 - 20". The mathematical expectation of total time needed for search of a record in file is taken as a criterion of optimality.
|
| first_indexed | 2025-11-30T14:15:40Z |
| format | Article |
| fulltext |
ISSN 0474-8662. . 2009. . 31 (107) 105
004.272.26
. . , . .
m
The optimal search are built with using of the method of m-parallel block search in ordered files of
database for probability distribution of record request frequency as: discrete uniform, binomial, Zipf
and generalized the partial occasion of witch is the probability distribution approximately satisfying
the rule “80 – 20”. The mathematical expectation of total time needed for search of a record in file is
taken as a criterion of optimality.
m
, -
, , -
, “ ”, , ,
“80 – 20”. -
, .
-
( ).
-
. , -
,
.
-
. ,
, .
.
,
: -
, .
, ,
. , , -
.
[2–6] m -
m -
, -
,
. , -
-
-
[9]. [5]
, -
,
m .
, m -
, , -
.
. . , . . , 2009
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)106
-
[1–8]:
” ,
,
.
-
. ,
N , ,
m ,
. , n sm
( N nsm ) . -
, ,
m .
m [2, 4].
a0 = b0 + d0m – m , b0, d0 – -
; t0 – m -
; pi – ; Et – -
, .
Et ,
, -
, . Et
0 0 ( 1) ( 1) 0 0 ( 1) ( 1)
1 1 1 1 1 1
( )
n s m n s m
t k ms i m j k ms i m j
k i j k i j
E a t k p a s t i p ,
0 0 0 0 ( 1) ( 1)
1 1 1
( )
n s m
t k ms i m j
k i j
E a s a t k t i p .
Et -
, n s -
.
1 ( 1) ( 1)
1 1 1
n s m
k ms i m j
k i j
E ip , 2 ( 1) ( 1)
1 1 1
n s m
k ms i m j
k i j
E kp .
0 0 0 2 0 1( )tE a s a t E t E .
. ,
1
ip
N
, i = 1, 2, … , N.
1
1 ( 1)
2
E s , 2
1 ( 1)
2
E n
0 0 0 0
1 1( 1)( ) ( 1)
2 2tE a s n a t s t ,
ISSN 0474-8662. . 2009. . 31 (107) 107
0 0 0
1 1( 1) ( ) 2
2 2t
N NE n b d m n t
nm nm
.
0 0 02 2
1 1( ) 1
2 2
tdE N Nb d m t
dn n m n m
,
n, Et (m -
),
0
0
0 0
0 0
1
b m
dNn
b tm m
d d
.
/s N mn .
” . -
“ ” ,
1
2
i ip , i = 1,2, ... , N–1, 1
1
2
N Np ,
, [9],
1
2 (1 2 )
2 2 1 2 1
m
N
N m ms
s sE , 2
2 (1 2 )
2 1
ms
N
msE .
2-N,
0 0 0 0
2 2( )
2 1 2 1 2 1
ms m
t ms m ms
sE a s a t t ,
0 0 0
2 2 2( )
2 1 2 1 2 1
ms m ms
t ms m ms
sE s b d m t .
0 0 02 2
2 ( 1) ln 2 1 12 ln 21 ( )
(2 1) (2 1)
msms
t
ms ms
s mdE m b d m t
ds
,
m 2, s 2, m, s N Et s = 2.
0 0 0
4 2 4 22 ( )
4 1 2 1 4 1
m m m
t m m mE b d m t .
. ,
,
1
i
N
p
iH
, i = 1,2, ... , N ,
1
1N
N
k
H
k
– . , [9],
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)108
1
1 ( ( ) ( ))N ms m
N
E H s S n S sn
H
, 2
1 (( 1) ( ))N ms
N
E n H S n
H
,
1
( )
n
ms kms
k
S n H ,
1
( )
ns
m km
k
S ns H .
0 0 0 0
1 ( 1) ( ) ( ) ( )t N ms N ms m
N
E a s n H S n a t H s S n S sn t
H
.
( )msS n ( )mS ns [8]
1
1( ) ( 1) ln
2
ms NS n n H n C , 1
1( ) ( 1) ln( )
2
m NS ns ns H ns C ,
C1 = 0,5ln 2 ,
0 1 0 0
1 0
1 1 ln
2
1 11 ln ln ,
2 2
t N
N
N
E a s H n n C a t
H
H s n C s t
0 0 1 0 0 0
1 0
1 1 ln
2
1 11 ln ln .
2 2
t N
N
N
NE b d m H n n C b t d m
mn H
N NH n C t
mn nm
0 0 0 0 02
1 02
1 11
2
1 1 1ln 2 1 ,
2
t
N
dE Nb d m b t d m
dn H nmn
N Nn C t
mn n nmn
n, Et -
,
0 0 0 0
1
0 0 0
2 1 ln 2 1 2 N
b t t bNn n m n C H m
d m d d
.
. -
,
( )
1
i cc
N
p
i H
, i = 1,2, ... , N,
(0<c<1) – , ( )
1
1N
c
N c
k
H
k
–
. , [9],
( ) ( ) ( )
1 ( )
1 ( ) ( )c c c
ms mNc
N
E H s S n S sn
H
, ( ) ( )
2 ( )
1 ( 1) ( )c c
msNc
N
E n H S n
H
,
( )( )
1
( )
n
cc
ms kms
k
S n H , ( )( )
1
( )
n
cc
m km
k
S n H .
ISSN 0474-8662. . 2009. . 31 (107) 109
( ) ( )( ) ( ) ( )
0 0 0 0( )
1 ( 1) ( ) ( ) ( )c cc c c
t ms ms mN Nc
N
E a s n H S n a t H s S n S ns t
H
.
( ) ( )c
msS n ( ) ( )c
mS ns [8]
1 ( )( ) ( )
1
1 ( )( ) ( )
1 2
c cc c
ms N c
N c nS n nH n
c c n
,
1 ( )( ) ( )
1
1 ( )( ) ( )
1 2 ( )
c cc c
m N c
N c nsS ns nsH ns
c c ns
,
( ) ( 1) 21( )
2
c c c
nn H n
c
, ( ) ( 1) 21( ) ( )
2
c c c
nsns H ns
c
– -
,
1 ( )
( )
0 0 0( ) 1
1 ( ) ( )
( )
01 1
1 1 ( )( )
1 2
( ) ( ) ,
1 ( )
c c
c
t Nc c
N
c c c
c
N c c
N c nE a s H n a t
c c nH
N n nsH s t
c n ns
1 ( )
( )
0 0 0 0 0( ) 1
1 ( ) ( )
( )
02 1
1 1 ( )( )
1 2
( ) ( / ) .
1 ( / )
c c
c
t Nc c
N
c c c
c
N c c
N N c nE b d m H n b t d m
mn c c nH
N N n N mH t
c m n N m
Et n,
( )
( ) ( )( )
( 1) ( )
c
c cd n
n n
dn
.
0 02
1 ( ) ( ) ( )
( ) 2
1 ( ) ( ) ( )
0 0 0 03
1 1 ( ( 1) ( )) (1 ) ( )
1 2
( ( 1) ( )) (2 ) ( ) .
1
t
c c c c
c c
N
c c c c
c
dE N b d m
dn mn
N c n n n c n
c c nH
N N n n n c nb t d m t
c m n
n, Et
,
3 ( ) ( ) ( )
0 0 02
( ) ( ) ( )
02
( ) 1
0 0
2 ( 1) ( ) (1 ) ( )
(1 )
2 ( 1) ( ) (2 ) ( )
(1 )
2 .
1
c c c c
c c c
c
c c
N
cn n n n n c n b d m t
c
c N n n n c n t
mc
c N H n b d m
c m
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)110
. -
b0, d0 t0 , -
,
, b0/d0 t0/d0,
.
Et Et/d0,
:
0 0
0 0 0
1 11 2
2 2
tE b tN Nn m n
d nm d nm d
;
”
0 0
0 0 0
2 2 2
2 1 2 1 2 1
ms m ms
t
ms m ms
E b tss m
d d d
;
0 0 0
1
0 0 0
0
1
0
1 1 ln
2
1 11 ln ln ;
2 2
t
N
N
N
E b b tNm H n n C m
d d mn H d
tN NH n C
mn nm d
1 ( )
( )0 0 0
( ) 1
0 0 0
1 ( ) ( )
( ) 0
2 1
0
1 1 ( )( )
1 2
( ) ( / ) .
1 ( / )
c c
ct
Nc c
N
c c c
c
N c c
E b b tN N c nm H n m
d d mn c c dnH
tN N n N mH
c m dn N m
n, Et/d0 ,
Et/d0 n N = 106, m -
. 1 . 2.
1. n
m
= 0,2 = 0,4 = 0,6 = 0,8
”
1 1414 1500 1633 1868 2380 3794 1000000
2 1000 1061 1155 1321 1683 2683 500000
4 707 750 816 934 1190 1897 250000
5 632 671 730 835 1064 1697 200000
10 447 474 516 591 753 1200 100000
20 316 335 365 418 532 849 50000
40 224 237 258 295 376 600 25000
50 200 212 231 264 337 537 20000
100 141 150 163 187 238 380 10000
ISSN 0474-8662. . 2009. . 31 (107) 111
2. Et /d0
m
= 0,2 = 0,4 = 0,6 = 0,8
“ ”
1 142 889 134 721 123 763 108 196 84 934 53 311 336
2 102 053 96 220 88 395 77 278 60 669 38 091 312
4 73 592 69 387 63 745 55 731 43 758 27 483 312
5 66 461 62 664 57 569 50 333 39 521 24 826 315
10 49 249 46 436 42 662 37 302 29 295 18 414 330
20 38 008 35 838 32 927 28 793 22 618 14 230 360
40 31 375 29 585 27 184 23 774 18 684 11 769 420
50 30 075 28 360 26 059 22 792 17 915 11 291 450
100 28 384 26 767 24 598 21 520 16 926 10 689 600
m -
. -
m -
,
, , -
, “ ”, , ,
“80–20”. -
, .
, -
m
.
1. . . . 3: . – .: .
”, 2000. – 832 .
2. . . . . m
// -
. – 2007. – . 5. – . 109–119.
3. . . . . m
// . – 2007. – . 27(103). – . 87–92.
4. ., . m
// . . . . . . . – 2006. – . 13. –
. 177–186.
5. ., .
// . .- . . “ -
”. – . – 2008. – . 277–280.
6. . ., . . m-
// -
. – 2008. – . 7. – . 103–111.
7. . . – : , 1980. – 644 .
8. . . . – : . ., 1987.
– 176 .
9. . . . – : , 1990. – 168 .
14.04.2009
МАТЕМАТИЧНЕ ТА ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ
УДК 004.272.26
В. Я. Лісовець, Г. Г. Цегелик
ОПТИМІЗАЦІЯ m-ПАРАЛЕЛЬНОГО БЛОЧНОГО ПОШУКУ ІНФОРМАЦІЇ У ПОСЛІДОВНИХ ФАЙЛАХ БАЗ ДАНИХ
|
| id | nasplib_isofts_kiev_ua-123456789-16103 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0474-8662 |
| language | Ukrainian |
| last_indexed | 2025-11-30T14:15:40Z |
| publishDate | 2009 |
| publisher | Фізико-механічний інститут ім. Г.В. Карпенка НАН України |
| record_format | dspace |
| spelling | Лісовець, В.Я. Цегелик, Г.Г. 2011-02-04T18:09:36Z 2011-02-04T18:09:36Z 2009 Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних / В.Я. Лісовець, Г.Г. Цегелик // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 105-111. — Бібліогр.: 9 назв. — укp. 0474-8662 https://nasplib.isofts.kiev.ua/handle/123456789/16103 004.272.26 Побудовано оптимальний пошук записів з використанням m-паралельного блочного пошуку в послідовних упорядкованих файлах баз даних, які зберігаються в зовнішній пам'яті багатопроцесорної ЕОМ, для таких законів розподілу ймовірностей звертання до записів, як рівномірний, "бінарний", Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило "80 - 20". За критерій оптимальності взято математичне сподівання загального часу, необхідного для пошуку запису у файлі. The optimal search are built with using of the method of m-parallel block search in ordered files of database for probability distribution of record request frequency as: discrete uniform, binomial, Zipf and generalized the partial occasion of witch is the probability distribution approximately satisfying the rule "80 - 20". The mathematical expectation of total time needed for search of a record in file is taken as a criterion of optimality. uk Фізико-механічний інститут ім. Г.В. Карпенка НАН України Математичне та програмне забезпечення Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних Optimization of m-parallel block information searching in sequential database files Article published earlier |
| spellingShingle | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних Лісовець, В.Я. Цегелик, Г.Г. Математичне та програмне забезпечення |
| title | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| title_alt | Optimization of m-parallel block information searching in sequential database files |
| title_full | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| title_fullStr | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| title_full_unstemmed | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| title_short | Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| title_sort | оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних |
| topic | Математичне та програмне забезпечення |
| topic_facet | Математичне та програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/16103 |
| work_keys_str_mv | AT lísovecʹvâ optimízacíâmparalelʹnogobločnogopošukuínformacííuposlídovnihfailahbazdanih AT cegelikgg optimízacíâmparalelʹnogobločnogopošukuínformacííuposlídovnihfailahbazdanih AT lísovecʹvâ optimizationofmparallelblockinformationsearchinginsequentialdatabasefiles AT cegelikgg optimizationofmparallelblockinformationsearchinginsequentialdatabasefiles |