Geodesic
Information storage and search complexity theory
Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 49-73.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a new information-graph model for information storage and search. This model generalizes a number of known data representation models. We study the main properties of the proposed model. We solve the problem of optimal informational graph synthesis for a wide class of search problems including the most acute database search problems. 
@article{FPM_2009_15_3_a5,
     author = {E. E. Gasanov},
     title = {Information storage and search complexity theory},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {49--73},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a5/}
}
TY  - JOUR
AU  - E. E. Gasanov
TI  - Information storage and search complexity theory
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2009
SP  - 49
EP  - 73
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a5/
LA  - ru
ID  - FPM_2009_15_3_a5
ER  - 
%0 Journal Article
%A E. E. Gasanov
%T Information storage and search complexity theory
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2009
%P 49-73
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a5/
%G ru
%F FPM_2009_15_3_a5
E. E. Gasanov. Information storage and search complexity theory. Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 49-73. http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a5/

[1] Andreev A. E., “Metod bespovtornoi reduktsii sinteza samokorrektiruyuschikhsya skhem”, DAN SSSR, 283:2 (1985), 265–269 | MR | Zbl

[2] Blaivas T. D., “Optimalnoe reshenie zadachi intervalnogo poiska na bulevom kube v klasse sbalansirovannykh drevovidnykh skhem”, Intellekt. sist., 7:1–4 (2002–2003), 223–245

[3] Blaivas T. D., “Asimptotika slozhnosti intervalnogo poiska na bulevom kube v klasse sbalansirovannykh derevev”, Diskret. mat., 16:4 (2004), 65–78 | DOI | MR | Zbl

[4] Blaivas T. D., “Odin algoritm resheniya zadachi intervalnogo poiska na bulevom kube”, Intellekt. sist., 8:1–4 (2004), 389–408

[5] Blaivas T. D., O slozhnosti intervalnogo poiska na bulevom kube, Dis. $\dots$ kand. fiz.-mat. nauk, M., 2005

[6] Blaivas T. D., “Clozhnost poiska po maske dlya algoritma s zhëstkim poryadkom proverok”, Intellekt. sist., 9:1–4 (2005), 347–362

[7] Blaivas T. D., “Funktsiya Shennona slozhnosti intervalnogo poiska na bulevom kube v klasse derevev”, Diskret. mat., 18:2 (2006), 111–122 | DOI | MR | Zbl

[8] Bychenkova E. S., “Asimptoticheskoe reshenie zadachi o metricheskoi blizosti dlya odnogo bazovogo mnozhestva funktsii”, Intellekt. sist., 6:1–4 (2001), 221–230

[9] Bychenkova E. S., “Optimalnyi po poryadku metod sinteza odnogo poiskovogo operatora v klasse avtomatnykh skhem spetsialnogo vida”, Diskret. mat., 15:1 (2003), 131–156 | DOI | MR | Zbl

[10] Voronin B. V., Osokin V. V., “O slozhnosti rasshifrovki suschestvennykh peremennykh funktsii, zadayuschei razbienie bulevogo kuba”, Intellekt. sist. (to appear)

[11] Gasanov E. E., “Optimalnye informatsionnye seti dlya otnoshenii poiska, yavlyayuschikhsya otnosheniyami lineinogo kvaziporyadka”, Konstruktsii v algebre i logike, Izd-vo Tverskogo gos. un-ta, Tver, 1990, 11–17 | MR

[12] Gasanov E. E., “Ob odnoi matematicheskoi modeli informatsionnogo poiska”, Diskret. mat., 3:2 (1991), 69–76 | MR | Zbl

[13] Gasanov E. E., “Nizhnyaya otsenka slozhnosti informatsionnykh setei dlya odnogo klassa zadach informatsionnogo poiska”, Diskret. mat., 4:3 (1992), 118–127 | MR | Zbl

[14] Gasanov E. E., “Ob odnomernoi zadache intervalnogo poiska”, Diskret. mat., 7:2 (1995), 40–60 | MR | Zbl

[15] Gasanov E. E., “Mgnovenno reshaemye zadachi poiska”, Diskret. mat., 8:3 (1996), 119–134 | DOI | MR | Zbl

[16] Gasanov E. E., “Nizhnyaya otsenka slozhnosti informatsionnykh setei dlya odnogo otnosheniya chastichnogo poryadka”, Diskret. mat., 8:4 (1996), 108–122 | DOI | MR | Zbl

