Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/12316
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GRIMSON, Rafael | - |
dc.contributor.author | Heintz, Joos | - |
dc.contributor.author | KUIJPERS, Bart | - |
dc.date.accessioned | 2011-11-07T10:55:15Z | - |
dc.date.available | NO_RESTRICTION | - |
dc.date.available | 2011-11-07T10:55:15Z | - |
dc.date.issued | 2011 | - |
dc.identifier.citation | INFORMATION PROCESSING LETTERS, 111(19). p. 941-944 | - |
dc.identifier.issn | 0020-0190 | - |
dc.identifier.uri | http://hdl.handle.net/1942/12316 | - |
dc.description.abstract | Let F(1),...,F(s) is an element of R[X(1),...,X(n)] be polynomials of degree at most d, and suppose that F(1),...,F(s) are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of R(n) defined by F(1),...,F(s). For any point x is an element of R(n), we consider the task of determining the signs of the values F(1)(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 F1,...,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size s(O(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 d(O(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),...,F(s) belong to Z[X(1),...,X(n)] 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),...,F(s). (C) 2011 Elsevier B.V. All rights reserved. | - |
dc.description.sponsorship | Research partially supported by the following Argentinian, Belgian and Spanish grants: CONICET PIP 2461/02, UBACYT X-098, PICT-2006-02067, MTIA 2007-62799, FWO G.0344.05. | - |
dc.language.iso | en | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject.other | Constraint databases; Query evaluation; Computational complexity | - |
dc.title | Efficient evaluation of specific queries in constraint databases | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 944 | - |
dc.identifier.issue | 19 | - |
dc.identifier.spage | 941 | - |
dc.identifier.volume | 111 | - |
local.format.pages | 4 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | [Heintz, J] Univ Buenos Aires, Fac Ciencias Exactas & Nat, Dept Comp, RA-1428 Buenos Aires, DF, Argentina. [Grimson, R] Univ Buenos Aires, Fac Ciencias Exactas & Nat, Dept Matemat, RA-1428 Buenos Aires, DF, Argentina. [Grimson, R; Heintz, J] Consejo Nacl Invest Cient & Tecn, RA-1428 Buenos Aires, DF, Argentina. [Heintz, J] Univ Cantabria, Fac Ciencias, Dept Matemat Estadist & Comp, Santander 39071, Spain. [Grimson, R; Kuijpers, B] Hasselt Univ, Database & Theoret Comp Sci Res Grp, B-3590 Diepenbeek, Belgium. rgrimson@dm.uba.ar; joos@dc.uba.ar; bart.kuijpers@uhasselt.be | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1016/j.ipl.2011.06.015 | - |
dc.identifier.isi | 000295307300002 | - |
item.contributor | GRIMSON, Rafael | - |
item.contributor | Heintz, Joos | - |
item.contributor | KUIJPERS, Bart | - |
item.validation | ecoom 2012 | - |
item.fullcitation | GRIMSON, Rafael; Heintz, Joos & KUIJPERS, Bart (2011) Efficient evaluation of specific queries in constraint databases. In: INFORMATION PROCESSING LETTERS, 111(19). p. 941-944. | - |
item.accessRights | Restricted Access | - |
item.fulltext | With Fulltext | - |
crisitem.journal.issn | 0020-0190 | - |
crisitem.journal.eissn | 1872-6119 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
grimson 1.pdf Restricted Access | Published version | 117.09 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
1
checked on Sep 5, 2020
WEB OF SCIENCETM
Citations
1
checked on Apr 22, 2024
Page view(s)
90
checked on Sep 5, 2022
Download(s)
78
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.