Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Let F1,...,FsεR[X1,...,Xn] be polynomials of degree at most d, and suppose that F1,...,F s are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F 1,...,Fs. For any point xεRn, we consider the task of determining the signs of the values F1(x),...,F s(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F 1,...,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal. By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F 1,...,Fs belong to Z[X1,...,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F 1,...,Fs. © 2011 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Efficient evaluation of specific queries in constraint databases
Autor:GrimsOn, R.; Heintz, J.; Kuijpers, B.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Ciudad Univ. Pab. i, 1428 Ciudad Autónoma de Buenos Aires, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Ciudad Univ. Pab. i, 1428 Ciudad Autónoma de Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, 39071 Santander, Spain
Database and Theoretical Computer Science Research Group, Hasselt University, Agoralaan, Gebouw D, 3590 Diepenbeek, Belgium
Palabras clave:Computational complexity; Constraint databases; Query evaluation; Arithmetic circuit; Arithmetic operations; Connected component; Constraint Databases; Genericity; Keypoints; Mutatis-mutandis; Point location; Query evaluation; Sign conditions; Upper Bound; Polynomials; Database systems
Año:2011
Volumen:111
Número:19
Página de inicio:941
Página de fin:944
DOI: http://dx.doi.org/10.1016/j.ipl.2011.06.015
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v111_n19_p941_GrimsOn

Referencias:

  • Meyer Auf Der Heide, F., A polynomial linear search algorithm for the n-dimensional knapsack problem (1984) Journal of the ACM, 31 (3), pp. 668-676. , DOI 10.1145/828.322450
  • Meiser, S., Point location in arrangements of hyperplanes (1993) Inf. Comput., 106, pp. 286-303
  • Liu, D., A note on point location in arrangements of hyperplanes (2004) Inf. Process. Lett., 90, pp. 93-95
  • Kuper, G., Libkin, L., Paredaens, J., (2000) Constraint Databases, , Springer-Verlag
  • Strassen, V., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity (A), pp. 633-672
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic Complexity Theory (1997) Grundlehren der Mathematischen Wissenschaften, , Springer
  • Grigoriev, D., Topological complexity of the range searching (2000) J. Complexity, 16, pp. 50-53
  • Chazelle, B., Sharir, M., An algorithm for generalized point location and its applications (1990) J. Symb. Computation, 10, pp. 281-309
  • Grimson, R., (2010) Upper and Lower Complexity Bounds for SOme Problems in Elementary Geometry, , Ph.D. thesis, Hasselt University, Department of Mathematics, Physics & Computer Science
  • Basu, S., Pollack, R., Roy, M.F., Algorithms in Real Algebraic Geometry (2006) Algorithms and Computation in Mathematics, 10. , 2nd edn. Springer-Verlag Secaucus, NJ, USA
  • Canny, J.F., Improved algorithms for sign determination and existential quantifier elimination (1993) The Computer Journal, 36, pp. 409-418

Citas:

---------- APA ----------
GrimsOn, R., Heintz, J. & Kuijpers, B. (2011) . Efficient evaluation of specific queries in constraint databases. Information Processing Letters, 111(19), 941-944.
http://dx.doi.org/10.1016/j.ipl.2011.06.015
---------- CHICAGO ----------
GrimsOn, R., Heintz, J., Kuijpers, B. "Efficient evaluation of specific queries in constraint databases" . Information Processing Letters 111, no. 19 (2011) : 941-944.
http://dx.doi.org/10.1016/j.ipl.2011.06.015
---------- MLA ----------
GrimsOn, R., Heintz, J., Kuijpers, B. "Efficient evaluation of specific queries in constraint databases" . Information Processing Letters, vol. 111, no. 19, 2011, pp. 941-944.
http://dx.doi.org/10.1016/j.ipl.2011.06.015
---------- VANCOUVER ----------
GrimsOn, R., Heintz, J., Kuijpers, B. Efficient evaluation of specific queries in constraint databases. Inf. Process. Lett. 2011;111(19):941-944.
http://dx.doi.org/10.1016/j.ipl.2011.06.015