[17] Gasanov E. E., Funktsionalno-setevye bazy dannykh i sverkhbystrye algoritmy poiska, Izd. tsentp RGGU, M., 1997

[18] Gasanov E. E., Teoriya slozhnosti informatsionnogo poiska, Izd-vo mekhaniko-matematicheskogo f-ta MGU, M., 2005

[19] Gasanov E. E., Erokhin A. N., “Lineinyi po pamyati neperebornyi algoritm resheniya dvumernoi zadachi intervalnogo poiska”, Diskret. mat., 16:4 (2004), 49–64 | DOI | MR | Zbl

[20] Gasanov E. E., Erokhina E. P., “Modelirovanie i slozhnost poiska v mnogoprotsessornykh sistemakh”, Diskret. mat., 11:3 (1999), 63–82 | DOI | MR | Zbl

[21] Gasanov E. E., Kosolapov A. V., “K voprosu o drevovidnosti optimalnykh informatsionnykh setei vklyuchayuschego poiska”, Intellekt. sist., 3:1–2 (1998), 167–192

[22] Gasanov E. E., Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, FIZMATLIT, M., 2002 | Zbl

[23] Gasanov E. E., Kuznetsova I. V., “O funktsionalnoi slozhnosti dvumernoi zadachi intervalnogo poiska”, Diskret. mat., 14:1 (2002), 114–141 | DOI | MR | Zbl

[24] Gasanov E. E., Lugovskaya Yu. P., “Konstantnyi v khudshem sluchae algoritm poiska identichnykh ob'ektov”, Diskret. mat., 11:4 (1999), 139–144 | DOI | MR | Zbl

[25] Gasanov E. E., Mkhitarova T. V., “Ob odnoi matematicheskoi modeli fonovykh algoritmov poiska i bystryi fonovyi algoritm dvumernoi zadachi o dominirovanii”, Fundament. i prikl. mat., 3:3 (1997), 759–773 | MR | Zbl

[26] Ershov A. P., “O programmirovanii arifmeticheskikh operatorov”, DAN SSSR, 118 (1958), 427–430 | Zbl

[27] Efremov D. V., “Svoistva chastichno-uporyadochennykh mnozhestv, zadavaemykh perestanovkami”, Intellekt. sist., 9:1–4 (2005), 363–380

[28] Knut D., Iskusstvo programmirovaniya dlya EVM. T. 3: Sortirovka i poisk, Mir, M., 1978 | MR | Zbl

[29] Kudryavtsev V. B., Funktsionalnye sistemy, Izd-vo Mosk. un-ta, M., 1982 | Zbl

[30] Kudryavtsev V. B., Gasanov E. E., Podkolzin A. S., Vvedenie v teoriyu intellektualnykh sistem, Izd-vo f-ta VMiK MGU, M., 2006

[31] Kucherenko N. S., “Slozhnost poiska identichnykh ob'ektov dlya sluchainykh baz dannykh”, Intellekt. sist., 11:1–4 (2007), 495–516 | MR

[32] Kucherenko N. S., “Srednyaya slozhnost poiska identichnykh ob'ektov dlya sluchainykh neravnomernykh baz dannykh”, Diskret. mat. (to appear)

[33] Lapshov I. S., “Dinamicheskie bazy dannykh, osnovyvayuschiesya na kheshirovanii metodom tsepochek”, Intellekt. sist., 9:1–4 (2005), 191–207

[34] Lapshov I. S., “Dinamicheskie bazy dannykh s optimalnoi po poryadku vremennoi slozhnostyu”, Diskret. mat., 20:3 (2008), 89–100 | DOI | MR | Zbl

[35] Li D., Preparata F., “Vychislitelnaya geometriya. Obzor”, Kibernet. sb., 24, 1987, 5–96 | Zbl

[36] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Nauka, M., 1963, 63–97 | MR

[37] Mailybaeva G. A., “Granitsy vyrozhdennosti protokolov dostupa k dannym bez raskrytiya zaprosa”, Diskret. mat., 18:2 (2006), 98–110 | DOI | MR | Zbl

[38] Mailybaeva G. A., Kommunikatsionnaya slozhnost protokolov dostupa k dannym bez raskrytiya zaprosov, Dis. $\dots$ kand. fiz.-mat. nauk, M., 2007

[39] Mailybaeva G. A., “Tochnoe znachenie kommunikatsionnoi slozhnosti dlya odnogo klassa PIR-protokolov”, Intellekt. sist., 11:1–4 (2007), 167–200

