Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/15806
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Fan, Wenfei | - |
dc.contributor.author | GEERTS, Floris | - |
dc.contributor.author | NEVEN, Frank | - |
dc.date.accessioned | 2013-10-16T08:55:27Z | - |
dc.date.available | 2013-10-16T08:55:27Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Proceedings of the VLDB Endowment, 6 (1), p. 685-696 | - |
dc.identifier.issn | 2150-8097 | - |
dc.identifier.uri | http://hdl.handle.net/1942/15806 | - |
dc.description.abstract | A query class is traditionally considered tractable if there exists a polynomial-time (PTIME) algorithm to answer its queries. When it comes to big data, however, PTIME al- gorithms often become infeasible in practice. A traditional and e ective approach to coping with this is to preprocess data o -line, so that queries in the class can be subsequently evaluated on the data e ciently. This paper aims to pro- vide a formal foundation for this approach in terms of com- putational complexity. (1) We propose a set of -tractable queries, denoted by T0 Q, to characterize classes of queries that can be answered in parallel poly-logarithmic time (NC) after PTIME preprocessing. (2) We show that several natu- ral query classes are -tractable and are feasible on big data. (3) We also study a set TQ of query classes that can be ef- fectively converted to -tractable queries by re-factorizing its data and queries for preprocessing. We introduce a form of NC reductions to characterize such conversions. (4) We show that a natural query class is complete for TQ. (5) We also show that T0 Q P unless P = NC, i.e., the set T0 Q of all -tractable queries is properly contained in the set P of all PTIME queries. Nonetheless, TQ = P, i.e., all PTIME query classes can be made -tractable via proper re- factorizations. This work is a step towards understanding the tractability of queries in the context of big data. | - |
dc.language.iso | en | - |
dc.title | Making Queries Tractable on Big Data with Preprocessing | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 696 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 685 | - |
dc.identifier.volume | 6 | - |
local.bibliographicCitation.jcat | A2 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | http://www.vldb.org/pvldb/vol6/p685-geerts.pdf | - |
item.accessRights | Closed Access | - |
item.fullcitation | Fan, Wenfei; GEERTS, Floris & NEVEN, Frank (2013) Making Queries Tractable on Big Data with Preprocessing. In: Proceedings of the VLDB Endowment, 6 (1), p. 685-696. | - |
item.contributor | Fan, Wenfei | - |
item.contributor | GEERTS, Floris | - |
item.contributor | NEVEN, Frank | - |
item.fulltext | No Fulltext | - |
crisitem.journal.issn | 2150-8097 | - |
crisitem.journal.eissn | 2150-8097 | - |
Appears in Collections: | Research publications |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.