Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15806
Title: Making Queries Tractable on Big Data with Preprocessing
Authors: Fan, Wenfei
GEERTS, Floris 
NEVEN, Frank 
Issue Date: 2013
Source: Proceedings of the VLDB Endowment, 6 (1), p. 685-696
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.
Document URI: http://hdl.handle.net/1942/15806
ISSN: 2150-8097
e-ISSN: 2150-8097
DOI: http://www.vldb.org/pvldb/vol6/p685-geerts.pdf
Category: A2
Type: Journal Contribution
Appears in Collections:Research publications

Show full item record

Page view(s)

42
checked on May 24, 2022

Google ScholarTM

Check

Altmetric


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