Projects per year
Abstract
This paper proposes BEAS, a resource-bounded scheme for querying relations. It is parameterized with a resource ratio α ∈ (0, 1], indicating that given a big dataset D, we can only afford to access an α-fraction of D with limited resources. For a query Q posed on D, BEAS computes exact answers Q(D) if doable and otherwise approximate answers, by accessing at most α|D| amount of data in the entire process. Underlying BEAS are (1) an access schema, which helps us identify and fetch the part of data needed to answer Q, (2) an accuracy measure to assess approximate answers in terms of their relevance and coverage w.r.t. exact answers, (3) an Approximability Theorem for the feasibility of resource-bounded approximation, and (4) algorithms for query evaluation with
bounded resources. A unique feature of BEAS is its ability to answer unpredictable queries, aggregate or not, using bounded resources and assuring a deterministic accuracy lower bound. Using real-life and synthetic data, we empirically verify the effectiveness and efficiency of BEAS.
bounded resources. A unique feature of BEAS is its ability to answer unpredictable queries, aggregate or not, using bounded resources and assuring a deterministic accuracy lower bound. Using real-life and synthetic data, we empirically verify the effectiveness and efficiency of BEAS.
Original language | English |
---|---|
Pages (from-to) | 973-984 |
Number of pages | 12 |
Journal | Proceedings of the VLDB Endowment (PVLDB) |
Volume | 10 |
Issue number | 9 |
DOIs | |
Publication status | Published - 1 May 2017 |
Event | 43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Germany Duration: 28 Aug 2017 → 1 Sept 2017 http://www.vldb.org/2017/index.php |
Fingerprint
Dive into the research topics of 'Data Driven Approximation with Bounded Resources'. Together they form a unique fingerprint.Projects
- 1 Finished
-
GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
1/11/15 → 31/10/21
Project: Research
Profiles
-
Yang Cao
- School of Informatics - Lecturer in Database Systems
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active