Edinburgh Research Explorer

Data Driven Approximation with Bounded Resources

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Final published version, 832 KB, PDF document

    Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

http://www.vldb.org/pvldb/vol10/p973-cao.pdf
Original languageEnglish
Title of host publicationThe 43rd International Conference on Very Large Data Bases (VLDB)
Pages973-984
Number of pages12
Publication statusPublished - 31 May 2017
Event43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Germany
Duration: 28 Aug 20171 Sep 2017
http://www.vldb.org/2017/index.php

Publication series

Name
ISSN (Electronic)2150-8097

Conference

Conference43rd International Conference on Very Large Data Bases
Abbreviated titleVLDB 2017
CountryGermany
CityMunich
Period28/08/171/09/17
Internet address

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.

Event

43rd International Conference on Very Large Data Bases

28/08/171/09/17

Munich, Germany

Event: Conference

Download statistics

No data available

ID: 36017409