Paper Info
Title
Compressed Representations of Conjunctive Query Results
Abstract
Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole materialized output if we plan to reuse it further down a data processing pipeline. Motivated by this problem, we study the construction of space-efficient compressed representations of the output of conjunctive queries, with the goal of supporting the efficient access of the intermediate compressed result for a given access pattern. In particular, we initiate the study of an important tradeoff: minimizing the space necessary to store the compressed result, versus minimizing the answer time and delay for an access request over the result. Our main contribution is a novel parameterized data structure, which can be tuned to trade off space for answer time. The tradeoff allows us to control the space requirement of the data structure precisely, and depends both on the structure of the query and the access pattern. We show how we can use the data structure in conjunction with query decomposition techniques in order to efficiently represent the outputs for several classes of conjunctive queries.
Year
DOI
Venue
2017
10.1145/3196959.3196979
SIGMOD/PODS '18: International Conference on Management of Data Houston TX USA June, 2018
Keywords
Field
DocType
Query enumeration, Compressed representation, Space delay tradeoff, Join algorithms, Constant delay enumeration
Data structure,Data processing,Conjunctive query,Parameterized complexity,Reuse,Computer science,Theoretical computer science
Journal
Volume
ISBN
Citations 
abs/1709.06186
978-1-4503-4706-8
2
PageRank 
References 
Authors
0.36
27
2
Name
Order
Citations
PageRank
Shaleen Deep1185.32
Paraschos Koutris234726.63