Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15806
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFan, Wenfei-
dc.contributor.authorGEERTS, Floris-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2013-10-16T08:55:27Z-
dc.date.available2013-10-16T08:55:27Z-
dc.date.issued2013-
dc.identifier.citationProceedings of the VLDB Endowment, 6 (9), p. 685-696-
dc.identifier.issn2150-8097-
dc.identifier.urihttp://hdl.handle.net/1942/15806-
dc.description.abstractA 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.description.sponsorshipFan is supported in part by the RSENSFC Joint Project Scheme, EPSRC EP/J015377/1, UK, and the 973 Program 2012CB316200 and NSFC 61133002 of China-
dc.language.isoen-
dc.publisherACM-
dc.rights2013 VLDB Endowment-
dc.titleMaking queries tractable on big data with preprocessing: through the eyes of complexity theory-
dc.typeJournal Contribution-
dc.identifier.epage696-
dc.identifier.issue9-
dc.identifier.spage685-
dc.identifier.volume6-
local.format.pages12-
local.bibliographicCitation.jcatA2-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.identifier.doi10.14778/2536360.2536368-
dc.identifier.urlhttp://www.vldb.org/pvldb/vol6/p685-geerts.pdf-
dc.identifier.eissn2150-8097-
local.provider.typeCrossRef-
local.uhasselt.internationalyes-
item.accessRightsRestricted Access-
item.contributorFan, Wenfei-
item.contributorGEERTS, Floris-
item.contributorNEVEN, Frank-
item.fullcitationFan, Wenfei; GEERTS, Floris & NEVEN, Frank (2013) Making queries tractable on big data with preprocessing: through the eyes of complexity theory. In: Proceedings of the VLDB Endowment, 6 (9), p. 685-696.-
item.fulltextWith Fulltext-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
p685-geerts.pdf
  Restricted Access
Published version889.76 kBAdobe PDFView/Open    Request a copy
Show simple item record

SCOPUSTM   
Citations

28
checked on Sep 14, 2025

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.