[40] Mailybaeva G. A., “Poryadok kommunikatsionnoi slozhnosti dlya odnogo klassa PIR-protokolov”, Diskret. mat., 20:3 (2008), 136–146 | DOI | MR

[41] Martin Dzh., Organizatsiya baz dannykh v vychislitelnykh sistemakh, Mir, M., 1980

[42] Nyumen U. M., Spruell R. F., Osnovy interaktivnoi mashinnoi grafiki, Mir, M., 1976

[43] Osokin V. V., “Asimptoticheski optimalnyi algoritm rasshifrovki razbieniya bulevogo kuba na podkuby”, Intellekt. sist., 11:1–4 (2007), 587–606 | MR

[44] Osokin V. V., “O slozhnosti rasshifrovki razbieniya bulevogo kuba na podkuby”, Diskret. mat., 20:2 (2008), 46–62 | DOI | MR | Zbl

[45] Pivovarov A. P., “Poisk predstavitelya v zadache o metricheskoi blizosti”, Intellekt. sist. (to appear)

[46] Preparata F., Sheimos M., Vychislitelnaya geometriya: Vvedenie, Mir, M., 1989 | MR | Zbl

[47] Reshetnikov V. N., “Algebraicheskaya teoriya informatsionnogo poiska”, Programmirovanie, 1979, no. 3, 68–74 | MR

[48] Selton G., Avtomaticheskaya obrabotka, khranenie i poisk informatsii, Sovetskoe radio, M., 1973

[49] Skiba E. A., “Logarifmicheskoe reshenie zadachi ob opasnoi blizosti”, Intellekt. sist., 11:1–4 (2007), 645–676 | MR

[50] Feschuk A. A., “K voprosu analiza nechetkikh informatsionnykh grafov”, Diskret. mat., 14:2 (2002), 65–84 | DOI | MR | Zbl

[51] Kharina A. A., “O svedenii nechëtkogo informatsionnogo poiska k informatsionnomu poisku bolshei razmernosti”, Intellekt. sist., 9:1–4 (2005), 57–76

[52] Shennon K., Raboty po teorii informatsii i kibernetike, Izd. inostr. lit., M., 1963

[53] Shutkin Yu. S., “Sintez informatsionnykh grafov dlya predpolnykh klassov bulevykh funktsii”, Intellekt. sist., 11:1–4 (2007), 689–604 | MR

[54] Shutkin Yu. S., “O realizatsii bulevykh funktsii informatsionnymi grafami”, Diskret. mat., 20:4 (2008), 29–41 | DOI | MR | Zbl

[55] Ben-Or M., “Lower bounds for algebraic computation trees”, Proc. 15th ACM Ann. Symp. Theory Comput., April, 1983, 80–86

[56] Bentley J. L., Friedman J. H., “Data structures for range searching”, Comput. Surveys, 11 (1979), 397–409 | DOI

[57] Bentley J. L., Maurer H. A., “Efficient worst-case data structures for range searching”, Acta Inform., 13 (1980), 155–168 | DOI | MR | Zbl

[58] Bentley J. L., Stanat D. F., “Analysis of range searching in quad trees”, Inform. Process. Lett., 3 (1975), 170–173 | DOI | Zbl

[59] Bolour A., “Optimal retrieval algorithms for small region queries”, SIAM J. Comput., 10 (1981), 721–741 | DOI | MR | Zbl

[60] Chazelle B. M., “Filtering search: A new approach to query-answering”, Proc. 24th IEEE Ann. Symp. Found. Comput. Sci., November, 1983, 122–132

[61] Fredman M. L., Baskett F., Shustek J., “An algorithm for finding nearest neighbors”, IEEE Trans. Comput., C-24 (1975), 1000–1006 | DOI

[62] Fredman M. L., Bentley J. L., Finkel R. A., “An algorithm for finding best match in logarithmic expected time”, ACM Trans. Math. Software, 3:3 (1977), 209–226 | DOI

[63] Gasanov E. E., “On functional complexity of two-dimensional Manhattan metrics closeness problem”, Emerging Database Research in East Europe, Proc. of the Pre-Conference Workshop of VLDB 2003, Berlin, 2003, 51–56

[64] Lee D. T., Wong C. K., “Worst case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”, Acta Inform., 9 (1977), 23–29 | DOI | MR | Zbl

[65] Lueker G. S., “A data structure for ortogonal range queries”, Proc. 19th IEEE Ann. Symp. Found. Comput. Sci., 1978, 28–34 | MR