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 this issue. The idea is to trade-off between the query accuracy and evaluation efficiency. We study the resource bounded approximation scheme for different application scenarios, such as set semantic queries or aggregation queries, when an access schema is specified on the dataset. Under given resource constraint, we build a query driven synopsis of small size from access schema. An approximate answer with performance guarantee in the error from exact answer can be computed efficiently from such synopsis,. 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