Geodesic
On the functional complexity of a two-dimensional interval search problem
Diskretnaya Matematika, Tome 14 (2002) no. 1, pp. 114-141.

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

We suggest a modification of the Bentley–Maurer algorithm which solves a two-dimensional interval search problem. This modification allows us to decrease the initially logarithmic average search time to constant, retaining the logarithmic worst-case search time. This algorithm depends on a parameter whose change results in variation of the needed memory from $\mathcal O(k^3)$ to $\mathcal O(k\log k)$; the average search time (without the time needed to output the answer) varies from $\mathcal O(1)$ to $\mathcal O(\log k)$. In particular, for any $\varepsilon>0$ and available memory $\mathcal O(k^{1+\varepsilon})$ the average search time is $\mathcal O(1)$. On the basis of these results, we give upper bounds for the functional complexity of a two-dimensional interval search problem. This research was supported by the Russian Foundation for Basic Research, grants 98–01–00130, 01–01–00748. 
@article{DM_2002_14_1_a8,
     author = {\`E. \`E. Gasanov and I. V. Kuznetsova},
     title = {On the functional complexity of a two-dimensional interval search problem},
     journal = {Diskretnaya Matematika},
     pages = {114--141},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_1_a8/}
}
TY  - JOUR
AU  - È. È. Gasanov
AU  - I. V. Kuznetsova
TI  - On the functional complexity of a two-dimensional interval search problem
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 114
EP  - 141
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_1_a8/
LA  - ru
ID  - DM_2002_14_1_a8
ER  - 
%0 Journal Article
%A È. È. Gasanov
%A I. V. Kuznetsova
%T On the functional complexity of a two-dimensional interval search problem
%J Diskretnaya Matematika
%D 2002
%P 114-141
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2002_14_1_a8/
%G ru
%F DM_2002_14_1_a8
È. È. Gasanov; I. V. Kuznetsova. On the functional complexity of a two-dimensional interval search problem. Diskretnaya Matematika, Tome 14 (2002) no. 1, pp. 114-141. http://geodesic.mathdoc.fr/item/DM_2002_14_1_a8/

[1] Li D., Preparata F., “Vychislitelnaya geometriya. Obzor”, Kibern. sb., 24 (1987), 5–96 | Zbl

[2] Knut D., Iskusstvo programmirovaniya dlya EVM. Sortirovka i poisk, t. 3, Mir, Moskva, 1978 | MR | Zbl

[3] Loftsgaarden D. O., Queensberry C. P., “A nonparametric density function”, Ann. Math. Stat., 36 (1965), 1049–1051 | DOI | MR | Zbl

[4] Lauter U, “4-dimensional binary search trees as a means to speed up associative searches in design verification of integrated circuits”, J. Design Automation and Fault Tolerant Computing, 2 (1978), 241–247 | MR

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

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

[7] Bentley J. L., “Multidimensional binary search trees used for associative searching”, Commun. Ass. Comput. Mach., 18 (1975), 509–517 | Zbl

[8] Bentley J. L., “Decomposable searching problems”, Inform. Processing Letters, 8 (1979), 244–251 | DOI | MR | Zbl

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

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

[11] Bentley J. L., Shamos M. I., “A problem in multivariate statistics: algorithms data structure and applications”, Proc. 15th Allerton Conf. Commun., Contr., Comput., 1977, 193–201

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

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

[14] Chazelle B. M., “Filtering search: a new approach to query-answering”, Proc. 24th IEEE Annual Symp. Found. Computer Sci., 1983, 122–132

[15] Fredman M. L., “A lower bound of the complexity of ortogonal range queries”, J. ACM., 28 (1981), 696–705 | DOI | MR | Zbl

[16] Gabow H. N., Bentley J. L., Tarjan R. E., Proc. 16th ACM Annual Symp. Theory Comput., 1984

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

[18] Lee D. T., Wong C. K., “Quintari trees: a file structures for multidimensional database system.”, ACM Trans. Database Syst., 1:1 (1980), 339–353 | DOI

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

[20] Lueker G. S., Willard D. E., “A data structure for dynamic range queries”, Inform. Processing Letters, 15:5 (1982), 209–213 | DOI | MR | Zbl

[21] Saxe J. B., “On the number of range queries in $k$-space”, Discr. Appl. Math., 1 (1979), 217–225 | DOI | MR | Zbl

[22] Willard D. E., Predicate-oriented database search algorithms, Ph. D. Dissertation, Harvard Univ., Cambridge, MA, 1978

[23] Gasanov E. E., Kuznetsova I. V., “On one method to decrease average search time”, Abstr. First Turkish World Math. Symp., Elazig, Turkey, 1999

[24] Abdul Sattar A. V., Funktsionalnaya mera slozhnosti vychislenii v avtomatnykh skhemakh, Avtoreferat disser. kand. fiziko-matem. nauk. MGU, Moskva, 1994

[25] Gasanov E. E., Kuznetsova I. V., “Otsenki funktsionalnoi slozhnosti dvumernoi zadachi intervalnogo poiska”, Tezisy dokl. XII Mezhdunarodnoi konf. “Probl. teoretich. kibern.”, Nizhnii Novgorod, 1999

[26] Gasanov E. E., “Informatsionno-grafovaya model khraneniya i poiska dannykh”, Intellekt. sistemy, 3:3–4 (1998), 163–192

[27] Gasanov E. E., Funktsionalno-setevye bazy dannykh i sverkhbystrye algoritmy poiska, Izd. tsentr RGGU, Moskva, 1997