Geodesic
A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search
Diskretnaya Matematika, Tome 23 (2011) no. 3, pp. 138-159.

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

@article{DM_2011_23_3_a8,
     author = {E. A. Snegova},
     title = {A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search},
     journal = {Diskretnaya Matematika},
     pages = {138--159},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_3_a8/}
}
TY  - JOUR
AU  - E. A. Snegova
TI  - A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 138
EP  - 159
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_3_a8/
LA  - ru
ID  - DM_2011_23_3_a8
ER  - 
%0 Journal Article
%A E. A. Snegova
%T A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search
%J Diskretnaya Matematika
%D 2011
%P 138-159
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_3_a8/
%G ru
%F DM_2011_23_3_a8
E. A. Snegova. A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search. Diskretnaya Matematika, Tome 23 (2011) no. 3, pp. 138-159. http://geodesic.mathdoc.fr/item/DM_2011_23_3_a8/

[1] Guttman A., “$R$-trees: a dynamic index structure for spatial searching”, Proc. ACM SIGMOD' 84, ACM Press, New York, 47–57

[2] Korn F., Sidiropoulos N., Faloutsos C., Siegel E., Protopapas Z., “Fast nearest neighbor search in medical image databases”, Proc. VLDB' 96, Morgan Kaufmann, San Francisco, California, 215–226

[3] Roussopoulos N., Kelley S., Vincent F., “Nearest neighbor queries”, Proc. ACM SIGMOD' 95, ACM Press, New York, 71–79

[4] Beckmann N., Kriegel H.-P, Schneider R., Seeger B., “The $\mathrm R^*$-tree: an efficient and robust access method for points and rectangles”, Proc. ACM SIGMOD' 90, ACM Press, New York, 322–331

[5] Cheung K. L., Fu A. W., “Enhanced nearest neighbour search on the $\mathrm R$-tree”, ACM SIGMOD Record, 27:3 (1998), 16–21 | DOI

[6] Benetis R., Jensen C. S., Karciauskas G., Saltenis S., “Nearest and reverse nearest neighbor queries for moving objects”, The VLDB Journal, 15:2 (2006), 229–249 | DOI

[7] Song Z., Roussopoulos N., “$K$-nearest neighbor search for moving query point”, Proc. SSTD' 01, Springer, London, 79–96 | Zbl

[8] Seidl N., Kriegel H.-P., “Optimal multi-step $k$-nearest neighbor search”, Proc. ACM SIGMOD' 98, 154–165, ACM Press, New York

[9] Tao Y., Papadias D., Shen Q., “Continuous nearest neighbor search”, Proc. VLDB' 02, Morgan Kaufmann, San Francisco, California, 287–298

[10] Gedik B., Liu L., “MobiEyes: A distributed location monitoring service using moving location queries”, IEEE TMC, 10 (2006), 1384–1402

[11] Atallah M., “Dynamic computational geometry”, Proc. FOCS' 83, IEEE Computer Society Press, Los Alamitos, California, 92–99

[12] Bentley J. L., “Multidimensional binary search trees in database applications”, Commun. ACM, 18 (1975), 509–517 | DOI | Zbl

[13] Bentley J. L., Friedman J. H., “Data structure for range searching”, ACM Comput. Surv., 11 (1979), 397–409 | DOI

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

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

[16] Leuker G. S., “A data structure for orthogonal range queries”, Proc. FOCS' 78, IEEE Computer Society Press, Los Alamitos, California, 28–34 | MR

[17] Leuker G. S., Willard D. E., “A data structure for dynamic range queries”, Inf. Proc. Lett., 15 (1982), 209–213 | DOI | MR

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

[19] Willard D. E., Predicate-oriented database search algorithms, PhD Thesis, Harvard Univ., Cambridge, 1978

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

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

[22] Skiba E. A., “Logarifmicheskoe reshenie zadachi ob opasnoi blizosti”, Intellektualnye sistemy, 11:1–4 (2007), 693–719 | MR

[23] Snegova E. A., “Sluchai zadachi ob opasnoi blizosti, svodyaschiisya k odnomernomu intervalnomu poisku”, Intellektualnye sistemy, 13:1–4 (2009), 97–118 | MR