Approximate Query Processing under Bounded Resource


Yanghao Wang

Querying big data in relational databases is cost prohibitive. When the dataset is big, it is hard to compute query answer within constrained resources such as time and available processors. We consider approximate query processing to cope with querying big data. The idea is to trade-off between the query accuracy and evaluation efficiency. We study the resource bounded approximation scheme for both set answered relational algebra queries and aggregate queries, when an access schema is specified on the dataset. Under given resource constraint, we access a small fraction of data with distance bound from exact answers from access schema. In this way, we build a query driven synopsis with performance guarantee. We show that it is possible to find sensible answer within small resource budget, and the answer accuracy increases with more resources available.


Supervisors: Wenfei Fan & Leonid Libkin


Previous: Online Graph Embedding Algorithms                                                   Next: Faulty Ontology Detection and Repair