Space-bounded query approximation
Faculty of Sciences. Mathematics and Computer Science
Lecture notes in computer science
, p. 397-414
University of Antwerp
When dealing with large amounts of data, exact query answering is not always feasible. We propose a query approximation method that, given an upper bound on the amount of data that can be used (i.e., for which query evaluation is still feasible), identifies a part C of the data D that (i) fits in the available space budget; and (ii) provides accurate query results. That is, for a given query Q, the query result Q(C) is close to the exact answer Q(D). In this paper, we present the theoretical framework underlying our query approximation method and provide an experimental validation of the approach.