Geodesic
A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 49-64 
È. È. Gasanov; A. N. Erokhin. A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 49-64. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a5/
@article{DM_2004_16_4_a5,
     author = {\`E. \`E. Gasanov and A. N. Erokhin},
     title = {A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem},
     journal = {Diskretnaya Matematika},
     pages = {49--64},
     year = {2004},
     volume = {16},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a5/}
}
TY  - JOUR
AU  - È. È. Gasanov
AU  - A. N. Erokhin
TI  - A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 49
EP  - 64
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a5/
LA  - ru
ID  - DM_2004_16_4_a5
ER  - 
%0 Journal Article
%A È. È. Gasanov
%A A. N. Erokhin
%T A nonexhaustive algorithm, linear with respect to memory, for solving a two-dimensional interval search problem
%J Diskretnaya Matematika
%D 2004
%P 49-64
%V 16
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a5/
%G ru
%F DM_2004_16_4_a5

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

We suggest an algorithm to solve a two-dimensional interval search problem which is characterised by the memory consumed of order $k$, the average search time (without the time needed to output the answer) of order $\sqrt k$, where $k$ is the database size. This research was supported by the Russian Foundation for Basic Research, grant 01–01–00748.

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

[2] Gasanov E. E., “O lineinom po pamyati neperebornom algoritme dvumernogo intervalnogo poiska”, Tezisy dokladov XIII Mezhdunarodnoi konferentsii “Problemy teoreticheskoi kibernetiki”, Kazan, 2002, 44 | Zbl

[3] Gasanov E. E, Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, Fizmatlit, Moskva, 2002 | Zbl

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

[5] Gasanov E. E., “Mgnovenno reshaemye zadachi poiska”, Diskretnaya matematika, 8:3 (1996), 119–134 | MR | Zbl